2025.2.22 NOI 模拟赛 题解
szt100309
·
·
个人记录
T1 橡皮平原 2.0（plain）QOJ # 2552. Points
题意
n$ 次操作，每次加入一个三元组 $(s,x,y)$，或删去一个三元组 $(s,x,y)$（保证存在，若有多个则删去其中一个），其中 $s\in\{1,2\}$，每次操作后求出 $\min_{(x,y)\in U,(a,b)\in V}\max(x+a,y+b)$，其中 $U$ 为二元组 $(x,y)$ 的集合满足存在三元组 $(1,x,y)$，$V$ 为二元组 $(x,y)$ 的集合满足存在三元组 $(2,x,y)$，$n\le6\times10^5,1\le x,y\le3\times10^5
分析
y+b&x+a\le y+b\\
x+a&x+a>y+b
\end{cases}=\begin{cases}
y+b&x-y\le b-a\\
x+a&x-y>b-a
\end{cases}
对于 x-y\le b-a 和 x-y>b-a 的情况分开维护，两者的答案取较小的即为最终答案
后者只要将 U 和 V 互换、每个二元组两数互换即可转化为前者，因此只考虑第一种形式
考虑用一颗权值线段树维护，每个叶子 p 维护 U 中 x-y=p 的 y 的集合 与 V 中 a-b=p 的 b 的集合，区间中维护上述两个集合的较小值与区间内答案
时间复杂度 O(n\log V)
代码
T2 图书馆（library）CF868G El Toll Caves
题意
有 n 个格子，其中恰好一个包含物品（等概率且事先不知其位置），每次选择 k 个格子，若物品在其中任何一个当中则有 \frac 12 的概率结束游戏，求期望步数，n,k\le5\times10^8，多测 t\le10^5
分析
显然 n 个物品之间是等价的，因此每次选择 被选择次数最少的 k 个 一定最优（相同则任意）
因此考虑将物品标号为 0\sim n-1，第 i 次选择区间 [ik\bmod n,(ik+k)\bmod n)
其可以转化为每次选前 k 个，然后将这 k 个移到最后
从中可以看出，长为 \gcd(k,n) 的连续的一段可以缩为一个位置，因此以下假设 k 和 n 互质
令 f_i 表示位置 i 包含物品时的期望步数，则答案为 \frac 1n\sum_{i=0}^{n-1}f_i
考虑如何计算 \sum_i f_i
当 k\le i<n 时，选择前 k 个一定不会结束，因此满足 f_i=f_{i-k}+1
当 0\le i<k 时，选择前 k 个有 \frac 12 的概率结束，有 \frac 12 的概率继续，此时 i 处的移到 n+i-k 处，因此满足 f_i=\frac12f_{n+i-k}+1
由于 n,k 互质，因此递推关系成环
考虑将所有 f_i 都表示为 k_if_0+b_i 的形式
从 1 到 n-1 枚举 i，由 f_{(i-1)k\bmod n} 推到 f_{ik\bmod n}
最终 f_0=f_{n-k}+1，得到方程 f_0=k_{n-k}f_0+b_{n-k}+1，解出 f_0，从而得到 \sum_i f_i
这样时间复杂度为 O(n)，可做到 O(k)
考虑进一步优化
发现实际上可以舍弃 f 数组，上述递推过程可以看做两个一次函数递推，cur 和 sum，初始 cur=sum=x（此处 x 替代 f_0），然后从 1 到 n-1 枚举 i，若 ik\bmod n<k 则 cur\gets \frac12cur，然后 cur\gets cur+1，sum\gets sum+cur，最终的 cur=x，解得 x 后带入 sum 即为 \sum_i f_i
令 cur=k_0x+b_0，sum=k_1x+b_1，维护向量 (k_0,b_0,k_1,b_1,1)，上述过程可看做该向量乘以一个矩阵
$$\begin{bmatrix}
\frac12&0&0&0&0\\
0&\frac12&0&0&0\\
0&0&1&0&0\\
0&0&0&1&0\\
0&0&0&0&1
\end{bmatrix}$$
$cur\gets cur+1$，$sum\gets sum+cur$ 的矩阵为
$$\begin{bmatrix}
1&0&1&0&0\\
0&1&0&1&0\\
0&0&1&0&0\\
0&0&0&1&0\\
0&1&0&1&1
\end{bmatrix}$$
前者记为 $U$，后者记为 $R$，考虑万欧
则相当于从 $0$ 出发，沿着 $y=\frac knx$ 走，若纵坐标为整数则乘以 $U$，若横坐标为整数则乘以 $R$，优先取前者，横坐标到达 $n-1$ 时停止
可 $O(\log n)$ 计算，注意要提取矩阵中 $6$ 个有用位置计算以减小常数
[代码](https://codeforces.com/contest/868/submission/307285557)
# T3 扑克（poke）[P10363 [PA 2024] Monety](https://www.luogu.com.cn/problem/P10363)
## 题意
一个 $n\times m$ 的矩阵，每个位置为 $N/C$，前 $k$ 行给定，在矩阵上博弈，$N/C$ 中选择一个为先手，轮到的一方选择一个与它相同的字符，并删去该字符及同一行中该字符右侧的字符，无法操作为败，求能使后手必胜的矩阵数量，$0\le k\le n\le 32,m\le24
分析
考虑如何判断一个给定矩阵能否使后手必胜（之后称其为合法）
令每行 极长前缀连续段 中每个位置的权值都是 2^{m-1}，剩余每个位置的权值为该位置左侧的权值的一半，若 N 权值总和等于 C 权值总和，则该矩阵合法，否则权值大的一方必胜
证明：
- 对于一个局面，令其前驱为选择一行删去一个后缀能到达的局面
- 考虑归纳，对于每行都同色的局面显然，否则假定当前局面的所有前驱都符合
- 令 w 为权值最小的一个位置的权值
- 当前操作方可以操作 任意一个 w 对应位置和其左侧的位置中第一个（最靠后的）能操作的位置，显然其存在（否则 w=2^{m-1}），而且这样操作后 当前操作方的总权值减去对方的总权值 这一值会减少 w，且显然其为减少量最少的一种方式（根据等比数列求和公式，若选择了其他位置这一减少量不可能减少）
- 若当前局面的两个权值总和相同，显然 w 至少有两个，否则权值不可能相等（根据假设，w\ne 2^{m-1}）
- 此时当前操作方令总权值（己方权值减对方权值）减少 w，轮到对方时还剩下至少一个 w，从当前操作方的视角相当于令总权值加上 w，双方权值仍然相等，仍然为后手必胜
- 若双方权值总和不等，则类似可得最优情况下两者的大小关系不会变化，最终到达 N 必胜或 C 必胜的局面
考虑如何计数
先特判 m=1 的情况
将矩阵每一行错位，权值相同的位置对齐，从左到右扫描，遇到一个 2^{m-1}\to 2^{m-2} 的分界点就加入对应前缀，每后移一格就放好已经加入行对应位置的字符
令 dp_{i,j,w} 表示目前扫描了长为 i 的前缀，已经加入了 j 个，双方权值差为 w 的方案数
这样状态数是关于 m 的指数的，无法接受
发现上述加入过程相当于每次加入一个 NNN\cdots C 或 CCC\cdots N 前缀（全相同的行最后算贡献），所有这样前缀的总权值绝对值不超过 O(nm)2^{m-2} 且为 2^{m-2} 的倍数
剩余部分的权值一定为 2^i 的倍数，且绝对值不超过 O(n)2^i，否则最终无法归零
因此将 w 拆为两个数
总状态数为 O(m\times n\times nm\times n)=O(m^2n^3) 的
单次转移枚举新加入多少 NNN\cdots C 型的，新加入多少 CCC\cdots N 型的，加入的一列 C 的数量
三步之间是独立的，可以分步进行，单次 O(n) 转移
总时间复杂度 O(m^2n^4)，空间可以做到 O(mn^3)
代码
参考
比赛结果
56+8+0$，rk $-2