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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

高精度？×，考虑哈希。

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

一开始想的是使用 __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 是最简单的题，结果半天想不出来，后面才发现其实是气球给反了。

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

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

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

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

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

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

结论是这样的，$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)$

不难想到，对于 $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 了一发。

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

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

考虑当 $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)\}$。

$x$ 怎么求？别忘了还有性价比顺序的条件。显然 $\forall i\in [2, n], \cfrac{v_i}{w_i} = \cfrac{n - i + 1}{n - i + 2}(x + 1)$，一定是按降序排的，那么我们只需要满足 $\cfrac{v_1}{w_1} > \cfrac{v_2}{w_2}$ 即可，即 $x > \cfrac{n - 1}{n}(x + 1)$，解得 $x > n - 1$。由于 $v_i$ 为整数，取 $x_{min} = n$。

因此我们可以得到最优序列 $w = \{1, 2, ..., n\}, v = {n, n + 1, ..., (n - 1)(n + 1)}$。可以证明，没有比这更优的序列了。

因此直接输出就好了，时间复杂度 $O(W_{lim})$。

这题比较有趣。

首先我们将两幅图异或一下，即如果对于某个坐标，有且仅有一幅图在这个坐标上是黑色时，我们就把这个位置变成黑色，否则变成白色。

接下来考虑怎么讲所有黑色变成白色。如果直接想可能不好想，我们可以先从数轴想起。

显然在数轴上，如果 $x$ 上是黑色的，那么我们对 $x + 1$ 执行一次操作，相当于将 $x$ 上的黑色转移到 $x + 2$ 上了，这样我们就能保证 $\leq x$ 上的所有格子都是黑色的。如果一直做下去能够消完所有黑色，那么就说明答案为 YES。

接下来考虑在方格上怎么做。我们一列一列地扫，如果 $(x, y)$ 位置上是黑色的，我们就对 $(x, y + 1)$ 做一次操作，这样我们就能保证扫完 $y$ 列后 $\leq y$ 的所有列都是白色的。接下来的操作与数轴一样，不多赘述。

接下来我们在考虑六边形。我们一行一行地扫。如果 $(x, y, z)$ 位置上是黑色的，我们就对这个位置下面的那个格子做一次操作，这样我们就能消掉 $(x, y, z)$ 位置上的黑色，并且还能保证扫完一行后这一行及上面的所有格子都是白色的了。接下来的操作与数轴和方格一样，不多赘述。

接下来考虑怎么判定哪些格子在一行上。容易发现，在一行上的格子都满足 $y - z$ 的值相同，这样的话这个题就几乎做完了。

这题写特别好写，就是想不太好想到，限定最大操作数为 $n + m$ 应该就能保证如果答案是 YES 就一定能消完（但实际上我们设置的 $\max(n, m)$ 也过了）。

时间复杂度为 $O(n\log n)$（因为要按 $y - z$ 排序）。

本来是个简单题，但我们想到的时候已经太晚了，写不完了。

首先，将所有 w 拆成两个 v 做马拉车。然后考虑将 v 还原回 w，如果左右边界卡在了 w 的中间，就需要做找极长的 w 序列之类的操作。

预处理一下对于某个位置的 w，其向前的极长 w 序列长度和向后的极长 w 序列长度即可。

时间复杂度为 $O(n)$，但是及其难写，我们搓了一个小时都没搓出来，结果比赛结束了。

这题大水题，纯模拟，但是我以为不是个模拟题，于是就没敢写。而且封榜前榜是歪的，居然没几个队写这题，这就导致我更不敢写了。

这次比赛封榜前我们排名 74，银牌倒数第二。银牌肯定是不指望了，主要是看在铜牌哪个位置。滚榜的时候一看，铜牌倒数第二名就已经 5 题了（我们封榜前也是 5 题）。但还好，我们虽然也是 5 题，但我们的罚时较少，最后排名正好卡在了 100 名，与银牌线差 25 名。

拿到铜牌之后我们就撤离体育馆吃饭去了。

当时校园卡上还剩 94 块钱，由于用不完不兑现，于是我们就在哈工大文创店用了。

但说实话，如果人均 30 块钱的话真买不到什么东西（毕竟文创店一般都挺贵）。考虑到这是桑神退役前的最后一站了，我和 wxt 就没买，用剩下的 94 块钱给桑神买了个哈工大的小熊，就当作送给桑神的饯别礼了，也祝桑神考研能够考上自己心仪的学校。

出了校门，我们来到了一家开在人家小区里的东北菜。不得不说，一推门进去我就知道来对地方了。这家店并不在特别热闹的地方，相反开的比较偏僻，但仍然座无虚席。老板娘操着一口特别正宗的东北口音，和我交流也是一口一个“老弟”。说到菜品，这家店的菜品也都是用特别大的盘子装的（很符合我对东北菜的想象），而且价格也并不贵，最后人均 40 多点还剩一小半没吃完。

吃完后，由于 wxt 要提早赶火车，桑神要去中央大街逛逛，我还不知道干啥，于是就打算在这家店里就各自分别了。分别前，我们还拍了一张合照，作为我们曾经一起奋斗过的证据。

分别后，我去找了一家洗浴中心泡个澡。作为南方人，第一次来洗浴中心还特别不习惯。虽然在北京已经习惯了不穿衣服进大澡堂了，但对洗浴中心的一些规矩还不太了解。这家洗浴中心外面看着没啥人，但是里面人挺多，有很多老人和小孩在泡澡。我现在澡堂里泡了 50 分钟左右，还在澡堂里打了两把音游，就去洗了洗身子，漱了个口就收拾东西赶火车去了。

出澡堂的时候，我还想着把浴巾还给别人，结果店员给我说让我自己带走，还拿了个袋子帮我打包。出澡堂后买了杯热奶茶就赶火车去了，不得不说泡了个热水澡再喝杯热奶茶确实挺舒服的。

在火车上还遇到一个特别好的东北阿姨，应该是从东北来北京生活的。感觉这个阿姨特别能聊，给人一种特别热情的感觉，而且我有困难他都会帮助我，这使我对东北人的印象变的更好了。

又是错失银牌的一场比赛。本赛季打了三场比赛，都以拿铜失败告终。

这次打的三次比赛让我认识到了思维真的非常重要。只要能把思维题做的大差不差，拿个银牌基本上没啥太大问题。

后续应该会加强对 AT 和 CF 的训练，争取明年守银摄金💪。