Codeforces Round #560 (Div. 3)ABCDEF1F2

今天下午总算把好久之前没打的div3开了一场vp，补掉了，全暴力，除了自己读题傻逼以外没什么好说的，，

A

Remainder

standard input/output

1 s, 256 MB  x3717B

Polycarp Training

standard input/output

2 s, 256 MB  x4380C

Good String

standard input/output

1 s, 256 MB  x2792D

Almost All Divisors

standard input/output

2 s, 256 MB  x1395E

Two Arrays and Sum of Functions

standard input/output

2 s, 256 MB  x794F1

Microtransactions (easy version)

standard input/output

2 s, 256 MB  x179F2

Microtransactions (hard version)

standard input/output

3 s, 256 MB  x176

 

A：给出n，x，y，以及n长度的str（01串），可以01相互改变，问你最少多少次操作使得 str % 10^y = 10^x  瞎搞记录一下就可以

int main() { int x,y; while(cin >> n >> x >> y){ string str; cin >> str; int ans = 0,cnt = 0; for(int i = str.size() - 1;i >= 0;i--){ if(cnt == y){ if(str[i] == '0') str[i] = '1',ans++; break; } if(str[i] == '1') ans++,str[i] = '0'; cnt++; } cnt = 0; for(int i = str.size() - 1;i >= 0;i--){ if(cnt == y) ; else{ if(cnt == x) break; else if(str[i] == '1') ans++; } cnt++; } wt(ans); } return 0; }

B：第i天可以解决i个问题，如果第i天剩下的问题都没有大于i的，就停止训练了，贪心排序判断一下

for(int i = 1;i <= n;i++) cin >> a[i]; sort(a + 1,a + 1 + n); ll ans = 0; for(int i = 1;i <= n;i++){ ans++; if(ans > a[i]){ while(i + 1 <= n && ans > a[i + 1]){ i++; } i++; if(ans > a[i]){ ans--;break; } } } cout << ans << endl; } return 0;

C：判断好的字符串，给了good的定义，直接算

D：给了一些数的所有的因子，除了1和本身，问你存不存在这个数，并且输出最小的

拿最小的和最大的乘积去check这些因子的个数就可以，因为所有的都在里面，那a[1]*a[n]肯定就是这个乘积了。注意判断所有数是否整除他们，并且因子个数相同

int main() { int t; ios::sync_with_stdio(false); cin >> t; while(t--){ cin >> n; for(int i = 1;i <= n;i++) cin >> a[i]; sort(a + 1,a + 1 + n); ll num = a[1] * a[n]; set<int>s; for(ll i = 2;i * i <= num;i++){ if(num % i == 0) s.insert(i),s.insert(num / i); } // cout << s.size() << endl; if(s.size() != n){ wt(-1); continue; }else{ for(int i = 1; i<= n;i++){ if(num % a[i] != 0){ wt(-1); goto kkk; } } } wt(num); kkk:; } return 0; }

E：求题上的那个公式，水题+1，

1 * 5       5 2 * (4 + 4) 8 3 * (3 + 3 + 3) 9 4 * (2 + 2 + 2 + 2) 8 5 * (1 + 1 + 1 + 1 + 1) 5 1 1 1 2 1 3 1 4 1 5

2 2 2 3 2 4 2 5

3 3 3 4 3 5

4 4 4 5

5 5

你会发现，每个数的贡献很容易可以得到，就是(n - i + 1) * i * a[i]，上面的数是不变的，那么可以先乘上，然后一起排序就完了，算贡献就可以了，注意取模，细节

int main() { while(cin >> n){ for(int i = 1;i <= n;i++) cin >> a[i]; for(int i = 1;i <= n;i++) cin >> b[i]; for(ll i = 1;i <= n;i++){ a[i] *= ((n - i + 1) * i); } sort(a + 1,a + 1 + n); sort(b + 1,b + 1 + n,greater<int>());ll ans = 0; for(int i = 1;i <= n;i++){ // cout << a[i] << " " << b[i] << endl; ans += (a[i] % 998244353ll) * (b[i] % 998244353); ans %= 998244353ll; } wt(ans); } return 0; }

F1,F2 n个东西，对于每个东西，你都需要a[i]个，原价2金币，每天你可以获得1金币，并且他有m个优惠，优惠的那天是1金币，问你最少多少天就可以买完所有的东西

会了F1的写法，很快就二分改出F2的了 

int vis[200024]; int id[200024],m; P p[maxn]; bool check(ll x){ MS1(vis); for(int i = 1;i <= m;i++){ if(p[i].fi <= x) vis[p[i].se] = max(vis[p[i].se],p[i].fi); } // for(int i = 1;i <= x;i++){ // cout << vis[i] << " " ; // } // cout << endl; vector<vector<int> > off(200011); for(int i = 1;i <= n;i++){ if(vis[i] != -1) off[vis[i]].pb(i); } for(int i = 1;i <= n;i++) b[i] = a[i]; int num = 0; for(int i = 1;i <= x;i++){ num++; if(i > 200000){ num += (x - i);break; } for(auto d:off[i]){ if(num >= b[d]){ num -= b[d];b[d] = 0; }else{ b[d] -= num; num = 0; break; } } } int sum = 0; for(int i = 1; i <= n;i++){ sum += b[i]; } if(sum * 2 <= num) return true; return false; } int main() { ios::sync_with_stdio(false); while(cin >> n >> m){ for(int i = 1;i <= n;i++) cin >> a[i]; for(int i = 1;i <= m;i++){ int x,y; cin >> p[i].fi >> p[i].se; } ll ans = 1; ll l = 1,r = 400000; while(l <= r){ int mid = (l + r) / 2; if(check(mid)){ ans = mid ; r = mid - 1; }else l = mid + 1; } wt(ans); // cout << "dasda" << endl; } return 0; }