【Atcoder】AGC017 C-F简要题解

*C.Snuke and Spells

排序后又zz地想到一个假算法，然而正解是转化为线段覆盖。

拆成 n n n个点（标号为 0 − ( n − 1 ) 0-(n-1) 0−(n−1)），若权为 x x x的球有 k k k个，它能覆盖 ( x − k ) − x (x-k)-x (x−k)−x之间的线段。

0   n 0~n 0 n全部被覆盖时不需要修改，若没有全部覆盖，未被覆盖的线段数就是至少要修改的次数。

D.Game on Tree

Hackenbush删边

sg函数转移： S G ( i ) = x o r ( S G ( s o n ) + 1 ) SG(i)=xor(SG(son)+1) SG(i)=xor(SG(son)+1)

正确性：从链的情况外推一下

*E.Jigsaw

很妙的图论转化题。

发现 H ≤ 200 H\leq 200 H≤200且一侧高为k的实心可以和另一侧高位k的空心相接，那么可以拆出 2 H 2H 2H个点(标号 ( − H ) − H (-H)-H (−H)−H)表示相接。

设左侧高为 k k k的实心或右侧高位 k k k的空心是标号为 − k −k −k的点。

设左侧高为k的空心或右侧高位k的实心是标号为 k k k的点。

把每块积木看做是一条有向边，于是问题转化为能否找到若干条路径 ( S → T ) (S→T) (S→T)，使得 S &lt; 0 , T &gt; 0 S&lt;0,T&gt;0 S<0,T>0。

那么要满足条件：

• 对 于 i &gt; 0 , i n [ i ] &lt; = o u t [ i ] 对于i&gt;0,in[i]&lt;=out[i] 对于i>0,in[i]<=out[i]
• 对 于 i &lt; 0 , i n [ i ] &gt; = o u t [ i ] 对于i&lt;0,in[i]&gt;=out[i] 对于i<0,in[i]>=out[i]
• 对于一个弱联通分量，必须有一个点满足 i n [ i ] ≠ o u t [ i ] in[i]≠out[i] in[i]̸​=out[i]

*F.Zigzag

考虑将 L i L_i Li​表示为一个长为 n − 1 n-1 n−1的01串。

发现 L i + 1 L_{i+1} Li+1​要横向大于 L i L_i Li​必然是某位 1 1 1前移或者某位0转成了1：

设 d p [ i ] [ j ] [ s ] dp[i][j][s] dp[i][j][s]表示处理到 L i L_i Li​，前 j j j位与 s s s相同的方案数( s s s表示 L i − 1 L_{i-1} Li−1​，是动态变化的)

具体看这份题解吧