Day 0
今天是疯狂颓废的一天,见证了猫套+硫磺火+夜魔×4,也见证了白卡+Two of diamonds+补货。
Day 1
早上起的相当早。体验了像上文化课时候一样的拥挤的食堂。奇怪的是貌似食堂是分男女的,我们一直坐在女生食堂。食堂选择很少,质量不高。
到达机房之后,发现只有我们几个人,别人都很久之后才来。于是我随便找一台Linux坐了下来。桌面上有一个只读的“禁止列表”,包括我在雅礼时做过的升级系统等等。这个可怜的14.04已经停止支持了,为什么不让升级啊?不能理解。
预装了vim
+插件、Chromium
、clang++
(我看见了源码的.tgz,貌似是她自己编译的)等等东西,我觉得相当爽。然而在我快配置完的时候有个女的来了,说这是她昨天占的位置。所以我就走了。
隔壁机房的Linux也预装了一堆东西,包括搜狗输入法、Typora(这两个都超级有用),还有Numix主题(貌似是ys用的?)。
然后开题。一开始我不想看题,装了isympy
,发现这个低版本的isympy
可以支持readline,所以可以凭借我的.inputrc
括号补全,为什么高版本反而不支持了呢?
然后发了一个xls文件,说是账号和密码在里面。然而我这台垃圾电脑没有任何打开方式,于是只好现装了LibreOffice(因为WPS不支持32位)。
终于开始看题了。T1很像是一个我见过的原题,然而那题是序列上并且有别的性质。当时那题全场都会\(O(n^2)\),然而我只会费用流。我还没有下载板子库所以懒得写。写了一个显然的20分贪心。
我一开始以为T2的矩阵大小是\(n\times n\)的,然而想了一会之后才发现那是T3。于是我就去开T3了。
然而T3不是很可做,我想了个假算法,我没有发现那是假的,于是就开始码。然后对拍,\(n=3\)就wa了。放弃。
接下来是T2的暴力。我原来以为只有\(n=m=1\)的情况是Far Cue
,然而其实\(n=1,m=1 (\bmod 2)\)也是负无穷大。否则如果\(n=1\),\(m\)是偶数也很可做。于是拿到了10分。
这就是我全部的分数了。。。然后就开始自闭。中途我学会了把NOI Linux的终端提示符加上颜色。
中午食堂的饺子把我烫到了。没带电脑,所以只好用机房里的电脑写博客,幸亏有搜狗和Typora,问题不大。
下午是讲题,三道题的题解我居然都差不多听懂了。然而接下来的难题让我一脸懵逼,什么邻接矩阵的行列式,完全不会。
晚上咕了。我用the lost无复活打败了超级撒旦,并且通过了backasswards挑战。
Day 2
早上继续尝试登录github,然而还是失败了。下载了题目,我双击zip,看见一个down文件夹。然后我关掉了zip,发现了一个down文件夹,很惊奇这玩意可以自动解压。
于是我进入文件夹开始看题,是两道传统题+一道交互。我觉得这个交互很可做,就开始码。码了一半发现我题看错了,然后一看网页上,题目名称好像不太一样。于是我进入了那个zip里面重新查看,发现这居然不是同一套题。
我终于获得了正确的题面。先看T1,这貌似是一道sb题,就分类讨论一下即可?然后发现复杂度过高,所以我就先去开T3。这个T3让我想起了我上次在知乎上提的一个问题,唯一的区别是我问的是一个01串,这道题是排列。我很快就想到了一个很好写的n^2做法,估计常数是4到8之间,只有39分。
接下来我看了一下T2的题面,求\(\sum_{i=1}^n\sum_{j=1}^{n}\mu(ij)\)。赛后看到有人凭借IOI赛制直接二分数据,获得100分。我就不会干这种事,所以就码了20分的\(O(n\log{n})\)暴力。
我回到T1,码了\(O(nk^3)\)和\(O(\frac{n^2k}{64})\),觉得应该可以过除了最后两档分之外的全部。然而我想的太美好了,本机跑了1.9s,时限1.5s。我把pi_faster.cpp下载下来测一发速度,居然用了55s,是我电脑的6-7倍,与我的手机不相上下!这个垃圾电脑怕不是二十年前的硬件吧。所以我觉得很稳。
最后一小时我对T3做出了一个错误的结论,我以为两个随机的排列期望有\(O(\log{n})\)个相同的数,就以此为基础写了一个随机化乱搞。写完之后测了一下小数据,并没有什么提升,才意识到了自己的错误。然而我写的新算法貌似常数比较小,所以多过了一个8分的点。
最后一直abnormal的T1可以显示成绩了,却发现只有35。点进去看,发现时限是1s,我很多点都跑了1.1-1.2s。于是被吊锤了。
下午解锁了店主,然后用店主和lost各打了一局,都TM死在了该死的肿胀手里。
晚上看了一遍三道题的题解,惊奇的发现T3里面用到了不久前让snz帮忙证的一个数竞结论(完全图的最小边染色)。
Day 3
今天没有早饭和午饭,所以早上我吃了自己带的东西。
这次开题没有什么意外。发现T2的其中一个部分分是之前NOIP训练时我写了很久的一个题,所以觉得他很不可做。我一开始以为T1只能竖直发射,觉得是sb题,然后发现不太对。所以这是毒瘤计算几何,也不可做。
于是我对着T3想。首先\(a_i \le 2\)是sb,只要把原串反一下接在一起跑一个本质不同子串数即可。下面一档分是\(a_i \le 5\),接起来跑肯定是没有前途的,要用广义SAM。
然而我从来没有写过广义SAM这个东西,所以很慌。我一遍写对了SAM,后面的部分却让我自闭了。我一开始以为是按照子串长度分类,长度在5以内的乘上\(\frac{5!}{(5-len)!}\),居然过了第一个样例。我没有发现第二个样例的存在,所以就直接开始对拍。我不会\(O(n^2)\)的算法,所以我写了个sort。然而一拍就WA。
我出去上了个厕所,冷静思考一下,发现是按照子串中字符种类数分类,所以就开始重构计数部分。重构的过程中我发现了更大的问题,SAM用了450M,暴力用了190M,加起来就爆了。所以我开了一个union存放SAM和暴力。
今天脑子一直很不清醒,我没有发现只要个数相同种类无关紧要,写了一个\(O(2^5)\)的循环枚举字符种类。并且我忘了容斥。所以连小样例都过不去了。
调试的过程中我发现了不用二进制枚举,所以改成了\(O(5)\)的。由于代码变得简短,我紧接着就发现了忘了容斥。可是加上容斥的过程中产生了一个我从来没有犯过的错误。
下面是所有人都会的二项式反演,令G是F的子集,也就是\(F=\sum_{G \in F} \binom{\|F\|}{\|G\|}G\),所以\(G=\sum_{F \in G} (-1)^{\|G\|-\|F\|}\binom{\|G\|}{\|F\|}F\)。
然后我就写出了这样的代码:
for(int j=1;j<i;j++)f[i]+=(i-j&1?-1:1)*C(i,j)*f[j];
我真是个大傻逼。(应该把\((-1)^k\)去掉,因为里面是\(f\)不是\(g\))这个错调了我半个多小时。
最后我花了三个小时写这个题,所以别的题只想写暴力了。可惜的是暴力还交错题了,又被吊锤了。
下午听了题解,发现三道题的标算其实都比较暴力,特别是T3。
晚上采取和NOI同步赛时同样的方法,尝试构造网址,提前获取了明天的题目。
Day 4
早上开题,发现没有一道会做的,于是开始给手机配置shadowsocks。我没有用shadowsocks-android
,而是在termux里面pip install shadowsocks
。解决了一些兼容性问题,然而连着流量的时候,貌似手机是不能开代理的。
接下来我装了一个bb
(滚键盘滚出来的名字)。在准备运行bb
的时候忽然发现T1貌似可以线性基。然而写到贪心部分的时候发现自己是假的。仍然交了一发,获得了30分。
于是我开始bb
。这特效比我想象中的还要神奇,简直就是在放电影。完全无法想象这是1997年时的Linux程序!中途被出题人lj看到了。
既然已经是假的了,我就开始随机化。首先我正着排一遍反着排一遍,然后在calc(x^a[i])==calc(x)
时随机决定是否更新答案,随个2e5次。随机之后成功获得了70分,我很满意。于是开始赶紧码T2暴力。
我一开始以为整数三分转移就行了,然后样例WA飞了。调试的过程中我发现这个dp是有平台的,所以我在初始值上做出微调,让平台变得稍有斜率,再稍微加了点特判,最后成功在比赛结束前1分钟获得了20分。
吃完饭被lj和snz轮番疯狂嘲讽,因为我没有过T1。其实把线性基像是求第\(k\)大异或值里面那样再消一遍元就是对的了。
Day 5
为什么因为之前代码中的那个小于号,gedit
把所有的md都高亮成html了。。。(2020-08-10更新:gedit的这个bug已经被修好了)
上午我继续颓废,又拿了猫套+硫磺火。下午听snz和lj讲神仙题。其实也没有上次听的那么神仙,都是我差不多可以听懂的类型。
Day 6
xyx坐在我旁边,所以心里超级慌。一开题,发现这个T1好像是裸数据结构?然而仔细想想发现要树剖套树套树套树。。。所以先不管了。
T3又是xjoi上的原题加强版,原题是这个题的前70分。当时那个原题我们都没过(除了乱搞的人),所以也先放着不管。
T2作为一个线性代数题,一看就很有趣。然而树那个部分分完全看不透。我写了一个python脚本,求我输入的树的秩,居然找不到什么满秩的树。
一看800的部分分,就觉得复杂度应该是\(O(n^3\log{n}/64)\),这个\(\log\)是为了线段树分治求出去掉某一行之后的线性基。我就先不动脑子的码了一个线段树分治。
然后开始仔细思考对于一行,翻转哪些数会改变秩。这个显然要分两种情况考虑:这一行可以被其他行线性表出,和不能。可以被线性表出的部分貌似比较好做。
我再想想,发现这个貌似需要用消元过后的线性基。然而我之前只会写把一个已有的线性基消元(这会使复杂度退化),不会一边加入一边消元。所以这里我写错了三次。
所以说,如果可以被线性表出,所有一行只有一个1的行就是答案。这个显然。否则还要分两类讨论,就是已经被消掉的部分和剩下的部分。都是可以发现规律的。
然后就获得了0分?我以为我的算法是假的(毕竟不能完全证明),然而调试一会发现是消元写错了。
最后我花了两个小时拿到了50分。接下来我码了T1和T3的暴力,貌似已经成为得分最高的一天了。
决定放弃继续做题之后,我登录了之前的账号,搜索70分代码。然后找到了我们学校的czy和(貌似是)lzq的代码,交上去,可惜都T成40了。所以说这个70还不完全是当时那个题?
当然,作为一个有素质的人,我最后交的是自己的暴力。
下午自闭the forgotten。
Day 7
这天早上起晚了。上午开题,一看貌似三题都不可做,然而仔细思考了T1,我猜了一个结论,是真的,然后就DAG求最长路即可,所以就把它过了。这是我这几天唯一过的一道题。然而T2和T3是贪心,我猜的都是假算法,所以只拿到了T2的暴力分,T3暴力不想写了。
晚上看了Missing HUD 2的源代码,懂得了很多东西。然而不知道为什么游戏中要把range属性记成相反数。
Day 8
这次是snz的题,是最自闭的之一。首先看T1,这是一个反演题,我貌似在洛谷上见过类似的要反演套反演的题目,对于这种题我一直只会\(O(Tn^{\frac{2}{3}})\)的做法。所以我就写了它,并且从20s卡到了3.2s,评测机上只要1.2s,然而还是过不去。lj也写的这个。
然后是T2,这个强制在线很弱,因为异或上的lastans最多有两个值(对于?
操作是\(0/1\),对于-
操作答案最多增加\(1\))。于是我开始思考一个乱搞,就是先根据-
操作的两个数一定在边集里,确定每次删的边,然后离线搞搞就完了。然而错误率有点高,所以只拿到了暴力分。
完全没看T3。虽然我看过snz的题解,然而还是不可能会做。
下午发现全场都过了T1,而且snz说这是套路,然而我完全没见过。
火车上看xyx用the Lost过Hush+Delirium。最后的总结:这真是以撒八天乐。