AtCoder CODE FESTIVAL 2017 qual C

发现能力还是差一些，依然需要努力，加油。

综述#

总共6道题，前四道相当简单，后两道没法下手，最后做出4题。检查代码的时候不太认真，爆了几发，下次应该多注意。

题意和题解#

A. Can you get AC?#

给个字符串，查是否有子串 "AC"。

B. Similar Arrays#

定义两数组“相似”，当且仅当对应位置元素的绝对差小于1。给个数组求多少种数组和它相似，并且那些数组元素的积为偶数。

（我……因为 $N$ 太小了，当场直接交搜索……）

会发现直接算还是有点困难。逆向考虑，若数组元素的积为奇数，那就意味着其中不存在偶数元素；这个计数还是很容易的，根据原数组每一位的奇偶可以看这一位置能取得元素的种类，乘起来。答案就是相似的数组的总数 $3^N$，再减去乘积为奇数情况的数目。

C. Inserting ‘x’#

给个字符串，让通过最少次数的插入 'x' 的操作把它整成一个回文串。

考虑让首尾两元素一致，在两端都插 x 没什么意义，如果两端一开始不同、且都不为 x，那无论怎么操作，字符串都不会成为回文串了；如果有一个是 x，那可以在另一头插个 x，让首尾先相同，这样首尾就不用再考虑了，删掉。把这样的若干次操作放到一起，相当于搞掉两头的 x，搞掉两头相同的字符，再往复这么搞。相当于把所有 x 都删掉，然后判断现在的字符串是不是回文的，“不是”就没法操作成回文的；“是”的话就考虑字符间的空隙，在每对对称位置上插 x，让字符串变成回文的。显然，每对对称的空隙所需的最少的操作次数，即是两个空隙内原有的 x 数目的绝对差。这样就得到了所需的最少的操作数。

D. Yet Another Palindrome Partitioning (dp)#

给个字符串，让把字符串分成尽可能少的块，使得每块都是一个回文串的重排列。

回文串的重排列，那就是每种字符出现次数都为偶数，或者至多只有一种出现奇数次。因为都是小写字母，可以把26种字符出现奇偶次的状态存成整数；并且若维护这个状态的前缀和 $s_i$，就可以用异或方便地得到所有块的奇偶次状态。

记 ${dp}_i$ 为前缀 $1 \cdots i$ 的最少分块数目，$bc(x)$ 为 $x$ 的二进制的1的数目。很容易得到
$${dp}_i = \min\limits_{\substack{1 \le j < i \ bc(s_i \oplus s_j) \le 1}} + 1$$
对于每个 $i$，枚举 $b$，找所有的 $j: s_i \oplus s_j = b$，即找奇偶次状态等于 $s_i \oplus b$ 的 $dp_j$ 的最小值，开个 unordered_map，每次都存一下 $s_i$ 对应的最小的 $dp_i$ 就可以 $\mathcal{O}(\Sigma*)$ 时间内转移了。

E. National Property (sweep line)#

给个由 $1 \times 1 \times 1$ 的小立方体搭成的 $A \times B \times C$ 大长方体（$A, B, C$ 两两互质），平行于坐标轴放置，一个顶点在 $(0, 0, 0)$，对面的在 $(A, B, C)$，这两个顶点间穿一根线；给每个小立方体标记一个坐标，取其坐标分量最小的顶点为立方体的坐标，比如最靠近原点的那个记为 $(0, 0, 0)$；记两个立方体的坐标的切比雪夫距离（各坐标绝对差中最大的值）为两立方体距离。问有多少个立方体到最近的、被线穿过的立方体的距离小于或等于 $D$。

（比赛时读完题了，但是没有什么思路。）

一个重要的结论是，线在两个顶点间，只会经过小立方体的“面”，而不会经过棱、顶点。可以把线表示成参数方程，然后令某一维坐标值为整数，会发现另外两维在顶点间都不会成为整数；同样对每一维这样讨论，就能得到三个坐标值两两间不会同时为整数。这就证明了上述结论。由这个结论，便可以发现相邻的、被线穿过的小立方体的坐标间，都是某一维差个1，具体是哪一维取决于线是经过了小立方体的哪一面；这样把相邻的小立方体记为 $P_0(x_0 = 0, y_0 = 0, z_0 = 0), \cdots, P_{n-1}(x_{n-1} = A-1, y_{n-1} = B-1, z_{n-1} = C-1)$，因为 $P_{i}$ 和 $P_{i+1}$ 只有一维差了1，相当于走了一个曼哈顿路径，所以总共 $n = A+B+C-2$。

如果不考虑大长方体的限制，让空间充满小立方体，和 $P_0$ 切比雪夫距离小于或等于 $D$ 的所有小立方体，即符题的立方体，发现总数是 $(2D+1)^3$；如果按顺序增加 $P_i$，符题的立方体每次都会在某个方向上多一个高度为1的扁平的长方体，且是在 $P_{i-1}$ 往 $P_i$ 走的方向上，距离为 $D$ 处，增加的这些立方体，最符题立方体总数的贡献是 $(2D+1)^2$。如果单纯这么考虑，那么总共的符题立方体数就很容易得到了。

若加上长方体的限制，会发现只有靠近边界的、被线穿过的立方体的贡献容易有变化，靠近中心的被线穿过的立方体的贡献就不会变化了。我们把贡献会变的被线穿过的小立方体记为关键点，用三个坐标分量的和作为关键字排序，类似于扫描线来处理相邻两个关键点的贡献。

记相邻的两个关键点为 $P(x, y, z),, Q(x+\delta x, y+\delta y, z+\delta z)$，在 $P,Q$ 间的所有被线穿过的立方体，在同一个方向上增长的那一些对答案的贡献是一样的。记三个方向上对答案的贡献分别为 $F_x, F_y, F_z$，则包括 $P$ 不包括 $Q$ 间的所有被线穿过立方体的总贡献是 $F_x \delta x + F_y \delta y + F_z \delta z$。

再深入思考，在 $P_{i-1}$ 转到 $P_i$ 过程中，若 $P_{i-1}$ 是在 $u \in {x, y, z}$ 方向上增加的贡献，而 $P_{i-1}$ 的 $u$ 方向上的分量小于 $D$，或者大于或等于 $A - D - 1$，则立方体 $P_{i-1}$ 必是一个关键点。这样，枚举三个方向上坐标有变化的、且离两个边界距离不超过 $D$ 的立方体，就可以找到所有的关键点。显然，这些关键点的总数是 $\mathcal{O}(D)$ 的。这样便能在 $\mathcal{O}(D\log{D})$ 时间内得到符题的立方体数目了。

F. Three Gluttons (dp)#

UPDATED on 2017-11-08

现在有 $N=3n$ 个寿司，有三个人 A, B, C，各自有个寿司的喜好顺序列表 $a_i, b_i, c_i$，三个列表都是 $1$ 到 $N$ 的排列。每一次，设是第 $t$ 次，三个人会按着喜好顺序从左到右，找现在还存在的寿司编号 $a_t, b_t, c_t$，然后同一个寿司最多被一个人选择的情况下，会吃掉这三个寿司，然后继续进行同样的步骤，直到吃完所有的寿司。题目则是给出 A 和 B 的喜好列表，在不出现选择的寿司有冲突的情况下，C 的喜好列表有多少种方案。

先只考虑如何计算被 C 吃的寿司的序列 $x_1, \cdots, x_n$ 的种类数。假设我们已经有了 A, B 吃的寿司的序列 $a_{u_i}$, $b_{v_i}$，对于每个 $t$，肯定有 $a_{u_t}$ 不在 $(b_1, b_2, \cdots, b_{v_t})$ 中，对于 $b_{v_i}$ 也不在 $(a_1, a_2, \cdots, a_{u_t})$ 中；而 $x_t$ 只要不在 $(a_1, a_2, \cdots, a_{u_t})$ 和 $(b_1, b_2, \cdots, b_{v_t})$ 中就没问题。但为了防止出现重复的 $x_i$，对于某个特定的 $t$ 可行的 $x_t$ 还需要考虑后面 A, B, C 各自吃的。记这样的 $x_t$ 可以取
$$f(u_t, v_t, t) = N - \left[3 (n - t) + \left|\left\{a_1, a_2, \cdots, a_{u_t}, b_1, b_2, \cdots, b_{v_t}\right\}\right|\right]$$
所以，已有 A, B 的寿司序列时，$x_i$ 的序列数是 $\prod_{t}{f(u_t, v_t, t)}$。

我们用 DP 来计算总的这些合法的序列的贡献，设 ${dp}_{i, j, k}$ 表示 $u_k \le i$, $v_k \le j$ 时，$x_1, \cdots, x_k$ 的总序列数目。显然小一点的 $i$ 和 $j$ 都是在这个答案里的，所以答案至少有 ${dp}_{i - 1, j, k} + {dp}_{i, j - 1, k} - {dp}_{i - 1, j - 1, k}$ 的贡献（相当于维护一个矩阵和）。如果 $a_i$ 没有出现在 $(b_1, \cdots, b_j)$ 中，并且 $b_j$ 也没出现在 $(a_1, \cdots, a_i)$ 中，那么可以让 $a_{u_k}=a_i$, $b_{v_k}=b_j$，然后从一些 $x_1, x_2, \cdots, x_{k-1}$ 中转移过来，即满足这种情况下的答案还有 $f(a_i, b_j, k) * {dp}_{i - 1, j - 1, k - 1}$ 的贡献。

所以总的，$x_t$ 的合法序列有：
$${dp}_{i, j, k} = {dp}_{i - 1, j, k} + {dp}_{i, j - 1, k} - {dp}_{i - 1, j - 1, k} + \begin{cases}f(a_i, b_j, k) * {dp}_{i - 1, j - 1, k - 1}, &, a_i, b_j \text{均第一次出现} \\ 0, &,\text{else}\end{cases}$$

而对于从 $x_t$ 向 C 的喜好序列 $c_i$ 转移时，会发现和具体的 $a_i, b_i$ 没关系，因为假设 $p_{i,j}$ 为已知 $x_t$，且已经吃了 $j$ 次、C 已经发现喜好序列的前 $i$ 个都被吃过了的情况的 $c_1, \cdots, c_i$ 种类数。对于寿司编号 $c_i$，如果 $c_i$ 不是 $x_t$ 中的寿司，则这里只能取前面自己没吃过，且是 A, B 前 $j$ 次吃过的寿司（不然 C 会抢在 A, B 之前吃掉 $c_i$，那 $c_i$ 应当在 $x_t$ 中）；如果 $c_i$ 是 $x_t$ 中的寿司，那这一位置就只有这一种选择。所以：
$$p_{i, j} = p_{i - 1, j} (3j - i) + p_{i - 1, j - 1}$$
和 $a_i, b_i$ 甚至 $x_t$ 的具体值都无关。

所以最终答案是 ${dp}_{N, N, n} * p_{N, n}$（查了表，实际 $p_{N, n}$ 就是 A052502）。

时间复杂度 $\mathcal{O}{(N^3)}$