26暑杭电 第四场总结

12：00开题

三个人上线，我看5-8

先看第8题，感觉不简单，中档偏难

然后看07，回文串，那应该是和PAM或马拉车有关？

然后看06，构造。

一路看，中途发现11过的人很多，然后王就去写11了。我就一路把除01以外的题目都看了一遍。感觉没有特别送的题。01是计算几何，后面丢给王。

孙说她去做04。

王很快过了11（12：10），然后10很多人过，他也去做了。

07也有人过，我看07，发现肯定是并查集连边。

一开始直接猜了一个做法，对每次+d，先判断第一对在不在一起。如果已经在就直接跳。然后这样写完交上去WA了。（12：41）

然后没办法。首先想到可以取gcd，但取完gcd呢？

感觉可以直接暴力连边，打个表看看。

然后就本地暴力连边，打了个表。发现规律挺明显的。

然后直接按照这个规律来写，写完就过了。至于为什么，我也不懂。（12：59）

这段时间，因为03有人过，孙就去看03了。

很快，孙也把03过了。（13：03）

然后孙继续去调04。

中途王问我10样例，然后发现看错题了，然后他就跑去改了。

我先跑去思考了一轮02，没什么思路、

然后去思考06。想了一轮发现原来a是一个排列，那ab的组成就直接确定了啊。

然后把a扔掉，专心处理b。

一开始想了一个一路向右的做法，然后发现不能处理跳的情况。

然后本地就打了个表，瞪着，看看有没有什么性质。

然后边吃饭边瞪。一直想的是可以直接先走右边，再走左边。

然后发现有问题，就尝试先走其中一边。然后本地拿数据验证了一下，会出现无解的情况。

这时就真的想不到怎么做了。但是过的人感觉越来越多了啊。

吃完饭，再想了一轮，发现可以左右同时处理，从外往里。本地拿了一堆小数据手动模拟了一下，感觉可行。

中途，王终于把10调出来了。（14：30）

然后就打了一轮。打完本地拍了，没问题。交，WA了。（14：40）

本地合法数据都没问题，到底是怎么回事？

突然想起可能是题目的神秘无解，然后本地构造的全是有解，我没判断清楚。改了一下，还是错。然后发现无解还是没有清空。再改了，还是有问题。

然后想了一轮，没想通。后来想到可能是排序的问题，dis相同没定义，我本地可能正常排序，但评测机可能给我乱序排。改了改然后就过了。（15：06）

然后跑去认真想05。王比我早想05。

简单讨论了一下，我想到了一个莫队+线段树的做法，感觉复杂度有一点危。我想尝试打打。

王想了一轮05去想02，但是也没什么进展。后来又回来想05，他感觉有个思路，然后继续想了一下。

孙通过大量分讨终于把04做出来了。（15：41）

然后我交了一发05，T掉了。重新算了一下复杂度，果然不行。（15：53）

王发现他05的做法假了，然后我让他去看01计算几何。

他在16点多的时候发现01是半平面交的板子，然后去写。

孙在想02。

我05又猜了另一种思路，直接在原笛卡尔树上建虚树。复杂度我不太会证。但是没时间了，先试着写一发。

然后写写写，终于写出来了，过了（16：43）

然后王说01有思路了，但是写不完。

最终过了7题，rank50，终于进首页了。

怎么全世界都会02？02到底是什么题？