qzz的场
好题:loj2336「JOI 2017 Final」绳
uoj213「UNR #1」争夺圣杯
考虑每个点作为最大值的可行范围,向左ln1向右ln2,讨论一下发现是三段等差数列,二阶差分后就是线性的
1 | ll a[N],gol[N],gor[N];pr b[N]; |
CF634E Preorder Test
题意:给出一棵n个点的树,求一条不一定简单的路径,要求经过了k个不同的点,最小化经过点的最大点权
明显二分,然后可以把那些满的子树缩上去,跑个类似求直径的换根就行了
loj2336「JOI 2017 Final」绳
好高兴能想出这种思维题,虽然因为一些原因并不是在赛中完成的;另外所有部分分的做法都想到了,恰好层层递进
转化一:数字不要中途改,将他们堆成两组后,各自统一颜色来考虑代价
转化二:考虑将所有位置分两组,考虑希望颜色now所在组为1,那么这个01序列一定满足,将连续同值的缩在一起,除了最左边和最右边一段,其他长度都是偶数,这个可以感性理解,再打个表验证也很容易
于是现在无脑枚举now和另一组中最后颜色mx就是$O(m^2n)$的,思考一下这个段长度的奇偶性,枚举第一个块的长度是奇数还是偶数,那么剩下的就能捆绑在一起选择(例如第一个块是奇数,那么位置2和3绑在一起,4和5绑在一起),于是答案的计算就是$n-C_{mx}-sum,sum=选若干组的最小权值$,每个组的权值的话如果存在颜色now就-1,存在颜色mx就+1,那么预先把mx插好,枚举now并和之前的mx插在一起,这样复杂度就是$O(m\sum=mn)$,比赛中止步到这里,然后忙于搞别的事了
感觉这个捆绑还是很妙的,如果只是部分分的话会很可惜,所以想着怎么推广,发现还可以进一步优化!
融入一点贪心,所有有-1的组肯定都选,假设最初权值就是$-C_{now}$,然后两个1的组肯定不选,单个的1如果和-1一组就要增加1的贡献,将式子改写成$n+(-1)*C_{now}+(-C_{mx}+「-1和1组合的损失」)$,枚举now的话找出每个单独now旁边的颜色,更新其作为mx的贡献,暴力找最小的mx就是$O(m^2)$,code
很明显可以优化成$O(n+m)$,每次将那些修改的地方存起来,思考一些小技巧怎么保证复杂度地回撤,可能方法很多,想不到见code