Codeforces Round 889

發表於 更新於 分類於 ， Disqus： 文章字數： 208 所需閱讀時間 ≈ 1 分鐘
B(bitset)C()D()E()F()

https://codeforces.com/contest/1854

B - Earn or Unlock

想了半天,bitset就过了??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

卧槽 200000^2/64 = 6'2500'0000.0 也能跑进3秒的吗?

https://codeforces.com/contest/1854/submission/216347777

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for(ll i=(a);i<(ll)(n);i++)
#define per(i,a,n) for(ll i=(n);i-->(ll)(a);)
ll read(){ll r;scanf("%lld",&r);return r;}
ll a[200010];
ll sa[200010];
int main(){
  int n = read();
  rep(i,1,n+1) a[i]=read();
  int OFF=n;
  ll ans = a[1];
  rep(i,1,n+OFF+1) sa[i] = sa[i-1] + a[i];
  bitset<200010> ok; // [1,n]
  ok[1] = 1;
  rep(i,1,n+OFF+1) {
    if(ok[i]) ans = max(ans, sa[i]-(i-1));
    ok |= (ok << a[i]);
    ok[i] = 0;
  }
  printf("%lld\n",ans);
  return 0;
}

总结

B

常数优化完全不会, n*bitset(n/64) n = 2e5可以跑进3秒!?

有人rust的也是bitset, https://codeforces.com/contest/1854/submission/216290617

pypy: https://codeforces.com/contest/1854/submission/216353273

C

参考

官方题解