THUPC2019&CTS2019游记&APIO2019场外记

由于某些原因并没有参加APIO。
Day0
前一天晚上做硬卧到北京参加THUPC，因为我也不知道的原因，早上四点多就起了。
头晕乎乎的，但就是睡不着。
队友supy,panole，cf rating都吊打我。
开场supy拿$2^n-1$爆了三发D，一开始没开unsigned long long也没特判0，但是改对后还是WA了，心态有点小崩。
换panole上去一A了M。
然后panole 2A了B，因为一个else的缘故挂了一发。
之后supy发现了D不是$2^n-1$，搞了搞就过了。
接着队友会了C，写到一半让我先写L。
我写了一发双向链表，感觉输入要T，就顺手加了个fread，居然有一血。
几分钟后队友过了C，这时大概过了一个小时，好像暂居rk1，有点膨胀。
还有记者来采访为什么先做L，答“因为倒序开题”。
之后panole秒了I就冲上去写，因为IO格式一直WA。
中途我上去写了个J，一开始数组开小挂了一发，真丢脸。
发现IO格式挂了后，I就过了，这时大概是开场140分钟。
supy说会了F。
panole说他会了H，而且半小时就能写完。
因为某些神秘力量，我们决定先干F。
中途算法假了几次，我闲着没事的时候发现K好像能做计数，FWT+矩阵树即可。
趁着supy调F的间隙，我去写了发K。
结果一开始还因为忘加IFWT挂了一发，真丢脸。
还剩四十多分钟时过了F，居然有一血。
全队开始rush H，因为蜜汁错误(upd:好像是检查吃子的函数参数弄错了)没弄出来。
隔壁txc队好强啊，半小时写完H一发过。
最后好像rk5+两发一血。
Day1
上来顺序开题。
发现T1以前好像在哪里见过二维并且k=1的版本。
反正xjb容斥就行了。
于是冲上去写了一发，改改改，改改改。

空调温度怎么这么低啊，冻死了。
感觉思维严重受限，全身瑟瑟发抖。
别人上厕所都是跑过去的，就我是散步过去的，因为要在室外晒太阳来回血。

一个多小时过去了。
还是爆零状态。
于是去补了个T2的$O(Dn)$和T3的第一个点。
回去继续刚T1。
感觉三维比较难调，于是写了个二维的版本并且和指数暴力拍上了，然而没什么用。
有去补了个T2矩阵快速幂，本地11s怎么可能有分。
回去看T1，想把容斥扔了改写30分暴力。
发现转移有八种，根本写不动。
心态崩了。
要吃铜牌了。
突然发现T1有个八项式可以优美地写成三个二项式乘积。
改改改。
竟然就过了小样例，士气大振。这时大概还剩一个半小时。
然而现在是两方的，不过好像有一方可以通过递推计算干掉。
干掉之后发现瓶颈在$O(nml)$的组合数上。
第一反应是既然单点12s，那就把阶乘离线下来，$O(998244353+Tn)$来做。
不过好难写啊，std不会这么丧病的吧。
猛然意识到有个东西叫约分。
一波操作后组合数没了，不过还有个求逆。
大样例要跑几十秒。
改成$O(n+log998244353)$求逆之后好像还是要11s。
优化了一下一个$O(n)$的组合数式子，好像只用6秒。
还剩40分钟，我有158分。
赶紧rush提答，写了个把所有矩形摆成一排，还只能做tp=1的垃圾贪心，后八个点喜提总分四分。
手玩了会第二个点，拿了个9分跑路。
回去补了下T2 m=0和m=1。
然后就只剩不到十分钟了。
100+56+（10+9+4+0+0+0+0+0+0+0）=179
咋比去年还低一分啊。
试图魔改提答的贪心，好像第三个点可以拿五分。
然后就响铃了。
出来遇到fyl，说他2.5h切完前两题，总分245。
遇到ftq，说T1他一个多小时就切了。
遇到yhx，说他T2 1h就切了，T3 90分钟70+，总分200+。
遇到cwy，说他总分217。

根本不给我这种弱者生存的空间。

下午出分后发现没挂分，行吧。
讲题时听说T1只过了15个，有点小吃惊，那我可能还有救。

Day2
好好考吧，顺其自然即可。
Day1没那么差（吧），也没啥翻盘任务。
GL&HF。

开场看T1，发现是计算几何。
猜了一堆性质全部叉掉。
结果忘记还可以拿假性质写乱搞，我真菜。
一个多小时过去了。
弃疗看T2，我会10分！
可能还会个30分吧，不过好难写啊。
再去看T3，naive地以为每条边是独立后，想了些假算法。
开写前先写了个$O(3^n\ast n)$的假暴力，样例挂了。
冷静了一下发现每条边不独立，鈤。
连忙写了个$O(2^n\ast n^2)$的暴力，好像能过大样例。
抢救了很久还是失败，大概过了三小时吧。
回去看T2，发现可以KMP自动机，之后的思考过程在这里。
写完后一遍过大样例。
但是码长怎么才1K啊？
虚得很。
去搭了个拍。

回去刚T3，发现一朵菊花的内向树要猎人杀，鈤。
众所周知猎人杀是容斥做的。
想了想，以为std是树形DP+转移时使用猎人杀。
然而直接对边容斥就行了，我真菜。
回去看T1，发现我会额外的十分。
又对T1做了个转化，发现转化后的东西不会做。
还剩10分钟时，去把T1的那十分补了。

出来后zjc说T2肯定要考虑m和n的大小关系。
我突然发现我拍的全是m=n。
那我爆零稳了，跟去年D2最后一分半拍停，出来后发现忘判无解后，一样的心情。
弱小，可怜，又无助。
但是这次我的算法是能严格证明的啊？
等出分吧。

查分时发现T2没挂，T1“至多两条曲线”还可以是一条，判挂了，掉了5分。

两天总分179+155=334。
居然有rk6。

但感觉其实考试过程不是很顺利。
每天前两个小时都是爆零状态。
如果两天我A的题都没搞出来并爆零，那么理论下限是58+60=Cu。

好像提答题送命的魔咒一直去不掉。
CTSC2018D2T3得分21
THUSC2018D1T3得分35
THUSC2018D2T3得分14
CTSC2019D1T3得分23
正式考试提答永远40-

造成这一严重的事实的部分原因是提答不会挂分，而且掌握一定套路后难度也大多比较低。
也就是说做提答比较稳（虽然THUSC2018两天的提答好像是反例，但可以预见到NOI如果也出提答，那么必然是送分型的）。
相对的，那种需要占用大量时间去刚的传统题就得分很不稳定了。万一没调出来呢？真.赌博。
不要把偶然一次的运气当成必然。

为自己感到深深的担忧啊，NOI也提答送命怎么办？
提答快速收割分数的水平还是有待提高。

Day3
闲了一天。

Day4
跑路回家了。

Day5
咕咕咕

Day6
上午听说zzq一个半小时AK。
晚上问txc要了下题，发现T3直接树套树，或者cdq分治也可以。
然后T2他跟我说是签到题就没看了。
T1好像对时间分块非常明显，而且常数应该挺小的吧，也没有log。
然后跟txc交流了一下发现他多了个按秩合并并查集的log也过了。

Day7
txc跟我说T2签到题很多人没过，直接吓傻了。
看了眼T2后发现不会。
冷静了一下好像$[F(x)=F(y)]=[x\mathrm{m}\mathrm{o}\mathrm{d}(a\ast b)=y\mathrm{m}\mathrm{o}\mathrm{d}(a\ast b)]$
（upd:好像不是a*b，反正不在场内，也没啥影响？）
然后就个模意义下的区间覆盖。

感觉APIO**也不是很难？
不过也没啥意义，又不是NOI。

听说下午讲了很多树上线性算法，听上去很有趣啊。
可惜没发课件。

Day8
写这篇游记。

最后

以上就是鳗鱼黑米为你收集整理的THUPC2019&CTS2019游记&APIO2019场外记的全部内容，希望文章能够帮你解决THUPC2019&CTS2019游记&APIO2019场外记所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。