Atcoder Grand Contest 046

dp 专项练习场.

A - Takahashikun, The Strider

为了方便,可以先规定初始方向是 $x$ 正半轴,那么第 $i$ 步的移动的向量就是 $(\sin ix,\cos ix)$ .
那么就是要求方程 $\sum_{i=0}^{k-1} (\sin ix,\cos ix)=(0,0)$ 的最小正整数解 $k$ .

可以把式子化简后求解,也可以直接猜结论,甚至还可以 MMA 求解 .

code

B - Extension

设 $dp(i,j)$ 表示有多少种不同的 $i$ 行 $j$ 列的矩阵,直接转移有 $dp(i,j)=dp(i,j-1)\cdot i+dp(i-1,j)\cdot j$ .
这样转移,若某种情况能被 $(i,j-1),(i-1,j)$ 同时拓展出来,就会被重复计算,需要将这部分减掉.

不难发现它们必须满足第 $i$ 行恰有一个黑的,且第 $j$ 列恰有一个黑的,因为每次黑色是新增的,所以交点处不能为黑.
于是这些情况数就是 $dp(i-1,j-1)\cdot (i-1)\cdot (j-1)$ ,将它们减去即可.
code

C - Shift

老套路了,每次把一个 $1$ 放到一个 $0$ 前面去,可以看成是 $0$ 将 $1$ 分成了若干段,数列可以用每段的长度来表示,每次操作就是让后面某段长度减 $1$ ,让前面某段长度加 $1$ . $k$ 那么大显然是唬人的,最多 $|S|$ 次操作就足够了.

记所有的 $0$ 将串分为了 $m$ 个由 $1$ 构成的连续段,第 $i$ 段的长度为 $a_i$ ,此处开头结尾也算,长度为 $0$ 的也算.

记 $n=|S|$ ,设 $dp(i,j,k)$ 表示考虑了第 $i$ 到第 $m$ 个段,操作了 $j$ 次,留出了 $k$ 个 $1$ 可以加给前面的段的方案数.

转移时枚举当前这一段增加的长度或减少的长度,注意不能又用后面留出的 $1$ ,又往前面送 $1$ ,这样是亏操作数目的.

长度增加时可以用类似前缀和的做法优化,即每次只增加一个,这样转移是 $O(1)$ 的,这部分时间复杂度为 $O(n^3)$ ,而长度减少时显然最多减少 $a_i$ 个,这部分时间复杂度也为 $O(\sum a_i\cdot n^2)=O(n^3)$ .

code

D - Secret Passage

先考虑给定一个字符串 $T$ ,如何判断它能否被串 $S$ 经过若干次得到.

若它们的最后一个字符相同,则可以同时删掉最后一个字符,判断前面的能否操作出来,若最后一个字符不同,则必须要在某次操作中,在这个位置插入一个对应的字符.

设 $dp(i,j,k)$ 表示当前 $T$ 的长度为 $i$ ,需要插入 $j$ 个 $0$ , $k$ 个 $1$ 的方案数,转移时讨论最后一个字符能否匹配即可.

需要注意,最后求出的状态 $(i,j,k)​$ 并非全部合法,即并不是每个状态都对应着能生成出来的串 $T​$ ,需要满足仅对串 $S​$ 的前 $|S|-(i-j-k)​$ 位进行操作的情况下,能向后插入 $j​$ 个 $0​$ , $k​$ 个 $1​$ .

我们每次对 $S$ 操作时,可以将其中一个字符插到后面,也可以插到前 $|S|-(i-j-k)$ 位中,设 $f(i,j,k)$ 表示仅对 $S$ 的前 $i$ 个字符进行操作,向后插入了 $j$ 个 $0$ , $k$ 个 $1$ 时,最多还可以向前 $|S|-(i-j-k)$ 位插入的字符数.
转移就讨论是否用新插进来的字符,插入的字符是 $0$ 还是 $1​$ ,插入到前面还是后面,这样就可以判断状态是否合法了.

时间复杂度 $O(|S|^3)$ .

code

E - Permutation Cover

明天再说.

F - Forbidden Tournament

明天再说.