赛时
创飞了www
赛前还是给自己定了目标,事实证明,定目标对像昨天那种顺风局是有利的,然而对于今天纯逆风局是负面buff
赛时开T1,一眼区间dp,因为异或的和这种一看就不能贪心,然后也不具有局部最优性,所以赛时反复考虑的按位枚举也是错误的
发现当前区间的贡献是很好得出的
难点在于统计k个的分别贡献
事实上,应当想到多个散点可以用同一个状态来包含,然后状态更新时对于一个一个k个中的一个分别算出来所有情况
然后当区间大到可以合并为一个时,就更新答案
具体的,只考虑最左的第一个点可能包含区间的情况
然后就能包含所有情况
非常经典的区间dp套路
T2,想了1h,想到了一种图,然后倍增处理
但是发现会有环,更新的有问题
然后赛时就想了调了好久
发现还剩1h,直接炸了,也想不出别的解法
然后才看T3和T4,T3也想不出怎么暴力
想写T3的20pts,然后不会判环(事实上就用出度来更新就行)
转战T2,打了40pts,但是空间来不及算,炸了
T4赶紧打了10分,a_i<=1都来不及想了
策略绝对的失误
发现当我觉得很多都可想但是时间又紧,又没有很多分的时候,是没法静下心来想的
考虑到想一个暴力的时间很短,所以策略调整
开题,想正解没什么思路就先想暴力,然后想做法和实现(一定要想到觉得实现不复杂为止)
然后4题都又思路了,决定写题的优先级,然后开写
赛后
补了T1,思路如上
T2,想了半天,然后kh一句话点醒梦中人,就新更新的点新建一个点就行了(类似分层图最短路)
还可以线性做法,发现如果新建了点,就相当于又若干条链,然后按照l从小到大排序,双指针???(没搞明白!!!)
T3,正解
考虑到一个全都能到达环上的图的出度都大于0(这个trick之前在内向基环树的性质时想过,但没有想到
然后对于一张这样的图,我们更新答案即可
考虑到这样一张图,更新答案不好知道从哪开始更新
考虑最没有影响的边,即全图中r最大的边,因为它相当于是一个相当充分的条件,最大的限制,所以不会对答案的缩小造成影响
当点的出度为0时,相当于它的答案已经更新完毕了,可以更新别的点了
以上两种操作交替进行,就可以了
T4,还没完全会,但是前几步转化可以积累一下
看到有一个 a_i<=1 的部分分,往往具有提示意义
二分一下区间的第k大,于是就能把区间划分为0/1了
然后就分成两部分
1.判断0/1的个数是否合法
2.计算前k个0的和
具体还不太会,但是,简化了问题