#1012 GDCPC2025题解
广东省第二十二届大学生程序设计竞赛（GDCPC2025）题解
难度参考
以下按比赛题号给出难度分级，仅供参考：
- Easy：D，F
- Easy–Medium：G，H，J
- Medium：A，I，K
- Medium–Hard：B，C，E
- Hard：L
题目索引
| 题号 | 题目名称 |
|---|---|
| A | 矩阵游戏 |
| B | 整数生成器 |
| C | 切牌 |
| D | 生成魔咒 |
| E | 网格染色 |
| F | 排名预测 |
| G | 货币系统 |
| H | 松散子序列 |
| I | 队伍取名 |
| J | 解谜比赛 |
| K | 打字机 |
| L | 路线选择 |
A. 矩阵游戏
题意
给定 n\times m 的 01
矩阵与整数 A,B。每次可选择一整行或一整列全部
0/1 取反，操作任意次。若格子为 1，则贡献 A\cdot i + B\cdot j。求最大总得分。
约束
1\le n\le 10^6，1\le m\le 10，|A|,|B|\le 10^6，a_{i,j}\in\{0,1\}。
做法
先枚举列翻转模式（共 2^m
种）。对固定行下标 i 与列模式 s，记
W=\sum_{j=1}^{m} j\cdot [s_j=1]，cnt1=\mathrm{popcount}(s)。
行不翻转与翻转时，全行贡献分别为
S_1 = A\cdot i\cdot cnt1 + B\cdot W,\quad S_2 = A\cdot i\cdot (m-cnt1) + B\cdot\left(\frac{m(m+1)}{2}-W\right).
行翻转更优当且仅当 S_2>S_1，等价于
A\cdot i\cdot (m-2\cdot cnt1) > B\cdot\left(2W-\frac{m(m+1)}{2}\right).
按阈值 k 将行下标分为 i\le k 与 i>k 两类分别统计。总复杂度 O(2^{2m}\log n)。
B. 整数生成器
题意
给定大小为 n 的整数集合 S（元素互不相同）与目标整数 x。每次从 S 中选 a,b，将 a\mid b、a\oplus b、a\mathbin{\&} b 之一加入 S，至多 70 次。判断能否使 x\in S，并输出构造。
约束
1\le n\le 10^5，0\le x<2^{30}，0\le a_i<2^{30}。
做法
在值域 V 上讨论，有 \log V=30 量级。已知做法复杂度可做到 O(n^2(\log V)^2) 或 O(n\log V+(\log V)^4)。
记闭包集合 B，利用恒等式
a_i\vee a_j=(a_i\mathbin{\&} a_j)\oplus a_i\oplus a_j.
在「\mathbin{\&} 对 B 封闭」等条件下，将三元积 a_1\mathbin{\&}a_2\mathbin{\&}a_3 用 \oplus 与 \mathbin{\&} 展开；再将每个 a_i 写成若干 x 的异或和 a_i=\bigoplus_j x_{p_{i,j}}，从而展开 a_i\mathbin{\&}a_j 并继续化简。
C. 切牌
题意
给定长度为 n 的目标排列，以及 Q 次交换操作；需与题目描述的切牌过程及合法分段规则一致。
约束
2\le n\le 10^5，1\le Q\le 10^5。
做法
将排列与下标 x,x-1 及点对 (p_{x-1},p_x) 的相对顺序分情况讨论；涉及 k 与 k+1 的分段，以及形如 (p_{a_x}-1,x) 的区间配对。单步或均摊复杂度可做到 O(1)，整体亦可做到 O(n\log n)（依实现与维护结构而定）。
D. 生成魔咒
题意
单击耗时 1，得到长度 1。长按选正整数 x，耗时 2^x，得到长度 10^x。对多个需求长度分别求最少总时间。
约束
需求组数 T\le 5\times 10^4，每个长度 1\le r\le 10^{18}。
做法
代价与长度满足「耗时 2^x、长度 10^x」的对应关系，据此对需求长度分别求最小总耗时。
E. 网格染色
题意
2 行 n 列网格，颜色编号 1\sim 2n。部分格子已染色且不可改，为未染色格染色，使四连通同色块个数最少，输出任意合法方案。
约束
1\le n\le 10^5。
做法
在 2\times n 模型上从边界情形（例如全未染色的基准）出发构造，时间复杂度 O(n)。
F. 排名预测
题意
ICPC 封榜模型：已知己方最终通过题数与罚时；另给一队在封榜前后的提交时间与封榜前结果，封榜后结果未知。判断对方是否可能严格优于己方；若能，求封榜后对方至少再通过多少题才会严格优于己方。无解时输出题面约定的特殊值（例如 -1，以题面为准）。
约束
多组数据，题目数 n 较小（如 10\le n\le 15），其余约束见题目描述。
做法
可建立 O(n\log n)、O(n2^n) 与 O(n) 等不同复杂度的建模与搜索/递推形式，按状态规模选取。
G. 货币系统
题意
升序正整数数组 A，A_1=1。f(x,y) 为题面定义的「从大面额尽量多取」的张数递归。对给定 m，求满足 f(x,n)=m 的正整数 x 的个数。
约束
1\le n\le 10^5，1\le q\le 10^6，A_i\le 10^6，1\le m_i\le 10^9。
做法
利用
f(x+A_n,n)=f(x,n)+1,\qquad f(x,n)=f(x\bmod A_n,n)+\left\lfloor\frac{x}{A_n}\right\rfloor
等性质，在 x\in[1,A_n] 上建立辅助序列 \{B_k\}，将「f(x,n)=m」转化为对 \sum_{k=1}^{m} B_k 的计数，并注意 m 增大时与 A_n 相关的求和不变量。预处理 O(A_n)，单次询问 O(1)，总可做到约 O(\max(A_n,q))。
H. 松散子序列
题意
子序列相邻两项在原串中下标差大于 k，称为 k 松散子序列。求本质不同非空 k 松散子序列个数，对 998244353 取模。
约束
多组，\sum n\le 10^6，0\le k\le n。
做法
k=0 单独处理。设 dp[i] 表示以位置 i 结尾的方案贡献；用 occ[i] 表示同一字符上一次出现位置，将 \sum dp[j] 的区间拆为 [0,occ[i]-1] 与 [occ[i],i-1] 两段化简。
k\neq 0 时，对 dp[i-k],\ldots,dp[i-1] 维护滑动窗口，并更新 dp[i+k] 等形式（见标准区间和优化）。总时间 O(n)。
I. 队伍取名
题意
n 个人，每人姓名编码为三个整数。从三人姓名各取一位拼成三字串，统计该串恰等于某人完整姓名的方案数（计数定义见题目描述）。
约束
3\le n\le 10^5，1\le S_{i,j}\le 10^6。
做法
对第 i 个人与三进制状态 s 设计 f_{i,s},g_{i,s}，在 s 维度上做子集卷积类合并（FWT / SOS DP）。对 \mathrm{popcount}(s)\ge 2 的状态需叠加与 f_{i,s}^2 相关的项。复杂度量级包括 O(2^{3n}\log n)、O(4^{3n}\log n)、O(2^{3n})、O(4^{3n}) 等（依实现与状态压缩方式而定）。实现可用哈希表或定长数组存稀疏状态。
J. 解谜比赛
题意
n 道题、带边权的有向图传播能量；每题有解锁阈值 a_i；若干强制刷新器在指定时刻将部分题的阈值改为 0。求每题最早解锁时间。
约束
3\le n\le 10^5，0\le m\le 10^6，0\le k\le 10^5，0\le a_i\le 10^5，边权与时间等可达 10^9 量级。保证至少一题初始阈值为 0。
做法
注意存在 a_i=0 的起点；将边权与刷新时刻纳入最短路模型，距离初值可取无穷大再松弛更新。
K. 打字机
题意
上纸槽模板串 T、下纸槽输出串 S；两槽指针按题面规则移动（上槽指针到端点后折返）。给定目标串 S，问是否存在模板 T。
约束
多组，\sum |S|\le 10^6。
做法
将无限输出写成周期形式：设 T=aLb（a,b 为子串记号），整体与 (aLbL^{\mathrm R})^\infty 一类无穷串对齐，其中 L^{\mathrm R} 表示反串。当 |T|\ge 2 时，定义
T'=T[1]T[2]\cdots T[|T|-1]\,T[|T|]\,T[|T|-1]\cdots T[2].
按 |S| 与 |T|、|T'|=2|T|-2 的大小分三类，将候选与 S 的某段子串比对；再按 |T| 与 |S| 分三段与前缀 S[1..i] 对照。实现可用 Manacher、Z 函数等与字符串匹配相关的工具，总复杂度 O(|S|)（辅以对数因子时可记为含 \log 的写法）。
L. 路线选择
题意
n\times m 网格，边上有移动速度。从入口到出口，需按任意顺序经过 k 个给定摊位（在网格边上），求最短时间。
约束
2\le n\le 50，2\le m\le 4，1\le k\le 10^5，边权范围见题目描述。
做法
状态压缩动态规划：在较小 m 下对「已访问摊位子集」与网格位置联合建状态，转移按多种情形分类讨论。复杂度约为 O(n\cdot m\cdot 7^m\cdot 36)，其中 36=6\times 6 与格点间六种走向及配对方式有关。