T & P 推免机考能找到的练习题 AC 代码汇总
Here's something encrypted, password is required to continue reading.
Read more退役老狗的 codeforces 摸鱼记。准备做做 Educational Round，一场做个五六题，试图维护一下捉襟见肘的代码能力，同时也拯救一下跌破下限的智商。
注意到当 \( i \) 大于 \(30\) 时，产生的效果与 \(i\) 从 \(1\) 开始相同，所以原串是有循环节的。
结论：最多使用两个 * 。
做法：
* : \(a\) 和 \(b\) 相同。* : 答案是 x* 或是 *x 的形式，只需要考虑 \(a\) 和 \(b\) 的首字母或是尾字母是否相同。* : 答案是 *xy* 的形式，如果答案是 x*y* 或是 *x*y 的形式，则可以等价替换为 x* 或 *y ，同理，使用 3 个或以上 * 一定不优。只需要考虑 \(a\) 和 \(b\) 中是否有两个连续字母相同。眼瞎了，没看到取模。
首先做这个最大\(size\) ，很好做，直接将 \(l\) 不断乘 \(2\) 直到超过 \(r\) 就可以得到最大的 \(size\) ，记为 \(n\) 。
然后考虑方案数，首先枚举一个集合中最小的数 \(x\) ，那么需要满足 \(l \leq x, x\prod_{i = 1}^{n}d_i \leq r, \forall d_i \geq 2\)，所有 \(d_i\) 的取法就是方案数。
可以设计递推计算这个方案数，设 \(f(x, n)\) 表示集合中最小的数为 \(1\)、当前集合中最大的数是 \(x\) 、集合大小为 \(n\) 的方案数，转移比较简单，那么此题答案就是：
\[ \sum{x = l}^{r}\sum{i = 1}^{\lfloor \frac{r}{i} \rfloor} f(i, n) = \sum_{x = l}^{r} g(\lfloor \frac{r}{x} \rfloor, n)\]
上式中，\(g(\ , n)\) 是 \(f(\ , n)\) 的前缀和。
整除分块，时间似乎刚刚好。
Tutorial 里面似乎有数学方法可以直接把这个方案数算出来。
贪心。
可以将题目中的操作看做将所有 \(a_i - x\) ，然后选择 \(k\) 个位置 \(+ 2x\) 。
套路地将区间和拆成前缀和相减的形式，考虑枚举右端点对于答案的可能贡献。接下来按照 \(x\) 的正负讨论，如果 \(x > 0\) ，那么希望尽可能将 \(k\) 个位置放在区间内，否则尽可能放在区间外。
需要把一点点细节全部都写对，老年人为了复习线段树没有选择更快的做法。
写半天没写出来，最后抄的题解，qaq。
还是看 Tutorial 吧。🥹
可能需要注意的是，当 multiset 为空的时候，*s.begin() 似乎是未定义行为，会返回一个奇妙的东西？
把两个序列拼在一起，中间切一刀，两边各自满足条件即可，暴力可过。
考虑选择所有包含 \(k\) 的区间 \(l, r\) 。
所有不包含 \(k\) 的区间一定不优，而加入一个包含 \(k\) 的区间不会使 ideal 的点集变大，所以全部加入之后判断 \(k\) 是否满足 ideal 即可。暴力可过。
对于每一个 \(a_i\) 在 \(b[i: n]\) 的区间上二分找到最后一个吃完的位置 \(p\) ，然后通过差分统计答案，\([i: p - 1]\) 的区间上每一个答案增加 \(b_j\) ，\(ans_p\) 增加剩下的价值。
时间复杂度 \(O(n\log n)\)。
因为所有 \(w_i \geq 0\) ，所以价值的代数和最大等价于扔掉最少的边。
一个三角形的三个顶点只有两种涂色方法：
因此，答案中有一个因子为 \(\binom{\frac{n}{3}}{\frac{n}{6}}\) ，上面是三角形数量，选出一半的三角形赋给两蓝一红的颜色，剩下的赋给两红一蓝的颜色。
然后对于每个三角形的边权 \(a \leq b \leq c\) 分类讨论即可，考虑到所有的三角形涂色方案独立，答案为所有因子的乘积。
一个很贴近真实算法的题，比较喜欢。
考虑对于每一个 \(h_i\) 使用操作 2 能够解决全部所需的最小操作 1 的数量，很显然 \(i\) 这个位置是不应用操作 1 的，所以可以只考虑 \(i\) 的每一个前缀和后缀，方法类似。
维护一个单增的单调队列，当遇到 \(h_i\) 时：
细节有一、、多
时间复杂度 \(O(n)\) 。
二分答案，考虑如何检验，令 1 为根，每一个黑点都尽可能向下（更深处）移动，如果无法往下移动，则向上移动到父亲尝试检验。移动到根或两个及以上黑点交汇则失败。
时间复杂度 \(O(n\log n)\) 。
按照 \(n\) 和 \(k\) 的奇偶性分类讨论：
好题，不要把算法题当成数学题来做。
先考虑只有一维的做法，一个直观的想法是先将 \(m\) 增大到 \(\sqrt{a}\) 左右，然后再走约 \(\sqrt{a}\) 步，这样最少。
但是在两维的情况下，这个想法并不一定成立，参考 \(a = 8, b = 4\) 这组样例解释，一个较大的 \(m\) 可能会对于上面这个最小的性质带来一些破坏。
考虑当 \(m\) 不超过 \(M\) 时所需的最少步数，答案为 \(M + \lceil \frac{a}{M} \rceil + \lceil \frac{b}{M} \rceil \) ，对于那些多出来的部分，只需要在 \(m\) 还没增大到 \(M\) 的时候先走即可。
结合最开始的观察，发现当 \(M\) 很大的时候是无意义的，而 \(M\) 应该 \(< \max(\sqrt{a}, \sqrt{b})\) 。
先考虑只有一个 \(a\) 的情况，很显然是把 \(r\) 逆序排序，直接按顺序构造最小，证明可以参考排序不等式。
那么如果有两个数组可以构造，只需要把 \([s_1, 2s_1, \ldots, ns_1, s_2, 2s_2, \ldots, ns_2]\) 排序，然后取前 \(n\) 项即可。
发现答案具有单调性，即如果改变 \(x\) 个 \(d_i\) 能做到，那么改变更多个 \(d_i\) 也一定能做到。
于是可以二分，这边考虑二分的是最多的不改变 \(d_i\) 的数量。原因是：设 \(p’\) 表示 \(p\) 从小到大排序的结果，那么不改变的这些点一定是 \(p’\) 中的一段连续区间。
现在问题变成了有了一段连续区间 \(p’[l: r]\) ，如何检验外面的这些点改变 \(d_i\) 之后能不能满足极差 \(\geq k\) 的条件，可以把区间外的这些点分成两类：
可以枚举这些点的左边的值，同时记录他们对应的右边的值，按照从小到大的顺序枚举这些点放在左边的值，每当端点右移时，相当于要把这个点放在右边，这时只需要维护延伸出的右端点最大值即可。
我认为，最后一步这个算法还是有一定的价值的，并不是完全套路。
时间复杂度可能是 \(O(n^2\log^2 n)\) ，但是不怎么满。
有点没意思，搞了半天就是动态 dp 。
结论是：一定可以把这个链条划分成若干个 \(2\) 个相邻点和 \(3\) 个相邻点的集合。
证明可以分为两步：
分析到了这里，dp 呼之欲出，设 \(f(i, 0 / 1)\) 表示到 \(i\) 这个点，选 / 不选 \(i\) 这个点的最小价值和，初值为
\[f(1, 0) = 0, f(1, 1) = \infty \]
有转移，
\[f(i, 1) = \min(f(i - 1, 0), f(i - 1, 1)) + a_{i - 1}\]
\[f(i, 0) = f(i - 1, 1)\]
套上动态 dp 那一套理论，先重新定义矩阵乘法：
\[C = A \cdot B, c(i, j) = \min(\sum_{k = 1}^{n}a(i, k) + b(k, j))\]
然后把转移写成矩阵乘法的形式，寄了 hexo 为什么连矩阵乘法都打不出来，看来还需要再调教一下这个博客。qaq
最后用线段树维护矩阵即可。
接下来准备结合 THU 的机考题，对于目前的训练情况做一些调整。
22 年“形式语言与自动机”课程中的部分作业整理，以我喜欢做错 / 不会做的证明题为主。
Prove or disprove the following statement:
考虑边界情况，如 \(L(\emptyset) = \emptyset\) ，它没有真子集。
以下结论都是正确的：
举一个反例，设 \( \Sigma = \lbrace 0, 1 \rbrace, A = \lbrace 0^n1^n \mid n \in \mathbb{N} \rbrace, B = L(0^{*}1^{*}) - A \) ，\( A \) 很显然不是正则语言，而 \( L \) 很显然是正则语言，关键在于证明 \( B \) 不是正则语言。
此处可以利用 正则语言在交（差）操作下的封闭性 ，由 \( A \cup B = L \) （其实是 \(B = L - A\)）知，若 \( B \) 正则，因为 \( L \) 正则，则 \( A \) 为正则语言，与 \( A \) 非正则的性质矛盾，因此可得 \( B \) 非正则。
作业中并没有想到这一点，尝试利用了正则语言的泵引理，觉得有一点问题，但助教判定为正确，记录如下：
正则语言的泵引理
反证，假设 \( B \) 为正则语言，则有 \( B \) 对应的泵引理常数 \( n \) ，设 \( s \in B \) ，且 \( s \) 有一段长度为 \(n\) 的 \(0\) 前缀，即 \( s = 0^nw\) ，依然将 \(s\) 表示为 \(xyz\) 的形式，可设 \( y = 0^m(m > 0)\) ，则 \( xyyz = 0^{n + m}w \) ，构造 \( w = 1^{n + m} \) ，即可推出 \( xyyz \notin B\) 。
这个证明与一般的利用泵引理证明某个语言不属于正则语言的过程的最大的不同就是 \(s\) 除前缀之外的 \(w\) 部分是最后“拼凑”上去的。但从另一个角度来讲，哪怕是对于 \(0^n\) ，也足以应用泵引理，也就是说 \(m\) 的大小确定，所以在这里姑且认为 \(w\) 是确定存在且能被确定构造出来的 。
解析里给了一个巧妙的构造：设 \( A = \lbrace 0^m1^n \mid m \geq n, m, n \in \mathbb{N} \rbrace, B = \lbrace 0^m1^n \mid m \leq n, m, n \in \mathbb{N} \rbrace, A \cup B = L(0^{*}1^{*})\) 。
考虑 \( \Sigma = \lbrace 0, 1, a, b \rbrace, A = \lbrace 0^n1^n \mid n \in \mathbb{N} \rbrace, C = \lbrace 0^m1^n \mid m, n \in \mathbb{N} \rbrace , B = \lbrace 0^m1^na^pb^p \mid m, n, p \in \mathbb{N} \rbrace \) ，很显然 \( A \subseteq C \subseteq B \) ，\( A \) 不是正则语言，\( C \) 是正则语言，关键在于证明 \( B \) 不是正则语言（看上去就不是正则语言 qaq ）。
比较简便的做法是利用正则语言在同态下的封闭性，设同态函数 \(h, h(0) = \epsilon, h(1) = \epsilon, h(a) = 0, h(b) = 1\) ，则 \(h(B) = A\) （虽然在这里不重要但是这个写法对吗？），若 \( B \) 正则，则 \( A \) 必定正则，矛盾。所以 \(B\) 不是正则语言。
根据提示，考虑使用泵引理，可在 \( L \) 中任取 \(w (|w| \geq n)\) ，设 \(w = xyz\) ，由 \( xy^iz \in B \) 可以猜测出将两部分串按照 \(i\) 奇偶性分类。
在作业中，我取了 \( L_1 = \lbrace xy^{2i}z \mid i \in \mathbb{N}, i \geq 1 \rbrace \) ，又对称地取了 \( L_2 = \lbrace xy^{2i + 1}z \mid i \in \mathbb{N} \rbrace \)，这里应该是没想清楚，因为 \( L_1 \cup L_2 \neq L \) 。
事实上，只需取 \( L_1 = \lbrace xy^{2i}z \mid i \in \mathbb{N} \rbrace \) ，然后取 \(L_2 = L - L_1\) 即可。由正则语言在集合差操作下的封闭性可知，若能证明 \(L_1\) 是正则语言，则 \(L_2\) 也是正则语言。在作业中，我只是感觉 \(L_1\) 是正则语言非常显然，并没有证明，这里应当需要补充一个简单的证明。事实上可以使用正则表达式，\( L_1 = L(x(yy)*z) \) 。
现在可以回过头来看看 1. 中最后提出的那个问题：对于正则语言 \(L\) ，若 \(|L| > 1\) ，则能否为 \(L\) 找到一个正则真子集？
按照 \(L\) 是有限还是无限集讨论：
所以搞了半天似乎 Bonus 是没有加分的，意思是你做了题目自己获得了提升。笑死了，不过 Bonus 应该就没有做出来过。
这道题的核心思想是利用 \(L\) 对应的 DFA 构造 \(\epsilon\)NFA，具体的细节以后有机会再详细写吧。
犯的一个错误是 2. 不能利用 1. 的结论（属于是初高中数学思维定式了），一个错解是这样的：
看上去很对，但是问题出在最后一步，正则语言在有限交下封闭，但是在无限交下不一定封闭，考虑一个反例：
For any contest-free language \(L\) and any regular language \(R\), answer each of the following statements True or False. If your answer is True, give an explanation. If your answer is False, give a counterexample.
\(L - R = L \cap \overline{R}\) 。这里的 \(\overline{R}\) 其实是针对语言的全集 \(\Sigma^{*}\) 来说的，全集是一个正则语言，由正则语言在差操作下的封闭性知 \(\overline{R}\) 也是一个正则语言；又由上下文无关语言与正则语言在交操作下的封闭性知 \(L \cap \overline{R}\) 也是一个上下文无关语言。
相似地，\( R - L = R \cap \overline{L}\) 。但上下文无关语言在集合差操作下不封闭，即 \(\overline{L}\) 不一定是上下文无关语言。这里需要一个反例。考虑构造一个 \(L(a^nb^nc^n)\) 的典型的非上下文无关语言，可设 \(R = L(a^{*}b^{*}c^{*}), L = \lbrace a^ib^jc^k \mid i \neq j \lor j \neq k \rbrace\) ，关键在于证明 \(L\) 是上下文无关语言。
可以将 \(L\) 拆解为 \(L_1 \cup L_2\) ，其中 \(L_1 = \lbrace a^ib^jc^k \mid i \neq j \rbrace, L_2 = \lbrace a^ib^jc^k \mid j \neq k \rbrace \)，由上下文无关语言在并操作下的封闭性可知 \(L\) 也是上下文无关语言。
有一个典型的错解是构造 \(L\) 和 \(R\) 的并行 PDA（PDA in parallel），然后标记 \(L\) 和 \(R\) 对应的结束状态，如在 1. 中将 \([p, q] (p \in F(L), q \notin F(R))\) 标记为接受状态。这样的做法在 1. 中是没问题的，但是在 2. 中不成立。
对于确定性的自动机，将所有的接受状态和非接受状态取反，得到的新自动机接受原语言的补集，但是这一点对于非确定性的自动机是不成立的。反例似乎遍地都是，比如我随手写了一个 \(L(ab^{*} + c^{*})\)。所以 \(\overline{L}\) 的自动机不能很好地构造出来。
Chomsky 范式
对于 \(L\) 的一个满足 Chomsky 范式的 CFG \(G = (V, T, P, S)\) ，构造一个新的 CFG \(G’ = (V’, T, P’, S’)\) 使 \(L(G’) = S(G)\)。
对于 \(G’\) ，从 \(S’\) 开始推导，\(A’\) 会忽略前缀，而 \(A\) 则会保留所有的后缀，因此 \(L(G’)\) 中含有 \(L\) 中所有的后缀。
可以将状态 \(Q\) 复制两份 \(Q_0, Q_1\) ，其中 \(Q_0\) 的所有转移都使用 \(\epsilon\)，用来忽略前缀 ，而 \(Q_1\) 的所有转移都保持不变，用来忽略后缀。\(Q_0\) 和 \(Q_1\) 的栈上的转移保持不变。并在 \(Q_0\) 和 \(Q_1\) 之间对应的节点使用 \(\epsilon\) 边连起来，表示从忽略前缀到处理后缀的过程。
这个新的 PDA 其实是一个分层图，只能从 \(Q_0\) 所在的层“向上”走到 \(Q_1\) 所在的层，同时能够保留所有的栈状态以确保能够顺利接受。因此新 PDA 可以接受 \(S(L)\) 。
构造反例，设 \(L = \lbrace a^{3n}b^{n}c^{m}d^{m} \mid m, n \in \mathbb{N} \rbrace\) ，考虑 \(L’ = H(L) \cap R\) ，其中 \(R = L(b^{+}c^{*}d^{*})\) ，则 \(L’ = \lbrace b^{p}c^{m}d^{m} \mid 0 < p \leq m \rbrace\) 。
因为 \(L\) 是由两个上下文无关语言连接而成的，所以 \(L\) 也是上下文无关语言。在 \(L’\) 中 \(0 < p \leq m\) 的限制中，\(0 < p\) 来源于 \(b^{+}\) ，而 \(p \leq m\) 则是来源于正则表达式中不包含 \(a\) 的要求，若 \(p > m\) ，则 \(H(L)\) 中一定包含 \(a\) ，与 \(R\) 交完之后不可能出现这种串。
那么这个 \(L’\) 里面有两个限制，看上去就不是上下文无关语言，又根据上下文无关语言和正则语言的交是上下文无关语言，若 \(H(L)\) 是上下文无关语言，则 \(H(L) \cap R\) 也一定是上下文无关语言。若能证明 \(L’\) 不是上下文无关语言，则 \(H(L)\) 就不是上下文无关语言，反例构造成立。
可以使用上下文无关语言的泵引理很方便地证明。
上下文无关语言的泵引理
在做题的过程中，发现了一件比较有意思看上去也比较有用的事情，就是在泵引理的应用过程中，可以不妨设 \(|u| < n \)。因为若 \(|u| \geq n\) ，可以直接对 \(u\) （不断）应用泵引理直到 \(|u| < n\) 。
那么对于 \(L’\) ，可以直接取 \(z = b^{2n}c^{2n}d^{2n} = uvwxy \) ，不妨设 \(|u| < n\)，那么 \(v, x\) 都是一段 \(b\) ，设 \(|vx| = l\) ，取 \(k = n\)，则 \(uv^kwx^ky = b^{2n + ln}c^{2n}d^{2n} \notin L’\) ，因此 \(L’\) 不是上下文无关语言。