jiry_2's Blog

之前去雅礼嘿嘿嘿了三个礼拜，最后还被XY强行报上了HNOI然后被六道大数据结构翔了一脸..

在原来的博客上随便改了一下，就当是游记了吧2333

【SRM688】

先发几张图随意感受一下：

T1一道几把细节题，样例给了和没给一样..

T2一道几把细节题+码农题，样例给了和没给一样..

T3一道noip傻屌DP题..

考完之后的感觉就是

不是很懂你们这些TC出题人啊..

这TM已经不是1000比500简单了啊..这TM比250还简单啊..

那些A题不会搞的小哥，你们哪来的自信搞C啊..为什么TM这么熟练啊..

好不容易熬夜搞个一场SRM，这怎么就给我塞了这么大一坨翔啊..

MD当初TC出那道构造生成树的题，我怎么就轻易的就睡觉去了啊..为什么TM这么熟练啊..

之前和鏼分工的时候怎么轻易的就接了500的锅啊..为什么TM这么不自信啊..

算了一下TM我开场肛C题TM就target了啊..AB这两道几把我去做他干嘛啊..

为什么TM这么不熟练啊..

现在TC这个垃圾网站除了原题搬搬分数乱标还会干什么啊..这TM和隔壁CF有什么区别啊..

明天打什么HNOI啊..现在睡什么觉啊..

以上是当时晚上意识模糊情绪激动瞎写出来的东西..好像在CF上随手发了篇博客就骗了40+的contribution。

现在冷静下来之后一句话总结一下那场SRM：cnbb，mdzz。

【HNOI2016 D1】

睡了四个小时就起床了..被闹铃吵起来的时候已经有点神志不清了..

跑到雅礼门口的时候发现雅礼的校车狗带了..最后myy带我们飞，蹭上了myy爸爸的车去考场..

在考场下面围观湖南众面基，然后发现自己什么人都不认识..论老年选手的自我修养233

进考场之前听说有小哥的座位夹在myy和yyt的中间，只能点蜡+1s了。

打开题目发现三道数据结构题感觉非常爽，还好没有浪费时间看板子..第一题一副魔法森林的感觉，第二题感觉大分治一波总能搞吧，第三题咦这不是xyz的angry tree吗，这五个小时怎么写的完啊..然后就直接把第三题丢进垃圾桶了，开始慢悠悠的写前两题。

第一题想了一下发现LCT好像不是很兹瓷啊..随便脑补了一下感觉按秩合并的并查集常数很小的样子，然后就开始自信分块了。

我当时的做法是按照[tex]a[/tex]的权值把边分块，保证每一块中除了最开始的一部分权值相同的边以外的边数都不超过[tex]\sqrt m[/tex]，之后分别处理[tex]a[/tex]的权值在每一块中的所有询问，可以按照[tex]b[/tex]排序，设这一块中最小的[tex]a[/tex]的值是[tex]limA[/tex]，把所有[tex]a[/tex]的权值小于等于[tex]limA[/tex]的边按照[tex]b[/tex]的权值依次加进去。这样处理每一个询问的时候至多会额外加入[tex]\sqrt m[/tex]条边，因为涉及到撤销，所以要用按秩合并的并查集，时间复杂度是[tex]O(n \sqrt n \log n)[/tex]。

和暴力拍上之后测了一下极限数据，发现只要跑0.6s，然后就非常自信的不管了，连块的大小都没有调。最后出考场才发现原来是我dtmk写炸了：考场上为了保证Yes的出现频率设定了边的权值只有20种，在生成极限数据的时候并没有改权值种类233。成功地错失了一次调参机会，可喜可贺，可喜可贺。

第二题看到题面先无脑上了一波分治，然后又无脑上了一波虚树..之后就开始意识模糊瞎JB暴力了..根本没有当初noip考场上的智商了2333实际上和noip那题一样把所有限制排序然后维护链的交扫一边的就好了，然后考场上意识模糊不知道在干什么。因为一条链不经过一个点的充要条件是：这条链的LCA不是这个点的祖先或者两个端点都在子树外。第一部分可以直接在虚树上暴力DP，第二部分可以求DFS序然后二维数点，这样时间复杂度就轻易的[tex]O(n \log^2 n)[/tex]了。因为都是非常暴力的东西所以代码虽然长但是写起来非常爽..

然后我的老年人分治就被湖南的评测姬卡常数啦，本来用倍增求LCA发现随机数据轻易的4s了，然后最后半个小时改成了树剖求LCA总算是卡到了2.3s，随便测了一下发现二维数点部分随便sort一下再树状数组一下就1.5s+了，简直不知所措..

第三题最开始看成x大爷的鬼畜题了，那题的链接在这儿：

http://acm.hdu.edu.cn/showproblem.php?pid=5300。

最后发现这道题可做的时候已经只有一个半小时了，第一题和第二题还没有测极限数据，因为不是很敢玩火，所以只写了30分暴力。然而当时又困又饿，暴力写的意识模糊，过了半个多小时才过样例..

出考场发现好像大家都写了两道题，好像我们四个人把三种可能的写法都占齐了233

吃了饭之后汪嗲在旁边的高端宾馆里开了间房间..然后我们就开始网吧四连坐肛胡测了..

【集训队胡测】

第一题看了一下题，发现数据范围20w，感觉根本不能做..

第二题感觉是polya裸题？感觉挺可做的样子..

第三题看了好久，不知道在干什么，就弃疗了..

于是全程肛第二题..先枚举一下循环节，然后长度为[tex]l[/tex]的环用不超过[tex]K[/tex]种颜色交错染色的方案数在BC上有，是[tex](K-1)^l+(K-1) \times (-1)^l[/tex]（不知道有没有记错），枚举每一个[tex]K[/tex]容斥一下再累加贡献就好了。

这样的复杂度是[tex]O(dK \log n)[/tex]的，[tex]d[/tex]是约数个数，轻易的T飞了..这样瓶颈是在对每一个[tex]i[/tex]求[tex]i^l[/tex]。然后我们就开始搞各种鬼畜的优化..最开始先加了一个线性筛，这样就只需要对每一个质数求快速幂了..然而还是T飞了。

然后一直卡不出来..中途弃疗了若干次..后来直接对每一个质数[tex]p[/tex]预处理[tex]p^{a \times 1024^b}[/tex]，这样快速幂就只要三次乘法就好了..然后终于是卡过去了..可喜可贺可喜可贺。

之后开始看第三题，感觉一副可持久化并查集的样子..然而根本不懂交互库在干什么..

后来听说原来第一题是真·题答题，可以对着数据爆出来高分..然而那个时候又累又困意识模糊就索性弃疗了。

胡测快结束的时候听说了HNOI的成绩..80+50+30..常数一卡就是70分..实在是爽的不行。

晚上家长们带我们去吃西餐，作为一个吃吃吃选手感觉非常赞..

[先坑着..之后有空了再写]