2021CCPC广州复盘


最后一场CCPC也没有金。怎么说呢,感觉pku出题稍微有点离谱,不过自己菜也是原因之一就是了。

热身赛

队友切了AB,C是神秘计算几何板子题,数据范围和精度各种神秘,三分了一下直线最短距离,然后再次被卡,愿天堂没有计算几何。

赛后听说是POJ原题,不过还是略显离谱。没想到好日子还在后面

正式赛

开局就是阿伟正开,我倒开,bbg看D。看了一圈题面长度、输入规模、时间限制,感觉后面没有前期题,看到F手推了前四项感觉很神秘,此时队友在看I,听说是打表题。bbg给我们灌了H的题意,貌似很cf的构造,但是榜上dirt相当高,反倒是I很像签到,阿伟于是打表秒了。

过了I之后,就是经典两路分推,bbg和阿伟讨论H的构造,我去推好像很可做的A。A写出生成函数就是$\prod_{i=1}^{n}\sum_{i=1}^{\infin}i^{c_i}x_i$前$W$项系数和,翻了波数学公式板子找到了$\sum_{i=1}^{\infin}i^kx_i=x^k\frac{d^k}{dx^k}\frac{1}{(1-x)}$,纸上推了推,发现$\frac{d^k}{dx^k}\frac{1}{(1-x)}=\frac{k}{(1-x)^{(k+1)}}$的规律,所以之前的生成函数就是$\frac{\prod_{i=1}^{n}c_ix^c_i}{(1-x)^{\sum_{i=1}^{n}c_i+1}}$,如果要求它的前$W$项之和,就等于原生成函数乘$\sum_{i=0}^{n}x_i=\frac{1}{(1-x)}$(也就是做一次前缀和)后第$W$项的系数。

然后我就不会求了

(现在想想只觉得离谱,无论是考虑前缀和的贡献还是从广义二项式定理都能随便乱推,但是当时就是没想到,再加上看了眼榜还没有人过这题就错误估计了难度,扔掉后再也没想过,最难的部分被板子解决了,却卡在临门一脚。感觉对我来说可能是这场最遗憾的事情了。)

此时H交一发wa了,听说check没问题,说明是有方案的情况时输出了$NO$,问了下当仅存在两个$0$的时候被判作无解了,在纸上乱写时搞出了一组方案,然后阿伟改改ac了。

看了下榜只有C和F看起来可做,而且F的通过率极高,于是打算一起搞C。我看了下时间限制和下面的神秘快读,断定这题是在卡非线性做法(事实证明如果队友真信了去搞线性做法,我队可能就又铜了),先跟队友讨论了一波二分check方法,突然不知道为啥去看了眼F,此时F大概是过了三四队。

想了想,为啥出题人会放个这么奇怪的公式,而且通过clarification才说清楚$f_n$是不是有标号树的计数,然后把$f_1=a,f_2=b$代入算了下$n=2$的答案,发现刚好能通分到$\frac{a-b}{a-b}=1$,于是猜想答案可能是个定值或者只和$n$有关然后做了个逆天决策

设$f_1=a,f_2=b,f_3=c$,然后在纸上通分出结果

(现在想想这个问题很大,如果是猜测的话为啥不直接代入任意值代码跑一下,反正现在队友在讨论C没人上机,一下跑出来后还能多出至少半小时想K或A)

纸上写了半小时多,发现$n=3$时答案是$2$,然后让阿伟敲了个暴力,代入了$f_i=i,f_i=2*i,f_i=n+1-i$,发现都是斐波那契,遂一发ac,此时是第11个过F的队。

然后我继续去看K,C直接被阿伟一发二分答案ac,只跑了0.1s,属实离谱,不知道出题人为啥装出一副要卡log的样子。K一看就是绝活莫反,但是此时我又开始神志不清了,推了一波不考虑$lcm\ge p$的式子,上去敲了一发结果没过第二个样例($p=1$),太久没碰到莫反迟钝了,看着自己以前的写的东西重推了两遍式子,发现是只算了方案数,改了改过了样例。

然后就是在电脑面前不知道怎么满足lcm的限制直到比赛结束

后记

桂林:我超,没有数学题,挂机了

广州:我超,全是数学题,挂了

Final Fantasy的数学手,和其他队伍比起来还是太弱了。要是我再强一点,会不会有A的一血?会不会能在封榜后的1h中做出K?会不会在最后一场正式CCPC比赛中拿到金牌?还是那句话,电子竞技,菜是原罪。

自己最大的问题还是没有经过系统性的学习,只是靠着自欺欺人的所谓天赋,通过偶尔找一些资料看看、随便学一些结论、模仿着博客推一些公式来提高自己的数学水平。太多时间被浪费在没有意义的速成中,不如多花时间读读书。

CCPC金已经没了,剩下可能达到的只有CF上红了,希望毕业之前可以达到目标。