2025🏀杯省赛游寄

· · 生活·游记

前纪

去年山东ca省赛rk2(山东省的大佬都去外省上大学了所以可以让我这种蒟蒻偷鸡)，然后去年rk1今年不打了，本来是希望可以偷鸡个sd的rk1的，结果成功翻车了😭😭😭

比赛当日

找到赛场在哪简直比所有赛题都难

外校的线下考点，早晨6点半就要起来准备，然后做一个多小时的车（我校在即墨某个镇里）到考点学校。。。然后考点学校里也没啥指引，去了只能自己导航走，在考点学校里绕半天，然后赶在开考前找到了考点。。。

而且当天下雨下的不小，风还大，然后走之前新买的伞直接被风吹坏了，而且还成功被雨伞刮到了手。。。

然后进了考场，内网的考试系统进不去，延时了将近30min（好消息是可以在这段时间里写点东西，写了个快读，fhqtreap，tarjan，结果只有快读用上了）

赛时

看到题，A没什么好说的，直接O(\sqrt{n})求质数（没错我连线性筛都懒得写）

B题，一看，答案是确定的（就是能得到答案大概率是对的，不会有数错了的情况），先写了个二进制枚举36个位置之后判断是否合法，结果跑不出来，然后就改成了只枚举没被填的26个位置，大概复杂度O(6^3*2^{26}) ,然后跑出来了

C题，就是直接每次直接跳到对应位置，然后判断的得了多少分，复杂度是O(m+n)的，（不知道他为什么只开1e3）

D题，考虑根节点到对应节点的路径，每次走一个右子节点则颜色反转，左子结点则颜色不变，那么即为求走了多少右子节点，然后考虑一下堆的节点分布，上层第k的节点的左子结点为下一层2k,右子节点为下一层2k+1(假如从0开始编号的话)，那么考虑位运算，左子结点1的比特数不变，右子节点1比特数+1，那么其实就是直接就是输入k，求k-1(因为题目从1开始编号)中有几个比特为1，直接__bulid_in就能O(1)，由于是闭卷背不过__build_in所以写了O(\log k) 求法。

E题，首先每个值可一个桶记录个数，考虑一系列球，第i种有x_i个，假如没种球认为是相同的，那么总排列数为\frac{(\sum\limits_{i=1}^n x_i)!}{\prod_{i=1}^n x_i!},那么考虑取出一个行长度一个列长度，设其为a,b,考虑将两个球取出再求排列，

当a\neq b时，x'_i=\left\{\begin{array}{cc} x_a-1 & i=a\\ x_b-1 & i=b \\ x_i & i\neq a,i\neq b\end{array}\right.

那么\frac{(\sum\limits_{i=1}^n x'_i)!}{\prod_{i=1}^n x'_i!}=\frac{(\sum\limits_{i=1}^n x'_i)!}{\prod_{i=1}^n x_i!}*\frac{x_a!}{x'_a!}*\frac{x_b!}{x_b'!}=\frac{(\sum\limits_{i=1}^n x_i-2)!}{\prod_{i=1}^n x_i!}*\frac{x_a!}{(x_a-1)!}*\frac{x_b!}{(x_b-1)!}

当a=b时，x'_i=\left\{\begin{array}{cc} x_a-2 & i=a\\ \\ x_i & i\neq a\end{array}\right.

那么\frac{(\sum\limits_{i=1}^n x'_i)!}{\prod_{i=1}^n x'_i!}=\frac{(\sum\limits_{i=1}^n x'_i)!}{\prod_{i=1}^n x_i!}*\frac{x_a!}{x'_a!}=\frac{(\sum\limits_{i=1}^n x_i-2)!}{\prod_{i=1}^n x_i!}*\frac{x_a!}{(x_a-2)!}

注意到对于每一对a,b式子中的\frac{(\sum\limits_{i=1}^n x_i-2)!}{\prod_{i=1}^n x_i!}部分均相同，其可以预处理求出，然后假如预处理出阶乘，那么后面的部分可以O(1)求，那么可以先找出输入值，枚举其所有因子找到对应的n,m，然后对于每一对n,m求答案，复杂度O(输入长度)

F题，就是对于每一个节点，求出其左侧一直递减，一直到最左侧是哪个节点，其可以有左侧相邻节点的结果推得，然后在对每个节点向左跳两次，复杂度O(n)

G题，直接用atanl求角度，然后扫描线扫一下就能求出结果，（暂时没找到什么可以不用三角函数避免掉精度的做法）

H题是带权基环树求直径的板子题

然后写完所有题才刚过12点，然后很自信的以为再对拍对拍就稳了（往年根本没时间对拍），然后对拍了EFH，出考场自信满满以为自己已经稳了。

赛后

之后群里有人问我是不是稳了，我自信回复，然后有人发了ca题面，然后点进去一看

可以经过相同的点只是不能经过相同的边。。。我当成不能经过相同点做的。。。

也就是说，

如果出现这种情况就寄飞了。。。

所以说，

读题很重要

读题很重要

读题很重要

所以说以后各位大佬一定要认真认真认真读题，千万别犯我这种低级错误。。。

后记

这次题不难，估计有一车ak的。自信满满，结果烤熟的鸭子飞了，偷鸡失败🤡🤡🤡，也是成功的捐了300。希望各位大佬国赛的时候轻虐😭😭😭