2020 四川省赛自贡游记

Day 0. 出发 & 热身赛

这次我们学校的参赛人数比较多（大概二十来个人），所以学校直接包了辆大巴，就没让我们自己买高铁票。因为是非正式参赛，我们也就没怎么仔细做准备，只是随便打了份 kuangbin 的板子。路上晃悠了四个多小时，终于在接近下午一点的时候抵达了目的地——四川轻化工大学。据说这个地方产五粮液。等我们一行人到食堂的时候，已经没剩下什么吃的了。主办方给我们的伙食，号称「精品套餐」，两荤一素，得到了大家一致的差评。

下午热身赛，我和 lls 由于先回了趟酒店，所以去的比较晚。等我们到赛场的时候，队友已经过了两题了。最后一道题我先是读错了一波题，纠正过来之后 lls 脑补了一个看上去很对的做法。然而写出来交上去之后却发现评测机卡了，不知道过没过。于是这场热身赛跟没打一样。

晚上回宾馆点外卖。

Day 1. 正赛

第二天早上 8:00 集合出发，然而众所周知 8:00 集合等 8:15 人才会来齐，lls 还因为前一天晚上打 Codeforces 结果没爬起来。总之等我们到赛场的时候已经快开始了。开始之后居然不是统一分发题目，而是念队伍名字，挨个上去拿试题。我们排到比较后面，等拿到题的时候已经比赛已经开始差不多五分钟了，榜上签到题过了一片。显然主办方就没经历也没了解过这种比赛，完全不知道这种比赛正常的流程是什么样子的。

整场比赛，我唯一的贡献就是写了一道签到题和一道不那么签到的题，然后读了三道题（还读错了一道）。果然是退役选手。

众所周知，打星等于打铁，所以颁奖和我们没有什么关系。

令人无语的地方就是他们在颁奖典礼的大厅门口安排了四个迎宾小姐。结果就是选手们很尴尬，迎宾小姐很尴尬，教练也很尴尬，反正所有人都不知道该做何表情。

最终没有滚榜，就直接把奖牌发了。我们学校拿了三个金牌，其中一个是金牌倒数第二。除了我们之外最好的成绩是第六名（包含打星队）。冠亚季军被电子科技大学承包了，然而真正的第一名是一支打星的高中生队伍。

D

求有多少对 $⟨ x, y ⟩$ 满足 $1 ⩽ x, y ⩽ m$ 并且 $g cd (2^{x} - 1, 2^{y} - 1) = n$ ， $n$ 和 $m$ 的范围都是 $1 0^{5}$ 。

不妨假设 $x < y$ ，注意到：

2^{y} - 1 = 2^{y - x} \cdot (2^{x} - 1) + 2^{y - x} - 1

即：

2^{y} - 1 \equiv 2^{y - x} - 1 (mod 2^{x} - 1)

因此：

g cd (2^{x} - 1, 2^{y} - 1) = g cd (2^{x} - 1, 2^{y - x} - 1) = 2^{g c d (x, y)} - 1

然后这个题就变成了经典的寻找某个范围内有多少对数互质，欧拉函数前缀和。

G

给定一张图，初始的时候全都是白点。第一步你可以选择一些点，把它们染成黑色，代价是这些点的权值和。第二步你可以反复把与黑色点相连的白色点染黑，不花费任何代价，最终整个图都是黑色。不过在任意时刻，所有白点之间必须连通。问最小代价。

首先缩点双连通分量，因为一个点双里面除了割点之外，随便怎么染都不会使白点不连通，只需要一个黑点当“种子”就能染完。缩出来之后是一棵树，可以发现我们必须从叶子节点开始，并且可以留一个叶子最后再染。注意特判原图只有一个点双的情况。

这个题我一开始读错了，以为是所有黑点必须连通，觉得这不是签到题么，于是 WA 了两发。

J

这题也其实蛮签到的。大概意思就是让你构造输入把快速排序的时间复杂度卡到 $O (n^{2})$ 。给定快速排序每次选择 pivot 的策略。

做法也很简单，就是每次让选的 pivot 的值都是最小值或者最大值就行了。然而这个题一直没人做，直到一个多小时之后才被我们拿了一血。