https://atcoder.jp/contests/abc319

F - Fighter Takahashi

根1,n点 树

非根节点, 2种类型， (si,gi) 或 ((gi) 最多10个)

1
2
3
4
5
6
7
8

初始 s=1 在根
   如果 首次 到点 (ei,si):
       if s < si:
           终止
       else:
          s += gi
   如果 首次 到点 (ei,gi):
          s *= gi

问 能不能经过所有 (si,gi)

n 500

si [1,1e9]

gi [1,1e9]

第二种类型最多10个

2s

1024mb

这不是手机广告里看到的游戏吗 哈哈哈哈哈哈哈

我的思路

这10个，和 n <= 500

我的感觉就是 bitmask乱搞一下？

dp[bitmask] = 恰好把bitmask的 (gi)类型点走完 的最大s

因为所有操作都是增长s的

所以一旦s > max(si)以后，就都可达了

那么对于 (s+w)*v和(s*v+w) 肯定先加会更好

所以步骤是

1. 当前bitmask,尽量+
2. 完成加以后走一次 (gi)

尽量+因为和当前s有关系，而办法就是所有可达点找最小的si,因为任何其它顺序的方案，对其 (可达性,si)排序，肯定有等价的 先最小可达si的方案，贪心就完了

那么问题来了，bitmask以后的方案似乎对应的点并不一致

因为在 尽量+的时候走过非bitmask的点

那么还剩下树的性质没有用，如何使用呢？

另一个想法就是 别bitmask了，直接 贪心+10! 吧，反正上面总结的是 每次尽量+，之后才走乘法

所以是

1. state => 贪心所有可用的+点全部用完
2. 那么现在剩余有若干个乘法点，这里直接分叉 暴力： $500\cdot 10!=1814400000$个方案

再一个就是两者结合，当达到bitmask且完成尽量+以后，记录s和对应的树状态

因为bitmask完成 和 + 以后，那么树上的不考虑s的 连通点是一样的，在一样的开放连通点情况下

“感觉上是” s越大越优，因为完成了 尽量+

所以 当前两个方案 如果不同 它们s如果相同，那么可达区域 <= s都可达 也就相同

如果它们 s不同，s更大的 可达区域也越大

所以就是 bfs + 贪心 + 优先队列 + bitmask?

直接过了

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 感觉也不行