T1
考场上先干的T2,最后慌慌张张没去想正解,打算把树建起来,拿70分的部分分,于是写树剖LCA,板子好像忘了,回忆了好久还模拟了好几遍才打对树剖LCA............期望70,结果0.考试结束后一模一样的代码交上去就70,考试的时候全部TLE,玄学.............
斐波那契找性质,推60个数,加前缀和,二分查找,一个一个往上跳.
构造出来的树是个扁树,DEP不深,所以完全可以跳父亲.
T2
瞅一眼,莫队?不对,带修的话效率太低.
在看交换位置,平衡树?平衡树还真行,但我觉得有点麻烦.
区间搞事情,主席树?貌似可以,说干就干.
later样例一拍就过,大数据一上就挂.各种调试搞了很久发现单点修改挂了,因为主席树前缀和有共用节点,所以修改的时候要把节点复制一边.岂不是要MLE?内心一阵恐慌,算了,先码出来再说.本机测试应该是没有问题.
期望100 实际60 我不敢把数组开大,就开了300010*55,结果还是小了.而且颜色的maxn我给搞成了N,导致WA了一个点.细节仍需努力.....................
不够我现在有点蒙,主席树意义何在哈哈?普通权值线段树就能干的事情.......而且正解竟然是二分.
T3
考场上10min特判了一下,期望8,实际8;
一档40pts应该很好拿,倒这扫一边就行.
二档60pts有点费劲,我瞎打的暴力拿了72pts,本来打算调满的,后来发现确实假了,就转向了并查集.我不喜欢特判,一堆if搞得头痛,于是借鉴VECTOR记录每个数出现的位置,这样去判断满不满足二分图.clear时不能全部clear,否则的话TLE...