PKUWC

· · 学习·文化课

Day 1

进场，试机总时长半个小时。

写了个 A+B Problem 还有大小为 10^7 的树的遍历。发现我不会在 Linux Sublime 下开大栈空间，爆！

由 APIO 的经验电脑试机后不会清空，写 NTT 和暴力对拍吧。

写完了，没过样例，爆！怎么 OJ 上还有个试机赛？

有一个圆神题看上去像个神秘题，还有个元旦激光炮。

五分钟把元旦激光炮速通了，交上去，怎么 CE 了？

哦原来要 #include"kth.h" 啊，试机赛结束了，爆！

继续激情大战 NTT，发现 rev 数组全是 0！过了手造的小样例，也没时间对拍了。

开 A，是个 a,b\le 1000 的神秘构造，感觉是对着方案 dp 一类的东西？

哦是不是平均分就行了，这么诈骗。

B 是个树上 ds 题，第一感觉像 NOIP D，仔细一看发现和 NOIP D 一点关系没有。

发现长剖完这玩意的合并次数是 O(n) 的，离线启发式合并完了变成单点修改区间数颜色问题，可以三维偏序解决！

把带的巧克力全吃了开启狂暴写代码模式，写到一半，数据范围多少来着？

原来我写了个 O(n\log^3 n+q\log^2 n) 的东西，复杂度高达 1.2\times 10^9！

犹豫了，这玩意真能过么？

启发式合并是不是带 \dfrac{1}{2} 常数来着，四秒刚好能过，写！

诶我修改带 6 倍常数，询问带 2 倍常数，爆！

原来我要对一个 8\times 10^6 大小的东西跑三维偏序，真是太色情了。

写了一个目测 \text {5KB} 的炫酷原神大王交上去首先吃了一发 24 分暴力分致敬老大。

上一发数组开小 RE T 飞了，修完分数停留在 41，比小若智档暴力多了整整十几分，爆！

相信树状数组的巨小常数，开始使用人类最伟大的发明「上手法」。

把 sort 换成双指针之后又开始一边憋尿一边加小手法，交上去，测不出来了！

上完厕所一看，怎么通过了？怎么通过了？怎么通过了？

得出结论，树状数组是 O(1) 的，秒了！

C 怎么是 DAG 连通性，bitset 跑不动啊！

有四个样例，先写个 20 分暴力验证正确性吧。

很快把样例全过了，交上去爆！

修了几个若只错误，交上去爆！

判了连通块内随便走，交上去爆！

是不是思路错了？是不是思路错了？是不是思路错了？是不是思路错了？是不是思路错了？

虚空调试，艰苦搏斗 2 小时！

欸~~~~

你↘缩↗点↘题↗样↘例↗怎↘么↗没↘有↗环↘啊。

判了强连通分量大小为 1，过了 20。

后边不知道在舒适圈里想什么，反正思路脱不开 DAG 传递闭包。我失败的 ARC190 又开始背刺我了。

最后尝试了 n^2 过百万！！！！

剩下五分钟玩 snake 和 tetris，两分半钟就被残忍地谋杀了。

Day 1 最终获得了 100+100+20=220 分。

Day 2

六 #国 #破 #灭 #非 #兵 #不 #利 #战 #不 #善 #弊 #在 #赂 #秦 #赂 #秦 #而 #力 #亏 #破 #灭 #之 #道 #也 #或 #曰 #六 #国 #互 #丧 #率 #赂 #秦 #耶 #曰 #不 #赂 #者 #以 #赂 #者 #丧 #盖 #失 #强 #援 #不 #能 #独 #完 #故 #曰 #弊 #在 #赂 #秦 #也 #秦 #以 #攻 #取 #之 #外 #小 #则 #获 #邑 #大 #则 #得 #城 #较 #秦 #之 #所 #得 #与 #战 #胜 #而 #得 #者 #其 #实 #百 #倍 #诸 #侯 #之 #所 #亡 #与 #战 #败 #而 #亡 #者 #其 #实 #亦 #百 #倍 #则 #秦 #之 #所 #大 #欲 #诸 #侯 #之 #所 #大 #患 #固 #不 #在 #战 #矣 #思 #厥 #先 #祖 #父 #暴 #霜 #露 #斩 #荆 #棘 #以 #有 #尺 #寸 #之 #地 #子 #孙 #视 #之 #不 #甚 #惜 #举 #以 #予 #人 #如 #弃 #草 #芥 #今 #日 #割 #五 #城 #明 #日 #割 #十 #城 #然 #后 #得 #一 #夕 #安 #寝 #起 #视 #四 #境 #而 #秦 #兵 #又 #至 #矣 #然 #则 #诸 #侯 #之 #地 #有 #限 #暴 #秦 #之 #欲# 无 #厌 #奉 #之 #弥 #繁 #侵 #之 #愈 #急 #故 #不 #战 #而 #强 #弱 #胜 #负 #已 #判 #矣 #至 #于 #颠 #覆 #理 #固 #宜 #然 #古 #人 #云 #以 #地 #事 #秦 #犹 #抱 #薪 #救 #火 #薪 #不 #尽 #火 #不 #灭 #此 #言 #得 #之 #齐 #人 #未 #尝 #赂 #秦 #终 #继 #五 #国 #迁 #灭 #何 #哉 #与 #嬴 #而 #不 #助 #五 #国 #也 #五 #国 #既 #丧 #齐 #亦 #不 #免 #矣 #燕 #赵 #之 #君 #始 #有 #远 #略 #能 #守 #其 #土 #义 #不 #赂 #秦 #是 #故 #燕 #虽 #小 #国 #而 #后 #亡 #斯 #用 #兵 #之 #效 #也 #至 #丹 #以 #荆 #卿 #为 #计 #始 #速 #祸 #焉 #赵 #尝 #五 #战 #于 #秦 #二 #败 #而 #三 #胜 #后 #秦 #击 #赵 #者 #再 #李 #牧 #连 #却 #之 #洎 #牧 #以 #谗 #诛 #邯 #郸 #为 #郡 #惜 #其 #用 #武 #而 #不 #终 #也 #且 #燕 #赵 #处 #秦 #革 #灭 #殆 #尽 #之 #际 #可 #谓 #智 #力 #孤 #危 #战 #败 #而 #亡 #诚 #不 #得 #已 #向 #使 #三 #国 #各 #爱 #其 #地 #齐 #人 #勿 #附 #于 #秦 #刺 #客 #不 #行 #良 #将 #犹 #在 #则 #胜 #负 #之 #数 #存 #亡 #之 #理 #当 #与 #秦 #相 #较 #或 #未 #易 #量 #呜 #呼 #以 #赂 #秦 #之 #地 #封 #天 #下 #之 #谋 #臣 #以 #事 #秦 #之# 心# 礼 #天 #下 #之 #奇 #才 #并 #力 #西 #向 #则 #吾 #恐 #秦 #人 #食 #之 #不 #得 #下 #咽 #也 #悲 #夫 #有 #如 #此 #之 #势 #而 #为 #秦 #人 #积 #威 #之 #所 #劫 #日 #削 #月 #割 #以 #趋 #于 #亡 #为 #国 #者 #无 #使 #为 #积 #威 #之 #所 #劫 #哉 #夫 #六 #国 #与 #秦 #皆 #诸 #侯 #其 #势 #弱 #于 #秦 #而 #犹 #有 #可 #以 #不 #赂 #而 #胜 #之 #之 #势 #苟 #以 #天 #下 #之 #大 #下 #而 #从 #六 #国 #破 #亡 #之 #故 #事 #是 #又 #在 #六 #国 #下 #矣

我们有一个选手在最后一个小时内获得了他比赛的全部分数，他一定很厉害吧！

Day 17

补一个 Day 2 游记。

PKU 少出点圆，多出点分流器。

进场，怎么 A 是交互？

端详了一段时间发现增量法比较有前途，于是一直在想怎么合并答案。

想了一个同时维护三条备选直径的做法，但是细节很多，丢掉了。

想了一个看上去很对的合并三元组的写法，假飞了。

过去 1h 了！

感觉 Day 1 的 A 是签到，这道题应该也是签到！（flag）树的直径满足什么特殊性质吗？

然后就想到了一个抽象东西，大概是从一个任意路径出发的最远距离点一定是直径的某个端点。

这个东西在直径和当前路径重合的时候就假飞了，但是场上没想到，坚信这个东西一点问题没有，还以为自己爆标了，开心的不行。

写完了，交上去爆！

手模样例，发现造个梳子我就寄了，把梳子特判了，交上去爆！

加随机化乱搞，交上去爆！加特判 n 很小，交上去爆！

开始对拍，怎么 n=10 全似光了？

过去 2.5h 了！

手玩了一会发现思路假了，开始流汗。我不要爆零，打暴力罢！

把 A 扔了看 B，贪心显然是假的，除了直接贪我就只会爆搜了啊，怎么一分都没有？当时心态特别急，C 的题面根本读不下去。

A 的 O(n^3) 暴力是平凡的，但是也没分！写完了，加乱搞，交上去爆！

过去 3h 了，坏了，这场真要爆蛋了！

小声骂了两句出题人强迫自己冷静下来，发现 A 的代码有小问题，修完获得了 16 分。

看完了 C，狄利克雷前缀和板子有 32 分！光速写完后提交，没有爆。爆搜状态数是不是非常少来着，写完交上去有 44 分。获得了 60 的高分，心态稍微有点平复。

这个 B 的 c=1 可以直接贪，提交获得了十多分。带着侥幸心理尝试使用贪心通过剩余的包，交上去爆！

但是由贪心发现了一些神秘性质，导出了一个 O(n^2) 的 dp！写完了，交上去爆！

原来是 Inf 开小了，修完获得了 73 分！

距离考试结束还有半小时！

坏了没时间了，开始乱搞吧！

写了我不会证明正确性的 O(6n) 抽象做法，一下就过拍了，获得了 56 分。

后边没啥可以打的分了就摆烂了。