美团笔试8.17
- 1. 预处理每个数的最小质因子,若没有最小质因子则为质数输出本身,否则输出最小质因子。
#include <iostream> using namespace std; const int N = 2e5 + 10; int ans[N]; void solve() { for (int i = 3; i <= 1e5; i++) { for (int j = 3; j * j <= i; j++) { if (i % j == 0) { ans[i] = j; break; } } } } int main() { solve(); int t; cin >> t; while (t--) { int x; cin >> x; if (x & 1) { cout << (ans[x] ? ans[x] : x) << endl; } else { cout << 2 << endl; } } } // 64 位输出请用 printf("%lld")
- 2. 由于数组总和不变,要让极差最小,最后极差必然是1,最后有sum%n个x+1和n-(sum%n)个x,按大小顺序依次赋值即可。
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10; #define int long long int a[N]; signed main() { int s = 0; int n; cin >> n; map<int, int> mp; for (int i = 1; i <= n; i++) { cin >> a[i]; s += a[i]; mp[a[i]]++; } int val = s / n; int y = s % n; int x = n - y; // cout<<x<<" "<<y<<endl; sort(a + 1, a + 1 + n); int m1 = 0, m2 = 0; for (int i = 1; i <= n; i++) { if (i <= x) { if (a[i] >= val) m1 += a[i] - val; else m2 += val - a[i]; } else { if (a[i] >= val + 1) m1 += a[i] - val - 1; else m2 += val + 1 - a[i]; } } cout << min(m1, m2); }
- 重点是先手要怎么乘,使得后手不会占到便宜,后手肯定选子序列最小/最大的区间,这里太菜了没想明白,感觉是dp,求大佬解答
upd:问了大佬指点会做了,实习两个月整个人都变菜了
由于先手不会让后手占便宜,选的区间肯定不会让后手也能够拿来用更优,所以两个人选的区间没交集。先预处理pre_max[i]表示到i前缀的子序列最大值,pre_min[i]表示1-i前缀的子序列最小值,后缀同理,枚举先手选的区间[i,j],后手选的是[1,i-1]的最小/最大 和 [j+1,n]的最小/最大,两者取min/max 取最小或最大由k的正负性决定
upd 经过评论区大佬们指正 做法还是有问题 等一个题解
#实习##笔试##秋招##美团#