发现能力还是差一些，依然需要努力，加油。
综述#
总共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)}\)
评论