2023.11 ~ 我明白太放不开你的爱 太熟悉你的关怀 分不开

1. LOJ 6502 「雅礼集训 2018 Day4」Divide

从大到小排序，那么能与 \(w_i\)，产生贡献的一定是一个前缀。但是还不够，因为这个前缀可能 \(<i\)，所以还是要对每个前缀记录 \(|A|\)。如果让这个产生贡献的前缀要不然是 \(i\) 要不然是 \(0\) 就可以只记当前的 \(|A|\) 了。也就是对于每个 \(w_i\)，在其前面的 \(w_j\) 要不然全部 \(w_i+w_j\geq m\) 要不然全部 \(w_i+w_j<m\)。归纳构造，当 \(w\) 从小到大排序之后 \(w_1+w_n\geq m\)，那么 \(w_n\) 可以直接放到最后，要不然 \(w_1\) 放到最后。这样重排之后就可以 \(\mathcal{O}(n^2)\) dp 了。

2. P5419 [CTSC2016] 单调上升序列

给出了最长的单调上升路径的下界是 \(\frac{2m}{n}=(n-1)\)。尝试将其构造出来。关键是发现如果两个相邻的权值，不是相邻边，那么这两个权值一定不会出现在同一个单调上升路径上。更近一步地，如果权值在 \([l,r]\) 里的边均两两不相邻，那么一条单调上升路径至多出现一个权值在 \([l,r]\) 内的边。现在想要尽可能搞出多的两两不相邻边，也就是完美匹配。将所以 \(\frac{n(n-1)}{2}\) 条边划分为 \((n-1)\) 组完美匹配即可。构造见这里，利用 \(n-1\) 边形去构造，连出边来旋转 \((n-1)\) 次得到所有的合法图形。

3. IMO 1997 p4

solution

增加一问 \((c)\)：对所有存在解的 \(n\) 给出 \(n\times n\) 的合法矩阵的构造。

\((a)\)：考虑一个数 \(x\) 出现在主对角上会满足 \(1\) 个十字，未出现在主对角线上会满足 \(2\) 个十字，它需要满足 \(n\) 个十字，由于 \(n\) 为奇数那么它至少要在主对角线上出现一次，所以 \(2n-1\leq n\Rightarrow n\leq 1\)。

\((b)\)：若存在 \(n\times n\) 且主对角线均为 \(1\) 的合法矩阵 \(A_n\)，可构造出合法的 \(A_{2n}\)：\(A_{2n}=\begin{bmatrix} A_n & B_n\\ C_n & A_n \end{bmatrix}\)，其中 \(B_n\) 是 \(A_n\) 中每个数加 \(2n\) 得到，\(C_n\) 是 \(B_n\) 的主对角线由 \(2n+1\) 改为 \(2n\) 后的结果。\(A_1\) 显然有解，从而所有 \(A_{2^k}\) 均有解。

\((c)\)：\(2n\) 个点的无向完全图必定存在 \((n-1)\) 组不交的最大匹配，对于第 \(i\) 组最大匹配中的边 \((x,y),x<y\)，令 \(A_{x,y}=i,A_{y,x}=i+n\)，最后令主对角线 \(A_{i,i}=n\) 即得到合法构造。

4. P6276 P6276 [USACO20OPEN] Exercise P

对于所有质数次幂 \(t=p^k\)，计算 \(t\mid \operatorname{lcm}\) 的方案数，再将 \(p^{cnt}\) 乘起来得到答案。反过来计算 \(t\nmid \operatorname{lcm}\) 的方案数。现在一个置换环的 egf 是 \(\sum_{i\geq 0} \frac{x^i}{i}-\sum_{i\geq 0} [i\bmod t=0]\frac{x^i}{i}=-\ln(1-x)+\ln(1-x^t)/t\)，再 \(\exp\) 得到置换的方案数是 \(\frac{(1-x)^{1/t}}{1-x}\)，那么 \(t\nmid \operatorname{lcm}\) 的方案数就是 \(n![x^n]\frac{(1-x^t)^{1/t}}{1-x}\)。

\(\frac{1}{1-x}\) 相当于作前缀和，而分子只有 \(t\) 的倍数处有值。所以 \(n\) 可以直接减去模 \(t\) 多的那部分来化简，令 \(k=\lfloor\frac{n}{t}\rfloor\)，则有 \([x^{kt}]\frac{(1-x^t)^{1/t}}{1-x}=[x^{kt}]\frac{(1-x^t)^{1/t}}{1-x^t}=[x^{kt}](1-x^t)^{1/t-1}=(-1)^k\binom{1/t-1}{k}\)。

现在要计算 \(n!(-1)^k\binom{1/t-1}{k}\)，注意它是放指数上的要对 \((\bmod -1)\) 取模所以需要手动展开一下，注意 \(p^k\) 的倒数和是 \(\mathcal{O}(n\log\log n)\) 级别的，所以这里我们接受 \(\mathcal{O}(k)\) 相关的复杂度。化简得 \(\frac{n!(t-1)(2t-1)\cdots(kt-1)}{k!t^k}\)，考虑计算 \(\frac{n!}{k!t^k}\)，\(k!t^k\) 实际上就是 \(t(2t)(3t)(4t)\cdots (kt)\)，于是这个式子相当于 \(1,2,\cdots ,n\) 的 \((k+1)\) 个区间乘积。为了保证 \(\mathcal{O}(n\log\log n)\) 的复杂度，实现 Sqrt Tree 即可。（代码偷懒了写的猫树 呜呜呜 Sqrt Tree 看上去好难写啊）

Code

5. ccpc 2023 桂林 E Prefix Mahjong

考虑怎么 check，那就是按值域 \(f_{0/1/2,0/1/2,0/1}\) 表示前前位置开头有几个顺子，前一个位置开头有几个顺子，是否已经有雀头。转移是一个矩阵乘法，那么直接在值域上线段树维护矩阵乘法。因为是 01 矩阵所以可以压位，然后值域可以离散化到 1e5，这样复杂度就是 \(\mathcal{O}(n k^2\log n)\)，其中 \(k=18\)。

Code

6. ccpc 2023 桂林 I Barkley II

计算 cnt-mex 最大的区间。枚举 mex 是 \(x\)，计算删去 mex 之后剩余的若干区间 cnt 最大是多少。这里虽然不能保证 mex 是 \(x\)，首先答案一定能被统计到，其次算错的话真实 mex \(<x\)，只会更劣，所以这么做是对的。

Code

7. ccpc 2023 桂林 H Sweet Sugar

一个连通块合法当且仅当 \(\sum\geq k\) 且与 \(k\) 同奇偶。和这个题一样证，\(w\) 合法那么 \(w-2\) 一定合法。所以贪心一下就行了。

Code

8. ccpc 2023 桂林 C Master of Both IV

枚举 xor \(=x\)，考虑它的真因子一定 \(\geq x/2\)，无论怎么异或都搞不出 \(x\) 的最高位，所以一定有奇数个 \(x\)，从而 \(x\) 的真因子 xor 和为 0。xor 为 0 的个数即为不在线性基里的元素个数，注意去重以及统计 \(x=0\) 的情况。

Code

9. UOJ76 懒癌

对于一个得病人的开枪时间是，假装自己没有病，所有情况中，最迟的开枪时间再 +1。它看到的该咋病就咋病，它没看到的就需要枚举。在所有情况中取 dp 值最大的再 +1 即为自己的 dp 值。转移出现环那么环上的所有状态 dp 值均为 inf（永远不会开枪）

如果 \(x\) 看不到 \(y\) 那么 \(x\to y\)，在这张图上考虑，得病的染成黑色，每次相当于将一个黑点染黑，再将后继中的若干点变色。答案就是最终所有点都是白色时，最大的《曾经是黑色》的点数。此时发现如果一个 \(>1\) 个点的 SCC 被染黑其中一个那么永远不会开枪，否则就是后继节点个数。所以只有不能被 \(>1\) 个点的 SCC 到达的点才能是黑色。

这时就能看出来对于某种染色方案，答案是所有能被黑点到达的点的个数。先将合法点求出来，再对每个合法点求出它能被多少合法点到达，答案的统计就很简单了。

时间复杂度 \(\mathcal{O}(n^3/w)\) 传递闭包。

Code

10. ccpc 2023 桂林 B The Game

从小到大排序之后，应当是 \(A\) 的后 \(m\) 个对应到 \(B\) 的后 \(m\) 个，记录 \(A\) 的后 \(m\) 个的总大小 \(sa\)，\(B\) 的后 \(m\) 个的总大小 \(sb\)，以及 \(A\) 比 \(B\) 多出来的数的个数 \(res\)。\(sb-sa=res\) 那么可以直接对应从小到大将 \(A\) 中的数依次修正为 \(B\)，删的一定是前面 \(res\) 个。否则我们需要浪费次数，贪心，需要浪费时去操作 \(A\) 的最小值。

用俩 multiset 实现了一个对顶堆一样的玩意维护前 \(m\) 大。时间复杂度 \(\mathcal{O}(n\log n)\)。

Code

11. P5330 [SNOI2019] 数论

\(\operatorname{lcm}\) 为循环的整段直接算，只考虑最后那个散段咋算。首先按 \(\bmod \gcd(P,Q)\) 分类转化到 \(P\perp Q\) 的情况，考虑 \(0,P,2P,\cdots (Q-1)P\) 在 \(\bmod Q\) 意义下是一个环，不重不漏取遍 \([0,Q)\)，并且每次询问的是这个环的某一段有多少个 1，对这个环作一个前缀和就行。

Code

12. P5331 [SNOI2019] 通信

先想到费用流，尝试建模：

• \(S\) 到 \(i\) 连 \((1,0)\)：追踪这个流的流向来确定 \(i\) 作为何种方式贡献答案；
• \(i\) 到 \(T\) 连 \((1,W)\)：直接取。
• \(i\) 到 \(j'\) 连 \((1,|a_i-a_j|)\) 其中 \(j<i\)：连接到前一个哨站。
• \(j'\) 到 \(T\) 连 \((1,0)\) 限制至多和后面一个哨站连接。

这里的问题是 \(i\to j'\) 的边数在 \(n^2\) 级别，尝试优化建边，这种左侧和右侧相连的形式可以联想到 cdq 分治。于是分治的时候变成右半部分向左半部分连边，对每个值单独建点，相邻的值连边 \((+\infty,|\Delta|)\)，就能将这部分边优化到 \(\mathcal{O}(n\log n)\) 条了。

Code

13. P5372 [SNOI2019] 积木

初始图 \(G_s\) 与最终图 \(G_t\) 的对称差 \(G\) 一定是若干环加上一条链，并且这条链是以 \(G_s\) 中的空格出发，走到 \(G_t\) 中的空格。需要找到这样的路径满足：

• 在 \(G_s\) 中走过的边的状态是 1010101010....10（一条边走过之后 0,1 互换）
• \(G\) 中的 1 边被走奇数次，0 被走偶数次

首先先走完那条链归约到只有环的情况。然后从空格处开始 dfs，每次 dfs 尝试走上下左右的积木，然后根据这个积木的形态再走到下一个格子（也就是一次 dfs 走两步），已经走到过的点打个标记以后不要再重新走。如果当前走到了一个环内就绕一圈回来把这个环修正（注意这一步修正环不要打标记）。

先将网格图黑白染色，每走两步空格只能走到同色点。只需证明 dfs 的过程中空格空格走偶数步能走遍所有的同色点即可。这样就能保证每个环都能被遍历到，从而所有环都可以被修正好。

assert 一下发现没问题那它就是对的 只需讨论出一个点能够走到它所有曼哈顿距离为 2 的点就行，不想讨论可以直接搜一下 5*5 的所有情况程序验证？所以还真是 assert 一下是对的它就是对的。

Code

14. XX Open Cup gp of Zhejiang F

这么妙？trick：假设点的编号是 \(0\sim n-1\)，将 \((2i,2i+1)\) 再连一条边，《原图的匹配》和《新图中若干环,链和单点》，是一个双射。将 \((2i,2i+1)\) 绑定之后，对每个集合 \(S\) dp 出 \(w[S]\) 表示 \(S\) 中连成一条链/环的权值和。链可以 dp \(f_{S,i}\) 表示 \(S\) 集合内以 \(i\) 号点为终点的链的权值和。环的话钦定 \(S\) 中最小的点作为起点，那么就是需要 dp \(g_{S,i}\)，其定义与 \(f\) 不同的就是起点一定是 \(S\) 中最小的点。求出 \(w\) 之后可以集合幂级数 exp 这样总复杂度就是 \(\mathcal{O}(2^{n/2}n^2)\)，当然后面直接 \(\mathcal{O}(3^n)\) 也是能行的。

Code