ZJOI 2019 Day2 游不动记
点击量:647
Day 1
在余姚中学待了一周多,还没去看过五楼报告厅。报告厅还是比较宽敞的,还有 LED 屏幕。
上午是 zzy 讲《树上分治算法》,分别讲了边分、点分和全局平衡二叉树。讲的很快,例题引入比较跳跃于是成功在开场 5min 掉线了。
课间放了 THU 的计算鸭小视频。由于奇特的动作特征(???)而面基到了 Sugar 大爷。
杂题选讲部分主要是图论,难度看上去比较大,感觉总是在反复用一些套路。知识点欠缺的确有些多。
中午和 Dew, xht37, Sugar 吃饭,小碗菜挺好吃的。出来之后买奶茶的时候一位歪果小姐姐要 a little Sugar,然后我们出于惊恐就散了2333
下午 samjia 和 zzq 继续讲杂题。稍微恢复了一点思考能力,但是还是秒不掉任何一道题。不过至少能听懂一点了,看来需要一些康复计划了。
17:00 结束讲课,17:30 试机。吃饭的操作非常不现实,于是决定试机完了再吃。不过走过去的操作也不现实,路程要 20min,并且还不知道机房在哪..于是准备骑车过去。
Dew 找到了电动车,我和 xls 骑自己动手丰衣足食的自行车,还是晚了几分钟到达了考场。
到了之后首先发现显示器高糊,但是 hp 的显示器一定是可以瞎搞的,于是自动调整给它修好了。只提供了 Dev-cpp 和 GUIDE,配置并不是很高,而且不知道评测用机是什么配置。
突然回归正常键位的键盘有点不适应,毕竟在余姚中学机房的某某某方键盘键位极其奇怪。
打了漏洞百出的 Dinic 之后终于调过样例交上了。后来研究完各种配置之后,想起来可以打一个 exCRT。但是 Dew 说电动车临时停车也要按时间扣钱,于是让我们尽快试完走人。
回来的路上找到了可用的电动车。骑着还是很舒服的,貌似还可以用脚蹬来发电。
晚上在万达吃吃吃。
22:35 是 CF #554 Div.2。想起来 ouuan 等人的比赛想要 #555,问了一下发现并没有轮到。
首先,前 3min 看不到题是惯例。然后发现 A 直接统计奇偶计算就可以了。
B 的 40 次操作感觉可以放飞自我了,然后好像异或的时候位没有控制好 WA 了一次,然后 pp 了。
然后是天诛地灭的 C。一眼贪心,感觉凑到 $|a-b|$ 的倍数就可以了,样例过了却一直 WA on 4。一直举不到反例,调了其他错误也还是 WA。最后大义凛然地扔掉了 C,去看了 D。
D 看了半天不知道是什么,以为是个求括号匹配方案数,打了记忆化递归之后才发现题意理解错了。翻译了题目中的一个括号才知道是把所有合法序列插入 trie 后,求最大边独立集的大小。
感觉可以按点贪心,于是记录下每个深度有多少个点就可以了,计算每个深度有多少个点可以 $O(n^2)$ dp。就差不多做完了。(直接贪心应该是对的吧
回去看 C 突然想起来,最大的 $\gcd$ 是差值,但是更小的 $\gcd$ 也许可以造成更优的解,于是开始 $O(\sqrt n)$ 枚举约数。
又想起来要求加上的 $k$ 尽可能小,于是套了两层最小值就水过去了。
最后剩下 20min 的时候开始尝试 E,感觉很有意思,不过一时半会分析不出来,就去看了 Room。
发现我暂时是 rk1,所以只能叉后面的人来涨 100 之类的。
看到一个 C 码长很短的 python,把核心代码放到本地跑却一直 CE。最后一分钟头铁扔了组数据上去…最终还是挂掉了。
快结束的时候 xls 和 Dew 都表示只写了 AB,还是有些担心自己 fst 的。还好最后没有。
Day 2
Day 2 游不动了(bushi
早上换了一家面馆,好像猪肝有点咸…
上午第一部分讲构造题,感觉很可听。不过神仙切题好快啊..感觉自己只能暴力构造,很多套路都不会啊。还有好玩的推箱子???整个课件里题目的来源都是 CF,还是 CF(不是 CCF)的题最有意思了。
第二部分是杂题选讲,但是貌似是春眠篇。为什么上来就置换啊…送温暖题还没看懂怎么就跳了。
有一个题是前几天 samjia 讲过的,又听了一遍终于听懂了暴力怎么写。貌似讲题人把 $\theta$ 跟 $\Theta$ 弄混了,看复杂度的时候一脸懵逼。
然后 PPT 的对比度有点强就很催眠了…
中午小碗菜仍然好吃啊啊啊为什么没早点发现这个地方
下午还是杂题选讲,感觉已经对杂题选讲这四个字有阴影了。
讲题人是 70245258。XD
貌似搬了很多 CCPC-WC 的题过来,一开始虽然想不到,但是也不是很毒瘤。
好像节奏有点快,给的思考时间比较少,在题解页面停留的时间比较多,不是很习惯。偶尔掉线再断线重连也是可以的,不过画风逐渐变得奇怪了…
首先是求 $n!\bmod p\ (n,p\le 10^{12})$,看题解上去是比较清真的分块倍增和插值。
然后是调和级数 $\left(\sum_{i=1}^n\frac 1i\right)\bmod p$ 取模输出,同样用到了分块倍增。
还有一个 $\left(\sum_{i=0}^n\mathrm C_n^i\right)\bmod p$,继续分块倍增。(好毒瘤啊但是好想学
于是 $\mathrm C_n^m\bmod p^c,pc\le 10^6$ 就开始话锋画风一转,突然化式子转多项式插值,跳满。
剩下全篇讲 min_25 相关,“您被房主请出房间”。
晚上啥都没整,改了一下前一天的煞笔题 E,顺便复习了一下欧拉路,好像又懂了一遍。被 KS 拉去打雀了2333然而手气真烂。
Day 3(真·Day 2
早上为了节省时间啃的面包。发现那边可以停电动车,然后找车骑了过去。路上看见一些(戴狗牌的)老哥怕是要迟到2333
差不多在 7:57 到了考场(怎么每次都这个点啊 我到底算不算鸽了)
开场看 T1,大概是这几天养成的习惯。一题一题的做不会太乱,虽然之前听说过难度是乱序的,但也不至于暴力都不会打。
然而真的暴力都不会打。写了两种转移,其中一种显然错误,另外一种在写完高斯消元之后发现有些不对,改不出来了扔了。甚至 $n=2$ 都不会写。
T2 是树上的一个问题,$O(n^3)$ 很显然,但是一直套不上 $O(n^2)$。也扔了。
突然发现 T3 好像可做,$x$ 是非负整数感觉会方便枚举。它们斜率都是正的,所以到最后会分散,那么就按 $a,b$ 分别为关键字排序。然后排名只可能有两种。
后来看大样例的时候发现排名不止两种,然后想到了三线相交的情况,于是开始往几何方面想。$O(n^2)$ 很快出来了,并没有考虑其他的细节,调了一会大样例就过了。
看到 $m=1$,想维护一个半平面交,然后那些最紧的限制条件就是答案。不过斜率都是正的,交不回来的,所以单调栈维护一个下凸壳就能搞定了。如果栈顶的点在线上要保留,因为并列也是算贡献的。
写完了发现 $x$ 是非负整数这个整数是个坑,改了改没过拍,看到时间不够就又改回来了。留了一个小时给前两个题,当然第一题还是弄不出来。
T2 $O(n^3)$ 暴力应该也挺好打。这时看到了链这个特殊情况,感觉要分别维护区间取较大值较小值、查询区间最大值最小值,需要两棵线段树。在写 T3 的时候就发现 debugger 不好用了,甚至打不开。T2 一直 CE, CE, CE,然后快调好的时候发现只需要维护最大值,12:55 火速打了个差分过了自造数据。
然后发现 T3 有个输出格式不对,调了一下。
出场没有正式考试的压力。想起 NOIP 的时候的不够清醒;想起 WC 一直纠结 T3 是什么操作;想起省选出来后的迷茫。但是这次出场就像平常下课一样。或许是根本没有压力,不过这样并不好,还是得有点追求的。
貌似有很多人甚至没有注意到 $x\in \mathbb N^*$,然后 Dew 和 xht37 都没有整出 T1 的高斯消元,但是总觉得是个什么套路。T2 据说可行的做法很多,好写的不知道有哪些。
事实上三道题看上去都不是很难,但是又感觉很陌生。
中午吃了黄焖鸡米饭,(怎么这个 lsy 现场催更啊)下午随便收集了一下资料,考虑了一下 HB Round 1 的事情,就睡觉了。
晚上买了自热米饭和自热海底捞(?这东西没吃过明天试一下)准备当明天在火车上的的晚饭。
打了一场路人雀,貌似手气还不错,洗完澡又和 KS、Dew 玩了一局,然而并没有开胡2333。
所以这次难得的 ZJOI 之行也到此结束了呐。
upd on 4.29
数据出来了
$0+60+40=100$
排正式选手里 rk120+ 了
orz wjy
orz wjyyy
orz wjyyy