ZJOI 2021 游记

# Day -4 补了一下去年的联合省选A卷.(下降幂都不会的我实在太菜了) # Day -3 继续补去年的联合省选A卷. # Day -2 鸽了文化课,vp了CF809,垫底了.然后冲去吃饭.下午补了作业题(矩阵树定理).晚上想冲[魔法商店](https://www.luogu.com.cn/problem/P6621)但是不会(逊爆了). # Day -1 上午不知道在干嘛,看了一上午的线性变换与矩阵,出发之前想冲点分治没调出来(是新学的),还忘记拿行李了.回到寝室带上行李箱,然后就匆匆地上车了. 车上和CE_WA_TLE一直在冲33iq,升了好几级来着. 下午大概3:00的时候就已经到宾馆了,我们住的DJ大酒店.于是就应该DJ.然后各回各房间去打[gen](https://generals.io)了(只有手机打不动呜呜呜). 我和CE_WA_TLE一个房间,因此他跟着我回到了房间里.我们继续33iq(雾). 实际上是我占用了CE_WA_TLE的电脑来打间,和QwQcOrZ一队打了两把,然而我太菜了,没几回合我就挂了,因此等待别人的时间,我在CE_WA_TLE的引导下看起了魔吧([魔法禁书目录吧](https://tieba.baidu.com/f?kw=%E9%AD%94%E6%B3%95%E7%A6%81%E4%B9%A6%E7%9B%AE%E5%BD%95)).结果打到第三把时,QwQcOrZ不见了. 我发觉他不对劲,于是就冲去他房间里.发现他在偷学. 偷的还是矩阵树定理([P6624](https://www.luogu.com.cn/problem/P6624)),我让他不要在偷了,他说他在PVZ. 一看,他还真在PVZ,打的是95版的僵尸快跑(之前我用1437阵过过这关,并且没有丢车,有一说一如果想不丢车不开挂的话还是比较难的).然后他就丢车了. 我说他不行,我来,然后就接手又复盘了一次我之前的通关方法. 然后QwQcOrZ去打锤僵尸了(我过不去,单指CPS只有6),我过不了他居然过了.然后就去比CPS了... 我们冲CPS的时候,一旁带了"装修工具"(装了大半瓶自来水的大号冰红茶)的CE_WA_TLE开始"装修"(利用在桌面上缓慢移动"装修工具"来引起共振来起到发出装修声的效果)了.实际上,他从两周前左右就已经研究出这个工具并教给我们了.~~因为这个,我,QwQcOrZ和CE_WA_TLE还被众人ARB了.~~然后我们反手抢走了他的装修工具. 玩完电脑大概已经快6:00了,该到吃饭的时间了.我们(我,QwQcOrZ,Froggy,exzαng,Limit,yuzhechuan,CE_WA_TLE,hezlik,...)一起去天街吃晚饭.路上exzαng问我平面图转对偶图怎么做.我跟他说要先对每个点的所有出边分别进行极角排序,然后找一条还没有归属任何平面的边,逆时针遍历出一个新的平面,随后将每条边所属的平面与其反向边所属的平面连边.他貌似听懂了. 到天街发现要健康码,然后exzαng,QwQcOrZ和hezlik就因为忘记带健康码而回去取了.Limit等人与yuzhechuan先进去了.我,CE_WA_TLE和Froggy等了一会,便等不下去,也进去了. 这是我第一次来到大城市里的商场,真令人新奇!商场里情侣随处可见(?)~~,还有一些好看的小姐姐~~.最令人好奇的是,门口进来那个指导器居然还能随着人的移动而旋转! 瞎jb逛了一圈,想要去找yuzhechuan和hezlik一起吃晚饭,回到门口等到了hezlik,然后Froggy又打电话和yuzhechuan会合.于是我们5人就去吃火锅了. 那天吃的火锅很烂又很贵,被我们戏称"四流火锅"店. 回去后瞎jb复习了点东西:Tarjan,字符串~~,33iq(?)~~. (题外话:对于任意四边形里较长三边长度之和必定大于两条对角线长度之和吗?) 然后就睡觉了.(睡觉都在MJ的CE_WA_TLE是泄) # Day 1 ## 考前 早上起来又去了一趟Froggy的房间把QwQcOrZ叫醒了.然后7:00去4F吃早饭. 吃早饭的时候顺便嫖走了所有橙汁. 到考场的时候已经到了8:00了.刚好开始排队入场. 入场之后周围的人全部开始码代码了,于是我也码出了缺省源并测试了环境----一切正常. ## 8:30 开始了,解压密码输错两次还被婊了一波,最后到白板前抄了下来才解压出来. 看到题目第一眼感觉T1能A,T2特殊性质全部能拿,T3只会16分暴力. 感觉良好,然后开始想T1. 我构造了一个函数$f(i)$表示i为最小值时最大值最小是多少.写了个$O(n^2)$暴力看,显然这个函数可以$O(n)$求,是增函数,且肯定是选择$a_j<i$的所有牌进行翻转,若翻转后最小值依然小于$i$,那就不可行了,返回$INF$,否则肯定是再选择前$k$大的$a_j$进行翻转. 开始的时候还在想怎么二分答案,即求$f(i)-i$的最小值,但是貌似并不可行. ## 9:15 于是就开始想由前推后的做法,即由$f(i)$推$f(i+1)$,然后就发现可以用`two-pointer`过掉这题.而且为了保险起见,我还写了个超级堆来维护集合里的最大值和最小值.大样例过了,和暴力写了一个拍,然后就一直在拍了. ## 10:00 写完T1大概就这个时间了,赶紧开始看T2,感觉$n,m\leq3$好写点,就分类讨论一下即可,然后就开始分类讨论,写了大概毛$200$行算是写完了.思路大概就是$n+m=4$时直接填满$a$;$n+m=5$时可以尽可能大地把两个$b$共有的部分填了,再处理另一边多出来的部分,$n+m=6$时可以先尽可能大地填中间的格子,再枚举其中一条棱,接下来顺推出来棱长,最后填角块(后面这个做法假掉了). ## 10:30 接着冲T2,看到第二个包$m=2$,就感觉可以变成序列做.我又感觉这个东西可以利用判断$a_1$是偏大还是偏小来二分$a_1$,但是这是错的(并不能判断偏大还是偏小),我还傻乎乎地以为是对的,看$0\leq b_i\leq1$去了. ## 11:00 还剩下两个小时,感觉$0\leq b_i\leq1$用`2-sat`(也是假的)并不是很好写,便去冲掉了T3的16分暴力,测了一下大样例,居然跑了二十余秒,还把风扇转起来了,估计整个考场都能听得见吧. ## 11:30 时间不多了,感觉有时间冲出之前的`2-sat`,但是在这之前,应该先写拍.于是就写了一个spj,又写了一个只有`YES`数据的mkdata,一拍$m=2$的点.没几组就萎了,很快嗷,当时就燃起来了.一想,原来是做法萎了.于是赶紧推了推式子: $$ \begin{cases} a_2=b_1-a_1\geq0\\ a_3=b_2-a_2=b_2-b_1+a_1\geq0\\ a_4=b_3-a_3=b_3-b_2+b_1-a_1\geq0\\ \vdots\\ a_n=b_{n-1}-a_{n-1}=b_{n-1}-b_{n-2}+b_{n-3}-\cdots-(-1)^na_1\geq0\\ \end{cases} $$ 因此有不等式: $$ \begin{cases} a_1\leq b_1\\ a_1\geq b_1-b_2\\ a_1\leq b_1-b_2+b_3\\ \vdots\\ (-1)^na_1\leq(-1)^n(b_1-b_2+b_3-\cdots-(-1)^nb_n)\\ \end{cases} $$ 那我找出$a_1$的下界模拟一遍作为可能答案就好了(貌似现在又假了?). ## 12:30 继续拍$n,m\leq3$,发现$n+m=6$的做法萎掉了,然而我时间已经不剩下多少了.我发现萎掉的概率非常小,而且也没时间改了,于是就放弃等待死亡了...... ## 考后 收卷了,旁边的人立马开始讨论起他们的AK做法,什么T1线性做法啊,T2差分约束啊,T3 $O(n)$做法啊.只有我一个人,一个讨论对象都没有. 出了考场,MicroMaker超AK地走过来,说:"你T2A了吗,CE_WA_TLE A了!"我当时直接就懵了,说只打了一档暴力,大概算了一下,只能有$100+30+16=146$. 然后就是接下来一系列的互相问分,因为我爆蛋了,所以我没参与.MicroMaker家长来问我,我没回答他. 午饭在天街周边的面馆吃的,吃了青菜肉丝面+荷包蛋,14块.吃完饭直接回Froggy房间已经是3:00了.然后整个下午都在颓废.大致开始时是在打斗地主,然后开始乱七八糟的电脑三人小游戏,接着是看QwQcOrZ和MicroMaker下[国际象棋](https://lichess.org/T27BD9Hn/black),看完继续打斗地主,打完后还和MicroMaker一起推广了一下音游(如deemo,钢琴块(?)),接着就去吃饭了. 吃饭在酒店东方(要素察觉)的麦当劳吃的,点了96元,一个随心配+一个三人餐,亏得一批,还不如8个随心配.而且那个奶茶配纸吸管口味就跟shit一样,食之无味弃之可惜.回到Froggy房间之后还发现书包忘那里了.来回大概又跑了十来分钟. 再次回到Froggy房间时,已经快8:00了.Sigma和Flower恰好在房间里,聊了一会儿考试要注意的点之后就离开了.然后又颓废了3个半小时,还顺便把赛马娘的大概玩法搞懂了. 然后就回去睡觉了,到这里貌似心态并没有爆... # Day 2 ## 考前 如昨日一样,也嫖走了所有橙汁,然后就去考场了. ## 8:10 进考场立马开始码缺省源和对拍,数据生成器写到一半发解压密码了. 这次居然一次就输对了密码,真是不可思议. ## 8:25 不知道为什么提前5分钟开始了,打开题面一看:T1树上路径问题,T2状压DP,T3支配问题(之前在kcm1996的题目里看到过板子).感觉良好. ## 8:30 一遍题目看下来,T3果断弃了,先冲T2正解试试.(这时我题意理解的是合法的$b$序列方案数) 显然最暴力的做法是用$dp[i][j][k][l]$表示一共已公布$i$个题目,当前的第一名做了$j$题,第一名是$k$,已公布$b_o$的队伍的集合的方案数.然而这无论是空间还是时间都过不去,光状态就有$500\times500\times13\times2^{13}=26624000000$种,这显然是无法接受的. 考虑先从差一点的方法开始?我码了半个`dfs`,结果发现`dfs`都拿不了$60$,于是跑路去T1了. ## 9:00 看看T1怎么做,我先想了想暴力的做法,对于每组询问把$s$作为起点`bfs`一遍,这个做法是$O(nq)$的,但是它可以一次性处理所有$s$在同一个点的询问,因此我想到可以同时处理所有询问.并且一出现$\sum_{j=1}^n[w_j=p_i]\leq\sqrt n$时,可以直接暴力,这时效率是$O(n\sqrt n)$的,并不是不能接受. 因此我想到是不是可以根号分治,考虑出现次数大于$\sqrt n$的$p_i$,可以直接倍增找,这可以用`bitset`存起来,空间$\frac{200000^{\frac32}\times\log_2200000}{8}B=187MB$,可以接受. 于是我便开始码,码了近一个小时后调过了样例,修好了$\sum_{j=1}^n[w_j=p_i]\leq \sqrt n$时的情况,但是$\sum_{j=1}^n[w_j=p_i]>\sqrt n$却调不出来了,还是大样例才萎. ## 10:30 然后我写了一个拍,却拍不出数据,直接自闭. 我心想:就放那里拍着吧,该萎的总会萎的,到时候萎了再去看就好了.(然而到比赛结束都拍不出来数据)然后就去看T2了.又对着错误题面写了半个小时`dfs`. ## 11:00 输出了$b$的方案才发现题意读错了,人直接崩溃了.好不容易才改对,又以为样例二太大过不去,就回去看T1了. 想到可以枚举排列,于是又花半小时写了一个$O(n!n)$的做法,输出和原来的`dfs`完全一致,就当我以为我A了的时候,我测了一下样例二,输出了`124`,直接燃起来了. ## 12:45 调了好久还是没发现问题,猛然间才发现时间距离比赛结束只剩下$15$分钟了(当时我以为比赛结束时间是$13:00$,但是实际上是在$12:55$结束的).整个人都不好了. 就当我感觉我快要调出来时,$10$分钟刚好到了,比赛结束了.我直接满脸问号了... ## 考后 我人直接傻了,回去的路上一直在赛马娘. Day2 期望$25+0+0=25$分,直接屈辱退役. ---- 撰写于2021.4.12.