摘要:科技小子或成最大赢家

11112020机房赛

summary

呜呼最近的考试好多原题啊~~不会教练又被骗了吧~~.

T1觉得可能有什么巧解,但是看到数据范围发现可以用splay维护,于是直接就开打了,但是我维护的方式比较怪,调得有点久.

然后看T2,其实没多久就想到贪心后分配剩下的位置的做法了,但是被1e3的数据范围唬住了,以为是什么n方dp做法,于是打了1和2的两个情况就去看T3了,准备把后面题做完再来继续想.但其实正解是nlogn的做法,而且2情况的做法和正解都差不多了,于是成为全场唯一没过这题的人.

T3看出是个容斥组合题,但我想的方法容斥系数不太好求,1e7的话没法做,就打了一个状压的30分和一个不用容斥的20分,数据出得比较水全部不容斥直接算都有40.

最后一个小时的时候开的T4,是个叫斯坦纳树的冷门算法,已经忘了怎么打了,于是想了个上下界最小费用流最大流的做法,时间太少了没调出来,后来发现是起点的流量设错了.

以后就尽量不要把已经有思路的题先放到一边做后面的题了,万一后面遇到题调不出来就无了,而且这次又是数据结构调得久,调数据结构还是不要打印中间变量了,变量太多了浪费时间,不如直接看代码抽象理解.