https://atcoder.jp/contests/abc313

F - Flip Machines

n张卡，正面ai,背面bi，初始都是正面

m个机器，对应卡xj,yj，！！xj可能等于yj

如果一个机器启动 则1/2几率 翻转卡xj,否则翻转卡yj

启动机器的集合任意选择

问 所有的 启动机器的集合 的方案中 卡的和的期望值最大是多少

n 40

ai,bi [1,1e4]
m 1e5

2s

1024mb

我的思路

显然是个概率论的题

n 比较小，m中等，ai,bi中等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

卡 a1 a2 a3

m组
[1,2]
[1,3]

第一次翻转
b1 a2 a3
a1 b2 a3

第二次翻转
a1 a2 a3
b1 a2 b3
b1 b2 a3
a1 b2 b3

从频次的角度来看， 如果涉及到翻转，那么该位置的期望贡献就是 (a[i]+b[i])/2

如果不涉及翻转 那么期望贡献就是 a[i]

所以选取的集合 就算再多，也只和被激活的那些有关，和一个位置被选了几次无关

所以问题可以变为，基础 = sum ai,

di = (b[i]-a[i])/2

有一堆激活的pair可以任意选，

问 最大 di和为多少

把di 按照正(>=0),负(<0)分类

如果有 (+,+)的di pair则一定选， 如果有(-,-)一定不选

那么剩下的就是 (+,-)的

而这类如果 其中的+已经选了 则一定不选

所以变成了, 未被选的+,所有- 和很多(+,-)的问题

那么显然 至少一侧的个数 <= n/2 = 20

这就很像bitset了

如果 所有-的个数 <= n/2 那最简单, 就是贪心选掉所有(+,-)有-被选的正的里面的

如果 所有+的个数 <= n/2???

1
2
3
4

(a0 10,b0 -5)
(a1 10,b0 -5)
(a0 10,b1 -4) 对于 单个来说最小， 但是 上面都选b0 比 选两个b1,b2更优
(a1 10,b2 -4)

只能说 最终被选的 -的个数肯定 <= n/2, 因为每个(+,-) 最多选一次

n-正 个中 选 <=正的方案数？ 这有多大？

正=20时 2^20

正=19时 $2^{21}-\binom{21}{21}-\binom{21}{20}$

正=18时 $2^{22}-\binom{22}{22}-\binom{22}{21}-\binom{22}{20}-\binom{22}{19}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def binom(n,m):
    s = 1
    for i in range(1,m+1):
        s *= (n+1-i)
        s //= i
    return s

def f(pos):
    neg = 40 - pos
    r = 2**neg
    for i in range(pos+1,neg+1):
        r -= binom(neg,i)
    print(pos, r)

for i in range(1,21):
    f(i)

看输出 感觉 还是2s过不了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1 40  
2 742  
3 8474  
4 66712  
5 384168  
6 1676116  
7 5663890  
8 15033173  
9 31621024  
10 53009102  
11 71116846  
12 76717268  
13 67108864  
14 48412432  
15 29703676  
16 16241061  
17 8344056  
18 4192510  
19 2097130  
20 1048576

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

参考

官方题解

https://atcoder.jp/contests/abc312/tasks/abc312_h

Ex - snukesnuke

N个字符串s[i]

1
2
3
4
5
6
7
8

t = set<string>
for i := 1..n
	k_i = 1
	while s[i] * k_i in t:
		k_i++
	t.insert(s[i] * k_i)

求 所有 k_1..n

$\sum |S_i| \le 2\cdot 10^5$, 小写英文字母

2s

1024mb

我的思路

如果不同字符串之间互不影响，那么相同si的ki对应的值就是1,2,4,5,6,7…

那么问题就是如果不同的字符串之间有影响

$k_i\cdot s_i = k_j\cdot s_j, s_i \neq s_j$

若$k_i = 1$,也就是 $s_i$会是$s_j$的重复序列， 首先重复序列的长度一定是 $s_i$长度的因数，这样可以 额外$O(|s_i| log|s_i|)$ 的把所有处理成

$(s_i,repeat)$ 的形式

根据字符串的循环结的理论，显然 一个字符串有一个最小循环单位，且其它循环都是它的倍数

1
2
3
4
5
6
7
8
9

引理 简单证明
最小循环节   l0 [.....][.....]
非倍数循环结 l1 [.........]

可以得到 (长度l1中，起始长度l0循环平移相等) -> F(l1,l0)

而 F(a,b) 当 a%b!=0时 可以得到 -> F(b,a%b)

这就是 gcd的过程，是有限的，所以总可以得到更小的循环节，矛盾

若 $k_i,k_j$均不为1,且$gcd(k_i,k_j) = 1$,那么用到上面引理类似的

不失一般性，设 $|s_i| > |s_j|$

1
2
3
4
5

[s_i......][s_i......][s_i......][s_i......][s_i.....]
[s_j....][s_j....][s_j....][s_j....][s_j....][s_j....]
得到 $F(len(s_i), len(s_j))$ 

所以它们一定有更小的循环节

综上，首先把所有的字符串拆成最小循环节和repeat, 然后对所有 最小循环结做hash

似乎就没了

https://atcoder.jp/contests/abc311/tasks/abc311_h

Ex - Many Illumination Plans

N点，根为1，树

点有b[i],w[i],c[i]=0/1

Q(v) = $\max \sum b_i, i\in U$ ，其中U是，v的子树U, 任意多次 删除点 并将子点和父节点相连， 最终满足$\sum w_i \le X$ 且 所有边的端点的c不同

求$Q(1),Q(2),…,Q(N)$

n 200

$X \in [0,50000]$

$W_i \in [0,X]$

$B_i\in [0,10^{15}]$

3s

1024mb

我的思路

先考虑其中一次的问题求解,

也就是给定一个有 点b[i],w[i],c[i]=0/1的树

然后删除点，让sum b尽量大，且满足 颜色 和w和的条件

dp[v] = w->b 保留v, v以下的和为w, 能得到的最大b

根据限制 传递时 只和 w与v的颜色有关

这样的问题是，要转移的话，每个v需要的就是所有后继不同色的点，并且还要考虑 后继点的关系

改一改

dp[v][c] = map<> w->b v或以下对上颜色贡献为c 和为w, 能得到的最大b

这样就是3个分支

• 选择v，w[v] + dp[u][c[w]^1]的合并
• 不选择v，颜色=0 的 dp[u][0] 的合并
• 不选择y，颜色=1 的 dp[u][1] 的合并

状态数 $O(n X)$ ,但转移代价似乎有点大，可以启发式合并吗？

然后启发式合并的一点是 每次会有一个很大的状态是不变的，每次把新增的相对小的状态向大的状态里塞，而这里每次选择v的话，可能有一个大的偏移

而且如果w是1,2,4,8,这样的话，只需要16个,2^16=65536 就可以让状态是满的

一个想法是 能不能 强制 让 b随着w单调递增，这样即可以让状态是连续的，又可以保证非严格单调递增

用更小的w 对应更大的b 去覆盖了更大的b， 如果这样的到了答案，那么对应选择的w一定是大与等于 实际的w的，不会不合法？

那如果有最优方案，关心对应的同样的w，如果被其它覆盖了，那么b一定更大，且有对应的合法w方案

这样的话 每个 dp[v][c] = 一个非严格单调递增的数组w2b

需要合并n次? 如何高效的合并？ merge(A,B) = C, C[i] = max(A[j]+B[i-j],j=0..i)

单调递增也保证不了 变化程度

https://atcoder.jp/contests/abc310/tasks

Ex - Negative Cost

$h \in [1,10^{18}]$

p = 0

n个($[1,300]$) $c_i [-300,300]$,$d_i [1,10^9]$

每次可以 任选一个p(可重复选), 满足$p \ge c_i$, 然后 $p -= c_i$, $h -= d_i$

问最少多少次 让 $h \le 0$

3s

1024mb

我的思路

先预处理数据

sort pair{ci,di}

对于 $c_i \le c_j, d_i \ge d_j$, 舍去 {cj,dj}

因为首先单次ci代价越小,di越多越好

dp[i][t][p] = 前i个 操作t次, p的结束值 能消耗最大的h

dp[i][t+k][p-k*ci] = max dp[i-1][t][p]

显然空间都存不下

考虑预处理后的数据

排序后前部分的 -k*ci > 0