360笔试题

http://discuss.acmcoder.com/topic/58cd31e475bf559a0653f98f 上面这个是360笔试题

跑步：

简单数学题，直接用三角函数计算坐标。

#include <bits/stdc++.h> #define maxn 100009 using namespace std; const double PI = acos(-1.0); int main(){ int L,R; scanf("%d%d", &L, &R); double theta = 1.0 * L / R; printf("%.3f %.3f\n", R * cos(-theta), R * sin(-theta)); printf("%.3f %.3f\n", R * cos(theta), R * sin(theta)); return 0; }

剪气球串：

动态规划，考虑前i个有多少种剪法，枚举最后剪的一段转移。 示例代码：

#include <bits/stdc++.h> #define maxn 100009 using namespace std; int n; int a[maxn], dp[maxn]; int cnt[11]; const int MOD = 1e9 + 7; int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); } dp[0] = 1; for(int i = 1; i <= n; i++){ memset(cnt, 0 ,sizeof(cnt)); for(int j = 0; j < i; j++){ cnt[a[i - j]]++; if(cnt[a[i - j]] > 1) break; dp[i] = (dp[i] + dp[i - j - 1]) % MOD; } } printf("%d\n", dp[n]); return 0; }

冒泡，快排，二分查找

#include <iostream> #include <vector> using namespace std; void bubbleSort(vector<int>& toBeSortedNums){ for (int i = 0; i < toBeSortedNums.size(); i++){ for (int j = 0; j < toBeSortedNums.size() - 1 - i; j++){ if (toBeSortedNums[j] > toBeSortedNums[j + 1]){ int temp = toBeSortedNums[j]; toBeSortedNums[j] = toBeSortedNums[j + 1]; toBeSortedNums[j + 1] = temp; } } } } void quickSort(int array[], int low, int high){ if (low >= high) return; int first = low; int last = high; int key = array[first]; while (first < last){ while (first < last && array[last] >= key) last--; array[first] = array[last];//小的放前面 while (first < last && array[first] <= key) first++; array[last] = array[first];//大的放后面 } array[first] = key; quickSort(array, low, first - 1); quickSort(array, first + 1, high); } int binSerch(int array[], int start, int end, int key){ int mid; while (start <= end){ if (array[start] == key) return start; if (array[end] == key) return end; mid = start + (end - start) / 2; if (array[mid] == key) return mid; if (array[mid] < key) start = mid + 1; if (array[mid] > key) end = mid - 1; } if (start > end) return -1; } int main(){ vector<int> toBeSortedNums = { 22, 11, 3, 4, 6, 7, 9, 21, 12, 34, 55, 28, 19 }; bubbleSort(toBeSortedNums); int array[] = { 22, 11, 3, 4, 6, 7, 9, 21, 12, 34, 55, 28, 19 }; quickSort(array, 0, sizeof(array) / sizeof(array[0]) - 1); int res = binSerch(array, 0, sizeof(array) / sizeof(array[0]) - 1, 9); return 0; }