IT校招全国统一模拟笔试(秋招备战专场) 编程题参考代码汇总
题目https://www.nowcoder.com/test/5217106/summary
变换次数
分析
暴力计算即可.
参考code
#include <bits/stdc++.h> using namespace std; int n, ans, tmp; int main() { cin >> n; while(n > 9) { tmp = 1; for(; n; n /= 10) tmp *= n % 10; n = tmp; ans++; } cout << ans << endl; }
神奇数
分析
枚举区间内的数,然后check一下要求的性质即可。
参考code
#include <bits/stdc++.h> using namespace std; bool isprime(int x) { for(int i = 2; i * i <= x; i++) { if(x % i == 0) return false; } return true; } bool check(int x) { int cnt[10]; memset(cnt, 0, sizeof(cnt)); while(x) { cnt[x % 10]++; x /= 10; } for(int i = 1; i < 10; i++) { for(int j = 1; j < 10; j++) { if(i != j && cnt[i] && cnt[j]) { if(isprime(i * 10 + j)) return true; }else if(i == j && cnt[i] >= 2) { if(isprime(i * 10 + j)) return true; } } } return false; } int main() { int a, b, ans = 0;; cin >> a >> b; for(int i = a; i <= b; i++) { if(check(i)) ans++; } cout << ans << endl; return 0; }
添加字符
分析
分为A长度小于B的情况和等于的情况。
小于就枚举B串的一个偏移量,然后枚举维护最小的不相等的位数。
等于就直接对比就好了。
参考code
#include <bits/stdc++.h> using namespace std; int main() { string a, b; cin >> a >> b; int la = a.size(), lb = b.size(); if(la < lb) { int ans = 1e9; for(int i = 0; i + la <= lb; i++) { int cnt = 0; for(int j = 0; j < la; j++) { if(a[j] != b[i + j]) cnt++; } if(cnt < ans) { ans = cnt; } } cout << ans << endl; return 0; } else { int cnt = 0; for(int j = 0; j < la; j++) { if(a[j] != b[j]) ++cnt; } cout << cnt << endl; } return 0; }
数组变换
分析
对于每个数一直除2,然后最后check是否相等即可。
参考code
#include <bits/stdc++.h> using namespace std; int a[55]; int main() { int n; cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; string res = "YES"; for(int i = 0; i < n; i++) { while(!(a[i] & 1)) a[i] >>= 1; } for(int i = 1; i < n; i++) { if(a[i] != a[0]) res = "NO"; } cout << res << endl; }
排序子序列
分析
考虑序列A_1, A_2, . . . , A_i是一个单调的序列.显然如果对于j < i把序列分为A_1, A_2. . . A_j 和 A_j+1, A_j+2, . . . , A_i 两个部分不会使问题变得更优.
于是我们可以贪心的去重复下面过程:
1、 从序列中找出最长的单调连续子序列
2、 删除找出的最长的单调连续子序列
这里的单调序列包括非递增和非递减,而判断子序列是否单调的时候,注意处理等于的情况。
参考code
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector <int> A; int ans = 1; for(int i = 0; i < n; ++i) { int x; cin >> x; if(A.size() <= 1) A.push_back(x); else { if(A[0] <= A.back() && A.back() <= x) A.push_back(x); else if(A[0] >= A.back() && A.back() >= x) A.push_back(x); else { ans++; A.clear(); A.push_back(x); } } } cout << ans << endl; return 0; }
组队竞赛
分析
对于所有参赛队员,我们把他们的水平值进行逆序排序,然后逐一挨着安排每个队伍,然后计算出队伍水平值总和,即为所求。对于a1 >= a_2 >= a_3... >= a{3N}, 我们可以容易观察出答案就是a2 + a_4 + a_6 +...+ a{2N}
参考code
#include <bits/stdc++.h> using namespace std; const int maxn = 300100; int a[maxn]; int main() { int n; scanf("%d", &n); for(int i = 0; i < 3 * n; i++) scanf("%d", &a[i]); sort(a, a + 3 * n); long long ans = 0; for(int i = 0; i < n; i++) ans += a[n + 2 * i]; printf("%lld\n", ans); return 0; }
训练部队
分析
可以考虑把新兵分为两种类型。
一种战斗型(战斗值大于潜力值的),一种潜力型(相当于打了他可以获得潜力值),对潜力型的新兵进行战斗力值排序。
然后一种情况是潜力型中战斗值最高的牛牛去打完剩余的潜力型,因为战斗力值会越大越多,另一种情况考虑打完所有潜力型获得值是固定的,那么在攻击型中找一个能打完所有的潜力型的牛牛,并且战斗力值和潜力值要最大。
实现就是用的前缀和和二分
参考code
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 100005; int n; int goodn,badn; LL sum[maxn],MAX[maxn]; struct Node { LL x,y; Node() {} Node (const LL &_x,const LL &_y) { x=_x; y=_y; } bool operator < (const Node &t) const { if(x ^ t.x) return x < t.x; return y < t.y; } }good[maxn],bad[maxn]; int search(int L, int R, LL x) { while(L < R) { int mid = (L + R + 1) >> 1; if(MAX[mid] < x) L = mid; else R = mid - 1; } return L; } LL solve() { LL ans = 0; ans = max(ans, sum[search(0, goodn - 1, good[goodn].x)] + good[goodn].x + good[goodn].y); for(int i = 1; i <= badn; i++) { int pos = search(0, goodn, bad[i].x); ans = max(ans, sum[pos] + bad[i].x + bad[i].y); } return ans; } int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) { LL x, y; scanf("%lld%lld",&x, &y); if(x < y) good[++goodn] = Node(x,y); else bad[++badn] = Node(x,y); } sort(good + 1, good + goodn + 1); MAX[0] = 0; sum[0] = 0; for(int i = 1; i <= goodn; i++) { sum[i] = sum[i-1] + good[i].y - good[i].x; MAX[i] = max(MAX[i-1], good[i].x - sum[i-1]); } LL ans = solve(); printf("%lld\n", ans); return 0; }
牛牛的数列
分析
正着枚举记录一下当前位置的连续上升子序列长度,倒着也做一遍。
最后枚举一个连接点即可。
参考code
#include <bits/stdc++.h> using namespace std; const int maxn = 100000 + 5; const int INF = 0x3f3f3f3f; int a[maxn], n; int pre[maxn], suf[maxn]; int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", a + i); a[0] = INF, a[n + 1] = INF; for(int i = 1; i <= n; i++) pre[i] = a[i - 1] < a[i] ? pre[i - 1] + 1 : 1; for(int i = n; i >= 1; i--) suf[i] = a[i] < a[i + 1] ? suf[i + 1] + 1 : 1; int ans = 1; for(int i = 1; i <= n; i++) { ans = max(ans, pre[i - 1] + 1); ans = max(ans, suf[i + 1] + 1); if(a[i + 1] - a[i - 1] >= 2) ans = max(ans, pre[i - 1] + suf[i + 1] + 1); } printf("%d\n", ans); return 0; }#Java工程师##C++工程师##iOS工程师##安卓工程师##运维工程师##前端工程师##算法工程师#