【题解】龟速更新的加训日记

vp 多一点还是有好处的。

计划将区域赛前的训练都写在这里。

与以往不同，这篇博客说是题解，实际上只会记录简要的解题思路，用于我日后进行回忆。

【8.21】NWERC 2023

H. Higher Arithmetic

将一个数拆分成若干正整数，要使得乘积最大，应当先尽可能多地拆成 \(3\)，再尽可能多地拆成 \(2\)。如果最后剩下 \(1\)，就把之前组合出的一个 \(3\) 拆掉，拼成两个 \(2\)。

注：实际上拆分成 \(e\) 最好，只不过 \(3\) 是最接近 \(e\) 的正整数，其次是 \(2\)。

回到这道题，\(\ge 3\) 的肯定直接乘起来，否则想办法凑出多的 \(3\)，其次凑出多的 \(2\)。

J. Jogging Tour

枚举 \(n\) 个点两两之间的 \(n^2\) 条边，最优策略中坐标轴肯定与其中一条边平行。

坐标轴旋转公式（逆时针旋转 \(\theta\)），原坐标 \((x,y)\)，新坐标 \((x',y')\)。 \[\begin{align}\pmatrix{x' \\ y'}=\pmatrix{\cos\theta & \sin\theta\\ -\sin\theta & \cos \theta}\pmatrix{x\\ y}\end{align}\]

之后跑最短哈密顿路径即可。

I. Isolated Island

比较蠢的方法是先建出平面图，再用最小左转法转成对偶图，再从无限面开始 bfs。

这当然是能做的，Link，\(O(n^2\log n)\)，缺点是一大坨。

注意到答案是 \(\texttt {No}\) 当且仅当对偶图是二分图。（相邻点到海边的距离最多相差 \(1\)，按到海边的距离的奇偶性建二分图，这个条件是充要的）二分图意味着没有奇环，因为 "奇 + 偶 = 奇"，如果对偶图有奇环，那么一定存在一个极小的奇环，环内的点度数为奇数。

于是判断输入的 \(n\) 条线段是否有某一个端点只出现了奇数次即可。

G. Galaxy Quest

设在第 \(i\) 条边上我们用了 \(x_i\) 秒来加速。如果我们知道最终走了哪些边，就能转化为线性规划问题 \[ \begin{align} &\min \ 2\sum x_i\\ &\sum x_i + \dfrac{d_i}{x_i}\le t \end{align} \] 拉格朗日乘数法，最终得到 \[ 2\sum x_i=t-\sqrt{t^2-4(\sum \sqrt{d_i})} \] 所以答案越小等同于让 \(\sum \sqrt{d_i}\) 越小。

给每条边赋权 \(\sqrt{d_i}\) 跑 dijkstra 即可，单次 \(O(1)\) 回答询问。

【8.25】2021 ICPC Jinan Regional

C. Optimal Strategy

先考虑所有数出现次数只有偶数的情况，如果一个人拿了最大的，另一个人必须跟着拿，因此可以两两配对。

从小到大考虑每个数，如果新加进一个数 \(x\)，导致 \(x\) 的出现次数变成奇数，先手肯定将 \(x\) 拿走一个，回到刚刚的情况。

对操作序列计数，设 \(f[i]\) 为当前最大的数为 \(i\) 的答案，用隔板法试图将 \(i\) 插进序列 \[ f[i]=f[i-1]\cdot \binom{cnt[i]/2+\sum_{j=1}^{i-1}cnt[j] }{cnt[i] / 2}\cdot cnt[i]! \] 最后乘阶乘表示分配这 \(cnt[i]\) 个 \(i\) 的次序。

L. Strange Series

\[ \begin{align} p&=\dfrac{S}{e}\\ &=\dfrac{1}{e}\sum_{m=0}^{\infty}\dfrac{\sum_{i=0}^{n}a_im^i}{m!}\\ &=\sum_{i=0}^{n}a_i\cdot \dfrac{1}{e}\sum_{m=0}^{\infty}\frac{m^i}{m!} \end{align} \] 令 \(T_i=\dfrac{1}{e}\sum\limits_{m=0}^{\infty}\dfrac{m^i}{m!}\)，我们要对 \(i\in [0,n]\) 求出 \(T_i\)。

对 \(T_i\) 建立 EGF，设 \(F(x)=\sum\limits_{i=0}^{\infty}T_i\dfrac{x^i}{i!}\)。那么 \[ \begin{align} F(x)&=\sum_{i=0}^{\infty}\left(\dfrac{1}{e}\sum_{m=0}^{\infty}\frac{m^i}{m!}\right)\dfrac{x^i}{i!}\\ &=\dfrac{1}{e}\sum_{m=0}^{\infty}\frac{1}{m!}\sum_{i=0}^{\infty}\dfrac{(mx)^i}{i!}\\ &=\dfrac{1}{e}\sum_{m=0}^{\infty}\dfrac{(e^x)^m}{m!}\\ &=e^{e^x-1} \end{align} \] 令 \(G(x)=e^x-1=\sum\limits_{i=1}^{\infty}\dfrac{x^i}{i!}\)。那么 \(T_i=i!\cdot [x^i]e^{G(x)}\)，多项式 \(\text{exp}\) 即可。

B. Monitored Area

对于一个多边形内的监控 \(O\)，以它为原点向多边形的每个顶点做射线，每条射线取极长的在多边形内的部分。极角序相邻的射线与多边形的一条边构成三角形，得到 \(n\) 个三角形，每个监控都这么做，再把所有三角形求并就是答案。

难点是如何正确识别三角形的顶点。我们对每一组极角序相邻的射线考虑，枚举多边形的每条边，对于一条边，如果某一条射线和它没有交点，就排除，否则设交点坐标分别为 \(A,B\)，只用判断线段 \(OA\) 和线段 \(OB\) 是否完全在多边形内部就行。

时间复杂度 \(O(n^4)\)。

M. Coloring Rectangles

每个矩形以其两条对角线为分隔，分出上下左右四个三角形。上和下恰好一个涂黑。左和有恰好一个涂黑，对应了题中的四种情况。用一个变量表示上黑还是下黑，另一个变量表示左黑还是右黑，一种染色情况就能用 \(2n\) 个二元变量来描述。两个三角形如果严格相交，就表示二者不能同时涂黑，2-SAT 即可。

因为要字典序最大，我们可以依次钦定每一个矩形是 \(3,2,1\) 或 \(0\)，最多跑 \(4n\) 遍 2-SAT，最终 \(O(n^3)\)。

两个三角形 \(A,B\) 严格相交（公共面积 \(>0\)），等价于

• \(A\) 中一条边和 \(B\) 中一条边在非三角形端点处规范相交。
• 或者，其中一个三角形的重心严格在另一个三角形内部。

A. Space Station

好难写，占坑。

【8.28】Ucup3-39. Tokyo

K. K-rep Array

数组可以是 \(K\)-rep 当且仅当不存在 \(i,j\) 使得 \(a_i\neq -1,a_j\neq -1,a_i\neq a_j\) 且 \(|i-j|\bmod K=0\)。

令 \(f_d=\sum\limits_{i-j=d}(a_i+1)(a_j+1)(a_i-a_j)^2\)，那么 \(K=i\) 时答案为 \(1\) 当且仅当 \(\forall j,\ i\mid j\)，\(f_j=0\)。

将 \(f_d\) 拆开，得到 \[ f_d=\sum_{i-j=d}a_i(a_i+1)\cdot (a_j+1)-2\sum_{i-j=d}a_i(a_i+1)\cdot a_j(a_j+1)+\sum_{i-j=d}(a_i+1)\cdot a_j(a_j+1) \] 每一项分别计算，将差卷积转化为和卷积后，用 NTT 求解。

差卷积化和卷积（0-index）： \[\sum_{i-j=d}f(i)g(j)=\sum_{i+(n-j-1)=d+n-1}f(i)g(j)\] 令 \(g_{\text{rev}}(i)=g(n-i-1)\)，化为 \(\sum\limits_{i+j=d+n-1}f(i)g_{\text{rev}}(j)\)。

L. LIS Triangle

如果 \(K=i\) 有解，那么 \(K>i\) 也有解，因为整体加一不影响构成三角形。

\(K=1\) 时无解，\(K=2\) 时一定有解，两种构造如下

\(L=N\) 时要特判。

N. Nice Bouquets

转化题意：找到最小的 \(c\)，通过对树 \(1\sim c\) 操作，使得在所有 \(k\) 天里，每一天三种颜色的花的数量（\(n_R,n_G,n_B\)）都满足 \(n_R\equiv n_G\equiv n_B\pmod {3}\)。

一棵树用长为 \(2k\) 的向量描述：第 \(2i\) 个值表示第 \(i\) 天这棵树对 \(n_R-n_G\pmod {3}\) 的贡献，第 \(2i+1\) 个值表示第 \(i\) 天这棵树对 \(n_G-n_b\pmod {3}\) 的贡献。如此得到 \(n\) 个长为 \(2k\) 的向量构成的向量组 \(\{v_i\}\)。

对第 \(i\) 棵树操作，默认状态 \(1\cdot v_i\)，砍掉即 \(0\cdot v_i\)，加速即 \(2\cdot v_i\)。令 \(V_{\text{init}}=\sum_{i=1}^{n}v_i\pmod{3}\)，目标是选取一组 \(\{a_i\}\) 使得 \[ V_{\text{init}}+\sum_{i=1}^{c} a_iv_i \equiv 0 \pmod{3} \ \ (a_i\in \{0,1,2\}) \] 即向量 \(-V_{\text{init}}\) 是否能被向量组 \(\{v_1,v_2,\ldots,v_c\}\) 线性表出，用线性基求解。

\(GF(3)\) 下的线性基：核心仍然是高斯消元。

基的每一维都是一个向量（当然也可以是三进制数）

GF(3) basis

struct Basis {
	int n;
	vector<vector<int>> p;
	Basis(int _n) : n(_n), p(n) {}
	void insert(vector<int> v) {
		for (int i = n - 1; i >= 0; i--) {
			if (v[i] == 0) {
				continue;
			}
			if (p[i].empty()) {
				p[i] = v;
				return ;
			}
			int fac = v[i] * p[i][i] % 3;
			for (int j = 0; j < n; j++) {
				v[j] = (v[j] - fac * p[i][j] % 3 + 3) % 3;
			}
		}
	}
	bool query(vector<int> v) {
		for (int i = n - 1; i >= 0; i--) {
			if (v[i] == 0) {
				continue;
			}
			if (p[i].empty()) {
				return false;
			}
			int fac = v[i] * p[i][i] % 3;
			for (int j = 0; j < n; j++) {
				v[j] = (v[j] - fac * p[i][j] % 3 + 3) % 3;
			}
		}
		return true;
	}
};

G. Guarding Plan

如果一个哨位已被监视，就可以删去。没被删的哨位构成一条随着 \(x\) 递增，\(y\) 递减的折线（红线），单调栈求出。我们再作出这些哨位的上凸壳（绿线），凸壳内的任意一点均能搞出一个哨位。

现在，你可以选择在绿线上新建若干点，覆盖掉红线上的一些点，让总点数变少。每段绿线分别考虑，\(dp(i)=(a,b)\) 表示这段绿线对应的红色折线上的前 \(i\) 个点至少能分成 \(a\) 段，且分成 \(a\) 段的前提下至少添加 \(b\) 个新点。

• 当前点选择保留：\(dp(i)=(a,b)\to dp(i+1)=(a+1,b)\)。
• 当前点选择被一个新点覆盖：\(dp(l-1)=(a,b)\to dp(r)=(a+1,b+1)\)。这需要凸包上的一个点完全覆盖 \([l,r]\) 这一段，也就是 \((x_r,y_l)\) 在凸包内。

dp 值是单调的，相同的 \(r\) 转移小的 \(l\) 更优，因此可以单调队列优化。

【8.30】CCPC 2023 Harbin

E. Revenge on My Boss

二分答案，设为 \(T\)。\(T\) 可行 \(\Leftrightarrow\) 重排三元组 \(\{a_i,b_i,c_i\}\) 使得 \(\forall m\in [1,n]\)，\((\sum\limits_{i=1}^{m} a_i+\sum\limits_{i=m}^{n}b_i)\cdot c_m \le T\)。

令 \(d_i=a_i-b_i\)，\(B=\sum\limits_{i=1}^{n}b_i\)，推一下式子，等价的条件是 \[ \sum\limits_{i=1}^{m-1} d_i\le T / c_m-B-a_m \] 不等号右侧均和放置顺序无关，记为 \(e_m\)。现在要重排 \(\{d_i,e_i\}\) 使得 \(\forall m\in [1,n]\)，\(\sum\limits_{i=1}^{m-1}d_i \le e_i\)。

最优策略下，显然先放置 \(d_i\le 0\) 的项，再放置 \(d_i>0\) 的项（其实并不显然，但可以感性理解？）。对于 \(d_i \le 0\) 的项，应当先放 \(e_i\) 较大的，让不等号右侧尽快增大，条件会更宽松；对于 \(d_i>0\) 的项，引入 \(D_i\) 表示 \(d_i\) 的前缀和，条件变成 \(D_i\le d_i+e_i\)，其中 \(d_i+e_i\) 可以看成天花板，我们要想不顶过天花板，策略应当是先放 \(d_i+e_i\) 较小的。

H. Energy Distribution

先忽略 \(e_i\ge 0\) 的条件，拉格朗日乘数法，\(\dfrac{\partial L}{\partial e_k}=0\Longrightarrow \sum\limits_{i\neq k} w_{ik}e_i=\lambda\)，是定值。

枚举子集 \(S\)，钦定子集内的 \(i\) 都满足 \(e_i >0\)，能列出 \(|S|-1\) 个方程，再加上 \(\sum e_i=1\)，就是 \(|S|\) 个，未知数也是 \(|S|\) 个，高斯消元，如果有负数解就舍去。答案对所有子集取 \(\max\)。时间复杂度 \(O(2^nn^3)\)。

C. Karshilov's Matching Problem II

拆贡献，式子可以写成 \(\sum\limits_{i=l}^{r}Sw[\min(r-i+1,z[i])]\)，其中 \(Sw\) 是 \(w\) 的前缀和，\(z[i]\) 是 \(\text{LCP}(T[i,n],S[1,n])\)，可以通过把 \(S\) 和 \(T\) 拼起来跑 Z 函数求得。

找到 \([l,r]\) 里最小的 \(mid\) 满足 \(T[mid,r]\) 是 \(S\) 的一个前缀。\(i<mid\) 的部分 \(\min\) 那项一定取到 \(z[i]\)，因此只用预处理 \(Sw[z[i]]\) 的前缀和；比较困难的是 \(i\ge mid\) 的部分，\(\min\) 那项仍旧有两个可能取值。换一个视角，我们可以对 \(S\) 的每个前缀 \(1\sim k\) 都预处理出 \(f(S[1,k])\)，这样两部分都能 \(O(1)\) 回答。具体的 \[ \begin{align} f(S[1,k])&=\sum_{i=1}^{k}\left(\sum_{S[i-j+1,i] \textbf{是 } S \textbf{ 的一个前缀}} w_j\right)\\ &=\sum_{i=1}^{k}\left(\sum_{j \textbf{ 在 fail 树上是 } i \textbf{ 的祖先} } w_j\right)\\ \end{align} \] 令 \(h[i]=\left(\sum_{j \textbf{ 在 fail 树上是 } i \textbf{ 的祖先} } w_j\right)\)，因为 \(i\) 的祖先集合 \(=\) \(\{i\}\ \cup\) \(\text{link[i]}\) 的祖先集合，所以 \[ h[i]=w_i+h[\text{link}[i]] \] 至于求 \(mid\)，可以在线段树上二分，找 \([l,r]\) 里第一个 \(i+z[i]>r\) 的位置。

【8.31】CCPC Final 2020

E. Game Theory

打表，令 \(k\) 表示 \(1\) 的个数，答案是 \[ \left(\sum_{s_i=1}2i-1\right)-k(k-1) \] 两部分都可以用线段树维护。

J. Permutation Pattern

区间 dp，令 \(f[l][r][i][j]\) 表示只考虑区间 \([l, r]\)，选出的子序列最小值为 \(i\)，最大值为 \(j\) 的答案。对于一个区间，枚举最大值出现的位置 \(m\in [l,r]\)，设 \(\{L\},\{R\}\) 分别表示 \([l,m-1]\) 和 \([m+1,r]\) 选出的符合条件的子序列，那么子序列 \([\{L\},m,\{R\}]\) 满足条件等价于 \(\max\limits_{x\in \{L\}} x< \min\limits_{y\in\{R\}} y\)。

分 () m ..，.. m () 和 .. m .. 转移，前两种表示最大值位于区间端点，第三种可以后缀和加速，总时间复杂度 \(O(n^4)\)。

K. Stringology

如下图。

M. 3D Geometry

将四面体的直角顶点平移到原点，三个维度进行缩放，变成标准四面体（\(x,y,z\ge 0,\ x+y+z\le 1\)），变换后的立方体只保留第一卦限的部分，最后计算出的体积交乘一个缩放系数就是答案。

设 \(V(x,y,z)\) 表示区域 \(\{(x',y',z')\mid x'\ge x,\ y'\ge y,\ z'\ge z\}\) 与四面体的体积交，那么总体积交可以拆分成 \[ \begin{align} &+V(x_a,y_a,z_a)\\ &-(V(x_b,y_a,z_a)+V(x_a,y_b,z_a)+V(x_a,y_a,z_b))\\ &+(V(x_b,y_b,z_a)+V(x_b,y_a,z_b)+V(x_a,y_b,z_b))\\ &-V(x_b,y_b,z_b) \end{align} \] 其中 \((x_a,y_a,z_a)\) 和 \((x_b,y_b,z_b)\) 为立方体的对角顶点，\(x/y/z_a<x/y/z_b\)。

【9.2】ZJCPC 2025

C. RDDCCD

任取 \(x=a_{1,1}\)，答案一定是 \(x\) 或 \(\text{rev}(x)\) 的质因数幂的组合。考虑怎么 check 某一个质因数幂 \(p\)。

对每一个矩阵中的 \(y\)，如果 \(y\) 和 \(\text{rev}(y)\) 都不是 \(p\) 的倍数，那 \(p\) 肯定不合法；如果都是，翻不翻无所谓；如果恰有一个是，我们就给这个位置随机赋一个 \(v\)，接着将 \(y\) 所处的两条对角线异或上 \(v\)。如此，每次更改一条对角线，我们就能快速计算当前相比初始状态被翻的格子对应 \(v\) 的异或和 \(\text{cur}\)。再令 \(\text{need}\) 表示使 \(p\) 合法应该翻的格子对应的 \(v\) 的异或和，比较 \(\text{need}\) 是否等于 \(\text{cur}\) 即可。单次 check \(O(n^2+q)\)。

M. Master of Both VII

问所有 \(i\in [3,n-1]\) 的 \((1,i)\)，记为 \(d_i\)。如果 \(d_i=0\)，直接计入答案。

一条边 \((x,y)\) 与 \((1,i)\) 在非端点处相交的充要条件是 \(1<x<i<y\le n\)。考虑 \(d_i-d_{i-1}\) 的意义，是 "以 \(i-1\) 为起点的边数 \(-\) 以 \(i\) 为终点的边数"。又因为任何一个三角剖分中形如 \((i-1,y),\ y>i\) 的边和形如 \((x,i),\ x<i-1\) 的边不可能同时存在，所以上述差值中的两项必有一个为 \(0\)。

• 若 \(d_i-d_{i-1} >0\)，说明有 \(d_i-d_{i-1}\) 条边以 \(i-1\) 为起点。
• 若 \(d_i-d_{i-1}<0\)，说明有 \(d_{i-1}-d_i\) 条边以 \(i\) 为终点。

用一个栈存储还没配对的边的起点，遇到一个终点时就弹栈配对。