CCPC 11st 区域赛（哈尔滨）游记

LittleYang0531 · 2025-11-13 17:08:25 · 生活·游记

CCPC 11st 区域赛（哈尔滨）游记

🐉🧱正式队伍 CAU_CiAllo University（中文名：中文队名一定要有中文） 队长。省流：铜了。

文章可能有点小长，主要是流水账式的记录，还有一些自己的解题想法，如果有 vp 的还请自觉跳过。

Day -1

本来准备做完大物实验然后上完半节复变函数再跑的，后面发现如果上完半节复变的话就来不及赶火车了，而且课中跑的话被抓到的几率更大，然后就没去，在寝室里呼呼睡大觉睡到四点半了再走的。

这次是从北京站坐的车。北京站虽然没北京西大，但建的比北京西好多了，看上去就是金碧辉煌的感觉。

火车是哈局的车，一上车熟悉的东北口音就涌来了。并且哈局的车在每个位置上都贴了列车长的电话，有任何困难都可以打电话找列车长，人文关怀这一块确实不错。

然后就没有啥好说的了。晚上十点熄灯就睡了，因为第二天早上要很早就得起。

Day 1

早上 6 点 45，火车就到哈尔滨了。当时气温 -1℃，穿着羽绒服一出火车就感觉特别冷，拍了两张照片就出战坐公交去了。

7 点 15 就到人家学校了。很早啊，来赶早八说是。先去体育馆看了一眼，发现没开门，就到人家食堂里吃早餐去了，顺便试一下给我们开的哈工大 e 卡能不能用。

8 点 10 左右队友过来了，我把卡给他也让他吃了个早餐，这个时候外面突然下雪了，趁队友还在吃饭，就出去玩了会雪。8 点半，队友吃完就差不多该过去签到了。

有一说一，哈尔滨站给的东西挺抠的。三个人只给一个包，一本参赛手册和一包红肠，没了。领完了也没事干，就跑到人家地下一层商业街买了杯奶茶坐着玩游戏了。

10 点左右出来给家人打了个视频给他们也看了看雪，聊了聊然后就又缩回地下一层了。

坐到 11 点左右就去食堂吃午饭了。吃了本校生推荐的鱼粉，味道很好，我买的鲜虾鱼粉，还额外加了一根肠和一个简单，虾的个头很大，吃起来虾肉很紧实。

吃完了逛了一会哈工大。哈工大的雪景还是很美的，要是有个女朋友一起逛一定会很幸福吧。找了个空地玩了玩雪然后就去体育馆准备打热身赛了。

B / T2

沙比题，但是我们场上半天都没反应过来。

实际上另外一个点就等于 (x_1, y_2) 就行了。记得判断一下 AB 平行于 x 轴和 y 轴的情况。

A / T1

高精度？×，考虑哈希。

我们做的哈希比较奇怪，准确来说并不叫哈希，是一个类似于哈希的东西。

一开始想的是使用 __int128 保留最后 24 位然后作为哈希值，但发现如果到后面 0 太多了就会出现非常严重的哈希冲突。于是考虑去掉末位 0，发现 99! 和 100! 的哈希也会冲突。这时队友提出来了个想法，就是再加上末位 0 的个数组成哈希的一部分，这样确实就不会冲突了。

因此，我们的做法是首先预处理出 1! 到 10^6! 的哈希值（去掉末位 0 后最后 24 位的值，再加上末位 0 的个数），放进桶里准备进行哈希比较。然后对于输入的 \cfrac{n!}{m}，先将 \cfrac{n!}{m} 转成哈希值，然后从 1 到 10^6 枚举 m^*，尝试还原 n!。如果 \cfrac{n!}{m}m^* 在桶里找到了，那就说明就是 m = m^*。

但是在做的时候一直在 WA，后面才发现原因，是这样的：

我们在进行计算的时候，每次都只保留了 24 位的值，即一直在 %= __int128(1e24)。但当如果有末位 0 出现的时候，我们会 /= 10，这就会导致高位出现 0，但实际上高位很有可能不是 0，这就导致了运算错误。因此我们在计算的时候需要保留 30 位，然后在塞进桶里或者比较的时候再 % __int128(1e24)，这样计算下来就没有问题了。

后面听说其实可以用正常的三哈希做，但并不是像我们一样通过枚举 m^* 还原 n! 的值，这个就没有细研究了。

这场热身赛其实还有个问题，AB 的气球给反了，这就导致场上 A 的气球更多，我们就一直以为 A 是最简单的题，结果半天想不出来，后面才发现其实是气球给反了。

打完了也没逗留，就去民宿办理入住，放下东西出来吃饭了。

吃完饭，我们来到了中央大街。其实中央大街没有什么观音桥春熙路热闹，卖红肠的卖套娃的卖大红帽子的比较多。走到中央大街尽头，就是松花江。这里居然没有护栏，感觉要是腿一软脚一滑人就没了。往回走，看到有卖红肠的，就买了两根尝尝（但后来问东北同学他说这个不正宗），然后就回民宿了。

回到民宿，玩了玩手机，洗了个澡，等桑神也到了之后就睡了。

Day 2

早上 7 点醒的，7 点半收拾好了，出门就把房退了，坐了个公交就到哈工大了。

到哈工大里吃了个早餐，然后就到体育馆准备正式开始比赛了。

A / T1

猜猜题，这题桑神只是看了眼样例就把结论猜出来了👍。

结论是这样的，f(k) 的最大值为满足 \forall i\in [1, n], a_i = x\mod f(x) 条件的 f(k) 的最大值，其中 x 为任意整数。

已知 f(k) 和 x，我们很容易就能得到满足 k\times x = 0 \mod f(k) 的最小 k 即为 k 的最小值，显然易得 k = \cfrac{f(k)}{\gcd(x, f(k))}。

至于 f(k) 的求法，就是一个很经典的差值 gcd，即 f(k) = \gcd(a_1 - a_2, a_2 - a_3, ..., a_{n - 1} - a_{n})。如果 f(k) = 0，则说明答案为 infinity。

时间复杂度 O(n\log n)

G / T7

不难想到，对于 a_{i, j} > 0 的格子，我们应尽可能将雪给到 a_{k, l} < 0 的格子，其中 k \geq i, l \geq j，那么最终答案即为 \sum |a_{i, j}|。

考虑如何分配雪。首先如果上一行之前的都已经考虑完了，我们就把多的雪堆到下一行去考虑，然后把上一行的雪清零（< 0 的除外，不处理）。

对于当前行，我们从最后一列开始扫。如果当前格子雪量 > 0，我们就将该格子的雪填到这个格子后面雪量 < 0 的格子，如果有富余，就留在这个格子里。

最后求一遍 \sum |a_{i, j}| 即可，时间复杂度 O(nm)。

这题其实不难写，只不过我们实现的时候有一点点不一样，没有及时出队就 WA 了一发。

L / T12

大水题，枚举一下每个障碍的要求，然后限定那些地方不能去，跑一遍 BFS 即可。

时间复杂度 O(nm2^k)。

K / T11

考虑当 W_{lim} = 2 时怎么构造。

我们令我们构造出的 w, v 对按照 \cfrac{v}{w} 的顺序排序。

首先性价比最高的 w_i \not= 2，否则贪心一定是对的，那么我们不妨构造 w_1 = 1, v_1 = x，为了卡掉贪心，那么 w_2 = 2, v_2 = x + 1。

扩展到 W_{lim} = 3，显然这个 w_i = 3 不能是性价比最高的（否则贪心法直接选 w_1 = 3 就炸了），也不能是性价比最低的（否则贪心法直接选 w_1 = 1, w_2 = 2 也炸了），因此我们的 w 序列只能是 \{1, 3, 2\}。贪心法一定会选 1, 2，为了卡掉贪心，我们只能让 3 的价值比 1, 2 加起来还高，即 2x + 2 = 2(x + 1)。

同理当 W_{lim} = 4 时，w_i = 4 也只能放在 1, 3 中间，否则都不能卡掉贪心，即 w = \{1, 4, 3, 2\}，v = \{x, 3(x + 1), 2(x + 1), (x + 1)\}。

综上，我们可以构造出长度为 n 的 w 和 v 的序列 \{1, n, n - 1, ..., 2\} 和 \{x, (n - 1)(x + 1), (n - 2)(x + 1), ..., (x + 1)\}。