https://atcoder.jp/contests/abc318

G - Typical Path Problem

n点,m边无向图

给定3点a,b,c，问是否存在从a到c经过b的简单路径

n 2e5

m 2e5

2s

1024mb

我的思路

找可以切割图的关键路径

按照关键路径切割图，合并

新图是树且树上所有边是原图的关键路径，在新树上找a到c简单路径

那么 就变成a-端点[关键路径]端点-...-端点[关键路径]端点-c

那么就是判断b 是否为其中的端点

或者相邻端点不同时，b属于对应连通块

然而ACx77,WAx16

https://atcoder.jp/contests/abc317

G - Rearranging

n x m 矩阵，一共含有 1..n 都有m个

n,m \in [1,100]

对于每一行，行内可以随意重排列

问是否有办法让每一列都是 1..n 各出现一次, 如果有给出方案

2s

1024mb

我的思路

第一直觉是一定有方法

想法是每次确定一列

每次找单行中出现次数最多的减去1,

然后 剩余行中未被选择的最多的减去1

如果这个方案是可行的，那么就能变成 列数规模减1的 同样子问题

所以需要证明 一定可行，或者找到反例

1
2
3
4
5

11144
22244
33345
55223
11553

是一个反例，这样会先选1,2,3 就无法选到4了, 但同时它也有方案

1
2
3
4
5

11144
24422
43335
52253
35511

另一个想法是 从值看，如果一个值占满了一行，那么这个值就不需要考虑如何分配了，变成行-=1的子问题

如果 一个值未占满一行，那么至少有2行有它

然后（一行，值）选不选，作为状态 似乎能构成2-sat问题

如果能证明这个2-sat问题一定有解，那么原问题就有解，如果证明不了，那当无解时，并不能证明不能递归下降就是无解

感觉需要智力来完成构造？但我没有智力

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