「总结」11112020机房赛
Contents
摘要:科技小子或成最大赢家
11112020机房赛
summary
呜呼最近的考试好多原题啊不会教练又被骗了吧.
T1觉得可能有什么巧解,但是看到数据范围发现可以用splay
维护,于是直接就开打了,但是我维护的方式比较怪,调得有点久.
然后看T2,其实没多久就想到贪心后分配剩下的位置的做法了,但是被1e3的数据范围唬住了,以为是什么n方dp做法,于是打了1和2的两个情况就去看T3了,准备把后面题做完再来继续想.但其实正解是nlogn的做法,而且2情况的做法和正解都差不多了,于是成为全场唯一没过这题的人.
T3看出是个容斥组合题,但我想的方法容斥系数不太好求,1e7的话没法做,就打了一个状压的30分和一个不用容斥的20分,数据出得比较水全部不容斥直接算都有40.
最后一个小时的时候开的T4,是个叫斯坦纳树的冷门算法,已经忘了怎么打了,于是想了个上下界最小费用流最大流的做法,时间太少了没调出来,后来发现是起点的流量设错了.
以后就尽量不要把已经有思路的题先放到一边做后面的题了,万一后面遇到题调不出来就无了,而且这次又是数据结构调得久,调数据结构还是不要打印中间变量了,变量太多了浪费时间,不如直接看代码抽象理解.
Author: lemir3
Link: https://www.lemir3.red/2020/11/11/zong-jie-11112020-ji-fang-sai/
License: 知识共享署名-非商业性使用 4.0 国际许可协议