离谱，这场又突破了过题数下限，NTU的预选赛就这么难，不愧是今年final拿牌的学校。
C. Perfect Cactus
tarjan。题意就是判断仙人掌中是否有大于$3$的奇环，tarjan跑出点双联通分量判断一下就行。
（题面巨长巨复杂，有用的就一句话）
D. String Repetition
AC自动机。又是瓜队绝活题，差点被爆杀，待补。
E. Identity Subset
很早就被开出来但是我们直到最后也没过，感觉是用牛逼性质降低复杂度的暴力，待补。
I. Road Reconstruction
网络流。首先这个数据范围，这个度数限制，这个最小代价，显然是费用流。
考虑图中的边一共有三类：
- 被反转，代价为$a_i$
- 被删除，代价为$b_i$
- 不操作，代价为$0$
显然，三类边的总和为$m$，考虑如何建图以用流量控制点的入度不大于$k$，
可以发现，三类边会给连接的点以不同方法改变入度，因此建图方法也出来了：
- 新建一个点$V$连向汇点，流量$inf$费用$0$，表示被删除的边。
- 对于每个边$i(u,v)$设置一个点$x_i$，从源点连一条流量$1$费用的边
- 向$u$点连一条流量$1$费用$a_i$的边，表示$i$被反转
- 向$V$点连一条流量$1$费用$b_i$的边，表示$i$被删除
- 向$v$点连一条流量$1$费用$0$的边，表示$i$不操作
- 从源点向每个$x_i$连一条流量$1$度数
- 对于每个表示原图中点的点向汇点连一条流量$k$费用$0$的边以控制入度
这样建出来的图其实很简单，从源点到汇点跑一遍MCMF，所需费用就是答案。
J. Hot Potato
状压dp。考虑用$f_{bit,i}$表示到达状态$bit$且在第$i$位时的概率，其中$bit$是压缩后的各点状态，$1$表示已经到达过了。
签到级别的dp，注意逆元要提前算出来不然会TLE。
（这题还是有点卡常的，可以换C++20(64 bits)交）
K. This is a Game
博弈，差分前缀和。通过打表or推状态能发现$SG_k(a_i)=\lfloor\log_{k}a_i\rfloor$，
【前置芝士：我们用$SG$函数来衡量一个公平博弈局面的状态，一个先手必败态的$SG$值为$0$，一个状态的$SG$值是它所有后继状态的$SG$值的$mex$，多个相互独立的游戏的$SG$值是这些游戏各自$SG$值的异或和】
因此，当且仅当存在一个$2\le k\le a_{min}$使得所有$SG_k(a_i)$异或和为$0$时，后手必胜。
由于$k$可能有$10^{15}$，显然不能枚举，所以反向考虑：
显然$SG(a_i)\le \log_210^{15}\le60$，因此对每个$a_i$，仅存在最多$60$个的$k$的取值区间使得$SG(a_i)$不同，也就是说，我们只需要枚举最多不到$60n$个$k$的取值然后判断所有区间是否为$0$。
显然当$O(60n^2)$还是会TLE，然后再反向考虑一下（！了转反）：
如果对上述的每一个区间异或上对应的$SG_k(a_i)$，最后只要判断是否存在一个点的值为$0$就行了：
先离散化，然后差分更新区间，最后前缀和，游戏结束。
【冷知识：不只是加法和异或，只要是有结合律（$(a?b)?c=a?b?c=a?(b?c)$）和逆元（对于任意的$a$，存在$b$使得$a?b=o$，$o$是运算的单位元）的运算$’?’$都可以使用差分前缀和，以及树状数组等。有兴趣的话可以去学学抽象代数相关知识】