https://atcoder.jp/contests/abc315

G - Ai + Bj + Ck = X (1 <= i, j, k <= N)

给定a,b,c,x,n 找满足限制的方案数

n 1e6

a,b,c [1,1e9]

x 3e15

2s

1024mb

我的思路

显然 for i = 1..n, 剩余部分exgcd算一算

但是wa了17个点，感觉我的exgcd应该是overflow了

https://atcoder.jp/contests/abc314

Ex - Disk and Segments

二维平面上 n条线段 两两无交点

求最小半径的实心圆，使得和所有线段至少一个交点

n 100

坐标 [0,1000]

2s

1024mb

我的思路

显然计算几何

都知道 圆上3点 能确定圆

但 问题是 3点不一定是 线段的端点，还可能和线段相切

想法还是 O(N^3)选择线段

那还需要 O(N)做校验

而且 选线段以后 ，是相切还是端点，似乎可以延长做三角形？

3端点 -> 定圆

2端点+1相切？

1端点+2相切？

3相切 -> 延长的三角形内切圆

另一个想法是利用坐标[0,1000]很小

如果一个方案可行，那么该方案离最近的整数点距离不超过 $(1,1) =\sqrt{2}$ , 所以整点的圆的半径和最优解的半径差不超过$\sqrt{2}$ 所以整点圆的半径也整数，和最优解差距不超过$\sqrt{2} + 1$

1
2
3
4
5
6
7

for i in 0...1000:
    # 奇
	for j in 0...1000:
    # 偶
	for j in 1000...0:
		# 圆心在i,j 的最小整数距离，注意到圆心移动不超过1,所以半径变化不超过1
		O(n) 校验

这样的话是 1000*1000*100 感觉也不行

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

似乎就没了