26暑杭电多校第三场 总结
26暑杭电多校第三场 总结
开场，12题，我从06往前看。
今天的题目都很短，感觉很友好。
看了06，感觉不是很难的题。但先放着，后面再说。
05感觉也比较简单。
04初看有一点点难，当时觉得可能是贪心或者dp之类的。
03看了一眼，也觉得不难
然后去看02，没看懂题。（后面证明是题目错了）
看了01，感觉是道不简单的数数题。
这时去看了一眼榜，发现遍地开花了，看来有很多可做题。
05过的人最多，随便推了推，发现非常简单，随便打打就过了。（12：13）
孙似乎在这个时间点前后上线了，然后去看03，很快也过了。（12：26）
王一直在尝试09，他说和什么基环树有关。中途他问了一些问题，孙好像去和他讨论。
这段时间里，我一直在写04。04看起来比较复杂，但随便推了推发现直接费用流就行。但不确定复杂度行不行。随便写了写也过了。（12：28）
这个时候，王也把09调出来了。（12：30）
孙本来去看10，她说期望她不太会，我去看了一下，猜了个结论，然后就过了。（12：36）
这个时间之前，王和孙一直在讨论06。然后我也加入进去。
王说答案上限是n/2向上取整，然后我证了一下。然后我用我的证明方法想了一种构造，和他们讨论了一下，感觉没什么问题。孙也顺便打了一个表，然后我用我的构造方法
我打完，和孙的小数据对照了一下，感觉没问题，交了一发，WA了。
我们百思不得其解。然后后来我想了一个 的做法，复杂度对上了。然后跑去写。
写了一大轮，终于写完。然后和我之前的做法一拍，100以内，500以内，1000以内，1200以内，1400以内都没问题，蒙掉了。然后重新看题，发现要先输出数量。把上一份代码改一下交上去，过了。（13：49）
但是当时非常非常生气。这个问题浪费了我半小时和一发罚时。
开始陷入瓶颈了。
然后去随机看题。因为1002过的人多，所以王和孙去看1002。
我边吃饭边想1001，感觉不简单。
然后吃完饭，我就一直在想1011，感觉不难，有机会搞出来。
然后他们再继续讨论1002，我尝试思考一下，不想深入思考。就说我去搞1008。
1008看了一眼题，不想动脑子，回去想1011。
然后他们聊着孙说要去看1008，我怕露馅我没去想1008，然后就回去想1008。
然后发现1008好像不是非常难，因为可以分成几个自问题。
首先是一个图论问题。可以转化为有k个自由位。然后怎么推呢？这里一直想了很久，没想通。一直觉得可以dp。然后发现好像还要缩点，好麻烦。
然后发现k可以去掉，只算01的情况。那样子相当于求一个图的割的数量。这不是NP-Hard吗？能做吗？
回去看了一眼数据范围，哦，n<=20，那随便写了。
然后回到原题的限制就是个数位dp，带修的话显然就是ddp，上线段树维护矩阵即可。
然后开始写，先写暴力。暴力那里调了很久，dp的转移有一些小问题。
然后开始转矩阵了。
先写线段树，线段树是很好写。
但是要让我手动输入4个4X4的矩阵，我要崩溃了。
然后他们在调1002，一直遇到很多问题，摇我，我不理，继续调。
终于写出来，然后交了一发，终于过了。（16：14）
然后回去听他们讲1002的做法。他们推出的全选1或2的性质我不太信。
然后自己埋头想，写了一下，得到和他们一样的结论。
然后搞不懂，乱搞了一下，没搞出来。
然后又随便手造了一组很多2数据，然后发现最开始的性质假掉了。
然后快速改，只处理2的情况，虽然大概率是错的。最后交了一发，还是错，但已经有hack数据了。
虽然结束了，但把构造数据发到群里。原来我们三个小时对这道题的挣扎，第一步就错了。
但其实如果这组hack我早点给出，感觉完全有机会改。
最后7题，但是排名还是不错的。
总结：
- 在本地，不要只和自己的数据对照，先跑一次样例。不然你输出格式都错了
- 有些猜结论题先想一想一些前置结论有没有错。
- 三个人分散想题
