首页 > 代码库 > vmware笔试题目
vmware笔试题目
http://discuss.acmcoder.com/topic/58db8e2ebb0f44ba0e94e670
上面是完整的题目，下面一下我自己的想法。
这次做的比较菜，就做出来第二题，1和3都没搞出来。
1. 第一题，首先知道数一个数阶乘末尾0的个数，由于5*2 = 10,5比2多，所以就变成数因子5的个数，5的数法，需要找规律，首先每五个数有一个因子5，然后接下来压缩后，每5个数，还有一个5，不断的递归调用，即可。同理，数其他的质因子都是这样吧。
我做的时候，老是以为有什么规律，默认为就是数学题么，肯定有规律的，然后没接出来。
有了快速数5的个数的方法以后，那么解法就显而易见了，就是二分。而且题目，也提醒单调的性质，就差直接提醒你用二分了，然后就是对可能的答案进行二分，多了往左走，少了往右走。很容易分析最大可能的答案是最大的数乘以5.然后二分。
总结出一个套路：有单调的性质，或者有非递减的性质之类的，立马要想到二分，有些二分可能不明显，如对答案二分等，需要仔细分析。同时，注意二分的几种写法，满足要求最小的，满足要求最大的，或者唯一的，写法都不太一样，注意。
1 #include <bits/stdc++.h> 2 typedef long long ll; 3 using namespace std; 4 const ll inf = 5e8; 5 6 ll work(ll t) { 7 ll res = 0; 8 while(t > 1) { 9 res += t / 5;10 t /= 5;11 }12 return res;13 }14 void solve() {15 int x;16 for (x = 1; x <= 50; x++) {17 ll left = 5, right = inf;18 while(left < right) {19 ll mid = (left + right) / 2;20 ll t = work(mid);21 if(t < x) left = mid + 1;22 else right = mid;23 }24 if(work(left) == x) cout << left << endl;25 else cout << -1 << endl;26 }27 }28 29 int main() {30 freopen("test.in", "r", stdin);31 freopen("test.out", "w", stdout);32 ios::sync_with_stdio(0);33 cin.tie(0); cout.tie(0);34 solve();35 return 0;36 }
2. 第二题，显然是一棵树，然后固定树的层次结构，对每一个节点，需要找到儿子里面的最长路径，以及该节点外的最长路径，发现不好计算，然后转化为依次切割每一条边，分别这个边两边的最长路径。看答案，我是真的把边删掉，其实只要简单设置根节点的父节点为相邻节点即可，真是个好方法。然后这个题数据范围很小，应该能跑出来，每次都是O（n）的，所以很容易的就ac了。
1 /* 2 ID: y1197771 3 PROG: test 4 LANG: C++ 5 */ 6 #include<bits/stdc++.h> 7 #define pb push_back 8 #define FOR(i, n) for (int i = 0; i < (int)n; ++i) 9 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl10 typedef long long ll;11 using namespace std;12 typedef pair<int, int> pii;13 const int maxn = 2e2 + 10;14 int e[maxn][maxn];15 int n;16 vector<pii> a;17 int ans;18 int work(int u, int p) {19 int x, y;20 x = y = 0;21 for (int i = 1; i <= n; i++) {22 if(e[u][i] && i != p) {23 int t = work(i, u);24 if(t > y) y = t;25 if(y > x) swap(x, y);26 }27 }28 ans = max(ans, x + y + 1);29 return x + 1;30 }31 void solve() {32 while(cin >> n) {33 memset(e, 0, sizeof e);34 int x, y;35 a.clear();36 for (int i = 0; i < n - 1; i++) {37 cin >> x >> y;//cout << x << " " << y << endl;38 e[x][y] = 1;39 e[y][x] = 1;40 a.pb({x, y});41 42 }43 44 int res = 0;45 46 for (int i = 0; i < n - 1; i++) {47 x = a[i].first, y = a[i].second;48 e[x][y] = e[y][x] = 0;49 int t1, t2;50 t1 = t2 = 0;51 ans = 0;52 work(x, 0);53 t1 = max(0, ans - 1);54 ans = 0;55 work(y, 0);56 t2 = max(0, ans - 1);57 res = max(res, t1 * t2);58 e[x][y] = e[y][x] = 1;59 }60 cout << res << endl;61 }62 }63 int main() {64 freopen("test.in", "r", stdin);65 //freopen("test.out", "w", stdout);66 ios::sync_with_stdio(0);67 cin.tie(0); cout.tie(0);68 solve();69 return 0;70 }
3. 第三题，读完题意，没啥想法，我的想法是对每一个区间进行求解，每个区间必须是匹配的，也就是完整的，然后第一个位置就是‘（’，然后一次枚举‘）’可以放的位置，进行递归求解，复杂度太高。直接tle。
没想法，只好看题解答案。
居然是转化成1,-1的形式进行处理，太巧秒了！（我就想到上次有一个01的序列，求最长的区间，这个区间满足0和1的个数相等，也是处理成-1和1的形式，真是够巧妙的。）处理成1，-1的形式，那么括号匹配的情况就很显然了，就是前面和为0，而且合法的情况必然是前面的和大于等于0的，这个也很关键，下面考虑怎么缩减问题规模，也就是怎么转移（通常的dp套路，缩减问题规模，转化为规模较小的子问题，而分出来的那一小部分很好计算）。然后就是第k个位置，可能的合法的情况就是0-k，0代表前面完全匹配，k代表前面的都是左括号，这样，前面就不会出现右括号不匹配的情况。
特别注意n*=2，然后考虑还会有一些非法的情况出现，比如偶数位置上，是不可能达到0的，设置这些状态为一个很小的数，使得不干扰最后的结果。
真是个好题！
1 /* 2 ID: y1197771 3 PROG: test 4 LANG: C++ 5 */ 6 #include<bits/stdc++.h> 7 #define pb push_back 8 #define FOR(i, n) for (int i = 0; i < (int)n; ++i) 9 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl10 typedef long long ll;11 using namespace std;12 typedef pair<int, int> pii;13 const int maxn = 1e3 + 10;14 const int inf = -1e9;15 int dp[2010][2010];16 int n;17 int a1[2010], a2[2010];18 void solve() {19 cin >> n;20 for (int i = 1; i <= 2 * n; i++) {21 cin >> a1[i];22 }23 for (int i = 1; i <= 2 * n; i++) {24 cin >> a2[i];25 }26 for (int i = 1; i <= n * 2; i++)27 dp[0][i] = inf;28 for (int i = 1; i <= n * 2; i++) {29 for (int j = 0; j <= i; j++) {30 if(j == 0) {31 dp[i][j] = dp[i - 1][j + 1] + a2[i];32 } else {33 dp[i][j] = max(dp[i - 1][j + 1] + a2[i], dp[i - 1][j - 1] + a1[i]);34 }35 }36 }37 cout << dp[n * 2][0] << endl;38 }39 int main() {40 freopen("test.in", "r", stdin);41 //freopen("test.out", "w", stdout);42 ios::sync_with_stdio(0);43 cin.tie(0); cout.tie(0);44 solve();45 return 0;46 }
做完题目，只有多总结，分析原因，尤其是自己当初做的时候是怎么想的，有没有计算复杂度，考虑可行性， 不行的话，有没有pass掉， 然后为什么没有想出题解的这样的方式，这才是最重要的，这样提高才是最快的，否则，跟没有做一样！
vmware笔试题目