gdcpc 2025 游记

cosf · 2025-06-02 19:20:22 · 生活·游记

已对关键信息进行覆盖（

喜提滚榜第一页倒一，不敌 * 个正式队。

队名：*****

A

给定 n \times m 的 01 矩阵 a_{ij}，定义点 a_{ij} 的权值为 A\times i + B\times j。你可以对任意多行、列进行取反，求最后所有为 1 的点的权值之和的最大值。

注意到 m 很小。将初始时相同的行归到一起，并且记录数组 v_S = \{A \times r_{S, 1}, A \times r_{S, 2}, \dots, A \times r_{S, k_S}\}，其中 r_{S, i} 表示所有为 S 的行的编号，其中 S 表示 1 的位置进行状压后的结果。

然后枚举有哪些列被翻转，假设为 T，则对于一个 S，在未翻转时 S \oplus T 为 1 的位置。于是可以设 j 表示 1 的个数，\mathit{bj} 表示所有 1 的位置乘 B 后求和，\mathit{sbj} 表示 \frac{m(m+1)}{2}\times B，则未翻转时，行 i 的贡献是 A\times i \times j + \mathit{bj}，翻转之后产生的增量为 A \times i \times (m - 2j) + (\mathit{sbj} - 2\mathit{bj})。显然，这个东西关于 i 单调，因此可以在 v_S 上二分。

大概通过时间：3h。

通过者：我。

罚时数：3。原因：初始答案开到 -10^{15}，调到 10^{-18} 就过了。做的时候完全没想道答案可以到 \frac{n(n-1)}{2} \times A。/cf

B

给定一个集合 S 和一个数 x，每次你可以选择 a, b \in S，将 a (\oplus \text{ or } \otimes \text{ or } \odot) b 加入 S。问你能否在 70 步内将 x 加入 S。如果能，给构造。

数据范围忘了。

不会。

学长在这题交了 9 发没过。

C

初始有一个排列 \{1, 2, \dots, n\}。定义一次切牌为：

将该排列划分成若干子串。

将子串任意重排。

按顺序依次取每个子串的第一项。

例如，一种 \{1, 2, 3, 4, 5\} 的切牌为：

现有长为 n 的排列 p，查询有多少种 \{1, 2, \dots, n\} 的切牌方式可以变成 p。

你还要支持 q 次两项 swap，每次修改后输出新的方案数。修改为永久性修改。

观察性质，可以得出以下结论：令 \mathit{pos}_i 表示 i 在 p 中的位置，

第 1 步中，若将排列划分成 k 段，则至多一段可以切牌为 p，并且存在 k_0，使得能否切牌为 p 的必要条件为 k \ge k_0。
若 \mathit{pos}_{i + 1} \gt \mathit{pos}_i，则 k_0 \ge \mathit{pos}_i。
若存在 i \not= j，\mathit{pos}_i \lt \mathit{pos}_j 且 \mathit{pos}_{j + 1} \lt \mathit{pos}_{i + 1}，则 k_0 \ge \mathit{pos}_{j + 1}。

经过暴力验证条件是充要的。只需求出 k_0，然后 n - k_0 + 1 即答案。

对于第二个条件，可以使用 set 维护 \mathit{pos}_{i + 1} \gt \mathit{pos}_i 的所有位置，更新是简单的。

对于第三个条件，可以视为若干个点 (\mathit{pos}_{i + 1}, \mathit{pos}_i)，我们只需要找到横坐标最大，且右下角有其他点的最大横坐标。注意到这些点的横坐标、纵坐标互不相同，并且可近似视为排列（排列去掉一个数），因此可以仿照第二个条件的做法。修改细节较多。

通过时间：没有通过。

想通的时间：4h58m。

成功没通过 C 题。一开始还写了个假做法。/hanx/hanx

D

给定数 n，你可以花费 2^x 的时间让 n 减去 10^x，求恰好让 n 变为 0 的最少时间。

范围忘了。

贪心，每次尽量选最大的 x。

大概通过时间：5m。

通过者：@happybob。

一开始 @happybob 为了翻转数组差点写了 sort。

E

有 2 \times n 的网格，每一个格子上有 2n 个颜色之一，或者没染色。你要给格子染色，使得颜色四连通块数量最少。
1 \le n \le 10^5

不会。

场上没人过。

F

不知道。

不知道。

大概通过时间：40m。

通过者：@Z**。

我连题都没看过，就被人会了。

G

给定 n 个数 1 = A_1 \lt A_2 \lt \dots \lt A_n \le 10^6，定义 f(x, i)：
f(x, i) = \begin{cases} f(x \bmod A_i) + \lfloor\frac{x}{A_i}\rfloor & i \gt 1\\ x & i = 1 \end{cases} $1 \le n, q \le 10^6$，$1 \le m \le 10^9$。

考虑对于 f(0) \dots f(A_n - 1) 暴力，然后 f(kA_n) \dots f((k + 1)A_n - 1) 为前一个数组整体加 k。于是可以变为数 f(0) \dots f(A_n - 1) 中有多少个数比 m 小，就做完了。

大概通过时间：22m。

通过者：我。

~~由于队友霸占电脑导致痛失首 A~~

H

给定字符串 S，求有多少个本质不同的子序列 S_{a_1}, S_{a_2}, \dots, S_{a_m}，使得 a_{i + 1} - a_i \gt k。

不会。

大概通过时间：50m

通过者：@happybob。

~~就是在写这个题霸占电脑（~~

I

给定 n 个三元组 T_i，求有多少个数对 (i; j, k) 使得存在 \{i, j, k\} 的排列 \{p_1, p_2, p_3\}，满足 T_{i, x} = T_{p_x, x}, x \in \{1, 2, 3\}。

不会。

大概通过时间：3h

通过者：@Z**

我一开始想大分讨，但失败了，所幸有队友。

J

给定一个 n 点 e 边带权有向图，每个点有一个权值 a_i。若当时刻 t 时 a_i 第一次变为 0，则时刻 t + w 时 a_v 会减去 1，其中 (v, w) 为 i 的一条出边。额外还有 m 个条件，表示 t_i 时刻会将若干个 a_i 清零。问每一个点第一次为 0 的时间。不存在则为 -1。

考虑拓扑排序，将 queue 换成 priority_queue 即可。然后模拟。

大概通过时间：1h

通过者：我

K

给定字符串 S，对其所有前缀求：

对于字符串 T = t_1t_2\dots t_m，定义其扩展字符串为：
t_1t_2\dots t_mt_{m - 1}t_{m - 2}\dots t_1t_2\dots t_mt_{m - 1}\dots
求最短 T 的长度，使得该 S 前缀为 T 扩展字符串的前缀。

\sum |S| \le 10^6

注意到，将 t_1 去掉后有回文 border，于是考虑枚举这个长度。我们可以在调和级数的复杂度内对能达到的点进行区间取 \max。离线 + set 可以做到单 \log。

另外，还要额外判断未满一个周期的情况，可以二分哈希然后区间取 \max。仍然是单 \log 的（可以 Manacher，没必要）。

注意特判 T 长度为 1 的情况。

大概通过时间：**

通过者：@happybob

一开始疑似哈希写挂，喜提 tle 和 wa，后来发现是 ub 了，改完就过了。

L

给定 n \times m 的网格图，你要在边上行走。你初始在 (0, 0)，你最终要达到 (n, m)。你还必须要经过 k 个边上的点。不同的边经过所需的时间不同。求最少时间。

范围忘了。1 \le k \le 10^5。

不会。

场上 0 人通过。

最后亲爱的 @happybob 在每一题都交了一发。我们获得了学校的第二名。

由于要中考了，所以打的很烂（确信。

自认为在策略上没有重大失误，主要还是实力不足。感觉 xcpc 赛制的比赛还是思维题偏多，~~毕竟可以携带纸质资料。~~