比赛时间
7.30-8.00 t1感觉好麻烦啊,dfs不想打,k=1感觉还挺简单的,每一个连续的块长度/2就行 t2 唔又是这种类型的,感觉平常模拟赛和usaco都做过好多了,答案测评是什么鬼啊?不理解不理解 t3 虚数!糟糕,忘记build代码了,自闭
8.00-8.05 t1第二档写完
8.05-9.00 t2 先想暴力怎么写,但是发现找完全排列之后就无从下手了,而且不知道咋求最小方案,然后就想手推一下也行?于是开始,4很顺利推出来了,发现差分之后刚好可以两两抵消,于是就去构造5的,发现得把中间变成0,然后也有一个非常少的方法,然后就是6,一直在想,死活想不出来,最后看太晚了,就不想了,这道题弃疗
9.00-9.25 t3看了一下样例,发现这里的虚数其实就是把所有的点到他们的lca上的边都加进来了,所以好像暴力不用build,于是很快码了,就是m棵树导致每个数组都要开三维就很难受
9.25-10.10 t1硬着头皮写了dfs,把所有情况枚举一边,然后再枚举删了哪些点,然后判断,复杂度贼高,但是一定跑不满,所以写上之后检查小细节没错就ok了
10.10-12.00 先去想了想t3,发现好像暴力还能在优化一点复杂度,直接预处理每个区间,到时候o(1)询问,写了之后发现大样例挂了,自闭,然后想m=1的能不能做,发现不能 于是转而去想t1的k=2,发现这样的三个点每个最多只有12个,也就是总共只能有30000个情况,全部枚举一下,然后是不是就可做了?! 先写再说吧,也许这就是唯一的希望了 然而写完之后,还是不知道该怎么办,难道二分?那我该怎么验证呢,未果,最后也想不到了
赛后总结反思
- t2本来能拿分的,这题的意思没有必要输出正解,而是越接近分越高,所以一定要写一些鸭!!
- t1暴力码的时间有点长了,一难就有点不想写,不过感觉代码能力比之前上涨不少
与正解的差距
T1
用了一个模型转换,这种切断联系的问题都能转化成最小割问题,没有想到,应该属于套路了
|