2025多校CSP模拟赛1
开 T1 水，开 T2 发现能乱搞，搞完发现是正确的。
开 T3 发现是熟悉的 dp，马上开写一个插板。
写了 2h 后发现占地面积不好算，放弃了。
T1 交友
发现只要特判类似
CG
GC
即可。
T2 炼金
因为环一定不优，所以出现环直接爆了，但是感觉写 \(dfs\) 很没有前途，于是选择递推模拟这样的过程。
具体的每次二分一个答案，然后进行很多轮，每轮遍历数组如果欠了金属就找两个儿子要。
容易发现如果 \(O(n)\) 轮后还是还不上，就说明出现了环，此时直接判凑不成。
那么复杂度是 \(O(Tn^2\log V)\)
T3 磁铁
发现肯定是先让所有磁铁紧密排列，然后求出剩下的空位进行插板法。
但是左右端点的磁力占地面积是不全的，不过根本没必要枚举左右端点，只需要将占地面积压入 \(dp\) 状态就好。
其次我们发现当一个磁铁需要放入两个磁铁之间时，需要将这两个磁铁分开，这样贡献不好算。
那么就可以枚举当前分为多少个连通块，这样每个联通块的左右端点的磁力就不用考虑了，此时如果从小到大枚举，占地面积的增加就极好算了。
设 \(dp_{i,j,k}\) 表示当前枚举到 \(i\) 分为 \(j\) 个连通块，占地面积 \(k\)。
第 \(i\) 个单开一个连通块：\(dp_{i,j,k}+=j\times dp_{i-1,j-1,k-1}\)
第 \(i\) 个合并两个连通块：\(dp_{i,j,k}+=j\times dp_{i-1,j+1,k-(2r_i-1)}\)
第 \(i\) 个放在一个连通块的左端或右端：\(dp_{i,j,k}+=2j\times dp_{i-1,j,k-r_i}\)
答案就是简单插板法，\(dp_{n,1,i}C^{l-i+n}_{n}\)。
复杂度 \(O(n^2l)\)
T4 铁轨
很好的欧拉回路题。
考虑可以将问题转化为加速不消耗代价，减速消耗代价。
那么因为要经过所有的铁轨，那么这些边一定经过。
此时如果将每个速度抽象成一个点，并且加入一个从 \(inf\) 连向 \(1\) 个边，这样就不用考虑起点终点，由路径变为回路。
因为向左经过一个点和向右经过一个点的数量一定要相同，那么就以此为代价在 \(i\) 和 \(i+1\) 间连边。
可是有可能连完后不连通，那么可以上一个最小生成树维护一下。