#1009 GDCPC2023题解
广东省第二十届大学生程序设计竞赛（GDCPC2023）题解
题目索引
| 题号 | 题目名称 |
|---|---|
| A | 算法竞赛 |
| B | 基站建设 |
| C | 市场交易 |
| D | 新居规划 |
| E | 新怀质问 |
| F | 格子旅行 |
| G | 交换操作 |
| H | 流画溢彩 |
| I | 路径规划 |
| J | X 等于 Y |
| K | 独立钻石 |
| L | 经典问题 |
| M | 计算几何 |
A. 算法竞赛
题意
竞赛自 y_1 年起举办，另有 n 个停办年份 s_1,\ldots,s_n；其余年份每年举办一次。给定查询年份 y_2（保证非停办年），求到 y_2 年为止该竞赛累计举办届数。
约束
多组；1\le T\le 20；1970\le y_1\le 9999；0\le n\le 100；y_1<s_i\le 9999 且 s_i 递增互异；y_1\le y_2\le 9999。
做法
在有序停办年份上扫描，总复杂度 O(n+y_2-y_1)。
B. 基站建设
题意
1\sim n 千米位置建基站成本为 a_i；m 条需求，第 i 条表示区间 [l_i,r_i] 内至少一座基站。求满足所有需求的最小总成本。
约束
多组；\sum n,\sum m\le 5\times 10^5；1\le a_i\le 10^9。
做法
设 f(i) 表示覆盖到位置 i 的最小代价。转移在区间 [j+1,i-1] 上取 \min，并可用指针 p_i 表示最左合法决策，满足 p_i\ge p_{i-1}-1 的单调性将转移压为均摊 O(1)。总复杂度 O(n)。
C. 市场交易
题意
n 间商店，第 i 间买卖单价均为 a_i，且最多交易 b_i 次（买或卖各算一次）。初无货，求最大利润。
约束
多组；\sum n\le 10^6；1\le a_i,b_i\le 10^6。
做法
时间复杂度 O(n\log n)。
D. 新居规划
题意
n 人入住 m 栋排成一排的互异房屋；相邻房屋的人互为邻居。第 i 人有邻居时满意度 a_i，无邻居时满意度 b_i。求总满意度最大值。
约束
多组；\sum n\le 10^6；1\le n\le 5\times 10^5，1\le m\le 10^9，n\le m。
做法
将住户按连续入住段分组，段长记为 k。与 \sum_{i=1}^{n} b_i/i、(a_i-b_i) 及段合并有关的式子中会出现 k+2(n-k)=2n-k，并用到条件 2n-k\le m（即 m\ge 2n-1）等分界。总时间 O(n) 或 O(n\log n)。
E. 新怀质问
题意
给定 n 个小写串，恰选 k 个，使某对串的最长公共前缀 v 的字典序最小；且 v 需为所有满足条件的串中字典序最大者（题面形式化定义见题目描述）。
约束
多组；2\le n\le 10^6，2\le k\le n；\sum |w_i|\le 10^6。
做法
在 n,k
与最长公共前缀（lcp）意义下构造字典序最小的目标串；按字符区间扩展并与字典序比较链（如
abcd* 与 abc[a-d]* 等形式）定序，用 Trie
维护，复杂度 O(26\cdot\sum|s|)。
F. 格子旅行
题意
n 个格子排成一行，每格颜色 c_i、球权 v_i。多次旅行：给定起点与颜色集合 \mathbb{A}，只能在颜色属于 \mathbb{A} 的格子上左右移动，并可按题面规则取走球。每次操作还包含题面给出的修改（类型见输入格式）。
约束
多组；1\le n,q\le 10^5；颜色、权值范围见题目描述。
做法
与分治或区间处理相关的复杂度写法包括 O(\sum k\log^2 n) 与 O(\sum k\log n)。
G. 交换操作
题意
给定非负整数序列 A，定义
F(A)=\max_{1\le k<n}\Bigl((a_1\mathbin{\&}\cdots\mathbin{\&}a_k)+(a_{k+1}\mathbin{\&}\cdots\mathbin{\&}a_n)\Bigr).
至多交换一对 i<j 的位置，求 F(A) 的最大值。
约束
多组；\sum n\le 10^5；0\le a_i\le 10^9。
做法
记 f(i,j)=a_i\mathbin{\&}\cdots\mathbin{\&}a_j，用相邻段首段尾是否变化把 i 的有效位置压到 O(\log a_i) 级别。枚举分割点与一次交换时，有形如
f(k+1,j-1)\mathbin{\&}f(j+1,n)\mathbin{\&}a_i,\quad f(1,i-1)\mathbin{\&}f(i+1,k)\mathbin{\&}a_j
等合并式，并对固定 v=f(1,i-1)\mathbin{\&}f(i+1,k) 用函数 g(v,k) 在 j 上扫描。单组可达 O(n\log^2 a_i)；配合 RMQ 可做 O(n\log n) 预处理、O(1) 查询。
H. 流画溢彩
题意
长为 n 的序列初值全 0。m 个操作，第 i 个将位置 l_i 改为 x_i、r_i 改为 y_i；每个操作恰执行一次。求操作顺序使最终序列元素和最大。
约束
多组；\sum n,\sum m\le 5\times 10^5；1\le l_i<r_i\le n，x_i,y_i\in\{1,2\}。
做法
将操作建成有向图，边上出现 1\to 2、权值 a_u 等；对状态 0、(l_i,2,r_i,2) 等分支 DFS，求使最终序列和最大的操作顺序。
I. 路径规划
题意
n\times m 网格，填入 0\sim nm-1 各恰好一次。从 (1,1) 只能向右或向下走到 (n,m)。路径上格子数值构成集合 \mathbb{S}，令 \mathrm{mex}(\mathbb{S}) 为不在 \mathbb{S} 中的最小非负整数。求 \mathrm{mex}(\mathbb{S}) 的最大可能值。
约束
多组；\sum nm\le 10^6；1\le n,m，nm\le 10^6。
做法
与 \mathrm{mex} 及 x、0、(x-1) 的判定链相关，复杂度 O(nm\log(nm))。
J. X 等于 Y
题意
定义 f(X,b) 为 X 在 b 进制下从低位到高位的数码序列。给定 x,y,A,B，求 2\le a\le A，2\le b\le B，使 f(x,a)=f(y,b)。
约束
多组；1\le T\le 10^3；1\le x,y\le 10^9，2\le A,B\le 10^9；至多 50 组满足 \max(x,y)>10^6。
做法
枚举参数 t 与进制 a,b 的大小关系分情况，复杂度 O(\sqrt{x}\log x) 或 O(\sqrt{x})；需处理 t\le\sqrt{x}、t\le\sqrt{y}、t>\sqrt{x} 等分支及余数 x-ta、y-tb 与整除条件。
K. 独立钻石
题意
n\times m 棋盘（n,m 很小），k 枚棋子初始放置于给定格；按题面四向跳跃吃子规则可任意次操作（含零次）。求操作后棋盘上棋子数的最小值。
约束
多组；1\le T\le 20；1\le n,m\le 6，1\le k\le\min(6,nm)。
做法
DFS 搜索，复杂度量级
O\Bigl(T\cdot nm\cdot k\prod_{i=2}^{k}2^i\Bigr)\approx 1.7\times 10^7.
L. 经典问题
题意
n 点无向完全图：若三元组给出 (u,v) 则边权为 w，否则边权为 |u-v|。求最小生成树边权和。
约束
多组；\sum m\le 5\times 10^5；1\le n\le 10^9，0\le m\le 10^5。
做法
采用 Boruvka：利用大量未显式给出的边权形如 |i-j|，每轮在 O(m) 时间内完成向连通块外连最小边的选择，轮数为 O(\log n) 量级；并讨论 2m、(2m+1) 与区间 [l,r] 上的代表元选取。总复杂度 O(m\log m)。
M. 计算几何
题意
给定 n 顶点凸多边形 P，选两个顶点，过这两点作直线将 P 分成两个面积均为正的多边形 Q,R。记直径为 d(Q),d(R)，求 (d(Q))^2+(d(R))^2 的最小值。
约束
多组；\sum n\le 5\times 10^3；4\le n\le 5\times 10^3；坐标 0\le x_i,y_i\le 10^9，逆时针给定凸包。
做法
在圆周序上设 f(i,j)，满足
f(i,j)=\max\{f(i+1,j),\,f(i,j-1),\,\mathrm{dis}^2(i,j)\},\quad f(i,i+1)=\mathrm{dis}^2(i,i+1),
并讨论 f(i,j) 与 f(j,i) 的对称分解及 i,j 与 (i\pm 1) 的转移方向。复杂度 O(n^2)。