https://atcoder.jp/contests/abc321

G - Electric Circuit

3种点

n个 part点

m个红点

m个蓝点

给定每个 颜色点连到一个part点

然后红点和蓝点的直接连线 需要单射且满射，那么有m!种

对于所有连法 求 Exp(连接后的连通块个数)

n 17

m 1e5

3s

1024mb

我的思路

n 很小想用bitmask

首先根据 n来整理，变成 有n个点，每个点有ri个红色，bi个蓝色

然后要把所有红蓝相连，求连通块的个数期望

1
2
3
4
5
6
7
8
9

f[mask] = mask内连成一个连通块 且无剩余蓝红的方案数
g[mask] = mask内无剩余蓝红的方案数
ans[s] = sum s的所有方案的连通块个数
ans[s] = for mask, mask 包含最小点
		f[mask] * ans[s-mask] 两边互不影响计算右边贡献
		+ f[mask] * g[mask] 计算左边贡献

g[mask] = sum红! , 满足sum红==sum蓝
f[mask] = g[mask] - sum f[submask]*g[mask-submask], submask包含mask中最小的

似乎就AC了

https://atcoder.jp/contests/abc320

G - Slot Strategy 2 (Hard)

n个只包含’0’-‘9’的长度m的字符串在旋转

对于一个时刻 最多停止一个字符串旋转，字符串展示字符s[i][t%m]

问 最少多少时刻 让所有字符串停止，且展示的字符一样， 或无方案

n 100

m 1e5

2s

1024mb

我的思路

注意到 只包含数字，而数字只有10个，所以可以指定数字比较方案优劣

那么对于给定数字以后，每个字符串将变成一个0/1 bool串，其中 true表示 对应位置是要指定的结果数字

有一点想搞可反悔的dp

首先如果每个字符串都有指定数字才有可能，这样就是依次来都是一个方案，只是可能不是最短时间

但实际上可以变成二分图

首先 左侧是 字符串id, 右侧是可以逐步增加点的的时刻, 只要有对应位置就建立一条边

这样如果有 ans = |n| 就是答案， 这样最坏的情况是 n*m个右侧点，也就是所有字符串都集中在一个循环时刻上了

这里可以优化一下 右侧增点的过程，把与左侧无连接的点直接预处理掉，变成 [offset,vector<int>left]

那么每次增加 至少增加一次连边，

想用hall定理，也就是什么时刻 左侧的任意点的右向连接数一定大于左侧点数， 这个量级的上限

因为每循环一轮，所有左侧点连的点个数 至少增1,所以 总边数不会超过n^2

似乎就没了， 然而TLE了2个点

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问题一定有解，那么原问题就有解，如果证明不了，那当无解时，并不能证明不能递归下降就是无解

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