Fliper(3)
将每个挡板拆成两个点（表示两面）并建图，即可求出所有环
建立一张新图，以每个环作为点，并额外建立一个点\(z\)表示不在环中
将每个挡板两点所在环连边，即对边染色使（除\(z\)外）每个点邻边满足限制
显然（除\(z\)外）每个点度数需为\(8\)的倍数，并对每个连通块求出欧拉回路
将欧拉回路上的边交替分类，除起点外，其余点的邻边均被平分
重复上述过程两次，下面仅需处理起点的问题：
-
若连通块包含\(z\)，以\(z\)作为起点即可
-
若连通块不包含\(z\)，由于所有点度数为\(4\)的倍数，总边数为偶数
换言之，两类边数相同，而其余点均被平分，因此起点也应被平分
时间复杂度为\(O(n)\)
建造摩天楼(3)
结论：有解的充要条件为黑格八连通
从后往前贪心，每次即删除满足以下条件且编号最大的黑格：
-
该次操作合法，即与白无界四连通块相邻（有公共边）
-
该次操作后仍有解，即剩余黑格仍八连通
取出其相邻（有公共点）的黑格，顺时针依次记为\(a_{0},a_{1},...,a_{k-1}\)
由于是平面图，即\(a_{i}\)和\(a_{(i+1)mod\ k}\)相邻（有公共点）或之间的白格所在四连通块有界
关于白格的四连通性，仅需以黑格相邻（有公共点）的白格为关键点考虑即可
在此基础上，每次删除会影响以下两类黑格重新判定：
- 与被删黑格相邻（有公共点）的黑格
- 某个白有界四连通块无界后，与该四连通块相邻（有公共边）的黑格
前者每次为\(O(1)\)，后者每个白格至多处理一次，均摊为\(O(n)\)
启发式合并维护白格连通块点集，用set维护可删除黑格编号，时间复杂度为\(O(n\log n)\)
Strange device(3)
记\(Q_{S,d}\)表示距离\(S\)中某一点\(\le d\)的点集（不包括\(x\)）
不妨以\(1\)为根建树（根节点深度为\(0\)），并将过程分为两步：
-
求出节点的深度
对深度分治，处理区间\([l,r]\)时，维护出深度\(\in [l,r],=l\)的点集\(S,T\)
记\(mid=\lfloor\frac{l+r}{2}\rfloor\)，查询\(Q_{T,mid-l}\)和\(Q_{T,mid-l+1}\)即可递归到\([l,mid]\)和\((mid,r]\)
同时，对于分治到的每一层，不相邻的两个区间查询互不干扰，可以并行
换言之，每层至多查询两次，区间长度\(\le 2\)时结束，查询次数为\(4(\lceil\log_{2}n\rceil-1)\)
-
求出节点的儿子集合
将节点按深度模\(3\)分类，显然每一类内部互不干扰
每一类中对节点分治，处理点集\(S\)时，维护出\(S\)内儿子集合的并集\(T\)
将\(S\)划分为\(S_{1}\cup S_{2}\)，查询\(Q_{S_{1},1}\)即可递归到\(S_{1}\)和\(S_{2}\)
由于互不干扰，每层可以一起并行，查询次数为\(3\lceil\log_{2}n\rceil\)
综上，总查询次数为\(7\lceil\log_{2}n\rceil-4\le 66\)
Friends(4)
参考这里
Full Tournament(4)
参考这里
Battleship: New Rules(4)
参考这里
Kitten’s Computer
咕咕咕
Be Careful(3)
记\(d_{k}\)为\(k\)的儿子个数，记\(l_{k}\)为其中叶子的个数
定义\(f_{k,i}\)表示\(k\)的权值为\(i\)的概率
定义\(g_{i,S}\)表示\(k\)权值\(\ge i\)的儿子恰构成集合\(S\)且其余儿子已覆盖\([0,i)\)的方案数
此时，转移有递推和容斥两种方式，分别即
\[\begin{cases}g_{i,S}\rightarrow g_{i+1,\complement_{S}T}\prod_{son\in T}f_{son,i}& (T\subseteq S,T\ne \empty) \\f_{k,i}=\sum_{S}g_{i,S}\prod_{son\in S}\sum_{i<j}f_{son,j}\end{cases} \]\[\begin{cases}g_{i,S}=\sum_{T\subseteq [0,i)}(-1)^{i-|T|}\prod_{son\not\in S}\sum_{j\in T}f_{son,j}\\f_{k,i}=\sum_{T\subseteq [0,i)}(-1)^{i-|T|}\prod_{son\in S}(\sum_{j\in T}f_{son,j}+\sum_{i<j}f_{son,j})\end{cases} \]结合两种做法，设置阈值\(K\)，并按以下方式处理：
- 容斥得到\(i\in [0,\min(d_{k},K)]\)时的\(f_{k,i}\)，时间复杂度为\(O(d_{k}2^{K})\)
- 当\(i>K\)时，\(g_{i,S}\)中的\(S\)必然满足\(\forall son\in S,d_{son}=0\)或\(d_{son}>K\)
- 前者两两无区别，可以仅存储个数
- 记后者有\(t_{k}\)个，容斥得到有意义的\(g_{K+1,S}\)，时间复杂度为\(O(l_{k}2^{K+t_{k}})\)
- 递推得到\(i\in (K,d_{k}]\)时的\(g_{i,S}\)，枚举\(T\)可以改为分别转移，时间复杂度为\(O(d_{k}l_{k}^{2}t_{k}2^{t_{k}})\)
瓶颈显然在于第\(2\)步，（对每个\(k\)）枚举求出\(K+t_{k}\)最小的\(K\)
记这个最小值为\(M\)，则\(t_{k}\ge M-K\)，进而
\[n>\sum d_{son}=\sum_{K\ge 0}t_{k}\ge \sum_{K\ge 0}\max(M-K,0)=\frac{M(M+1)}{2} \]换言之，有\(M\sim \sqrt{2n}\le 19\)，时间复杂度为\(O(n2^{M})\)
第\(3\)步中虽然看上去最坏是\(O(Mn^{3}2^{M})\)，但显然\(l_{k}\)跑不满
Colorful Doors
咕咕咕
标签：讨论,连通,授课,sum,黑格,son,ge,WC2023,复杂度 From： https://www.cnblogs.com/PYWBKTDA/p/17119441.html