noip模拟7

# 6.11考试总结 题比较基础，只有t3需要些运算，10$pts$说不过去了…… ## T1 匹配 next是c++11的保留字，跳next直接CE，然而我电脑上编译器不是c++11，然后就麻烦了…… 其实打字符串专题的时候遇到过这种情况，但我没长记性。。。遭报应了。。。 签到题，哈希和KMP均可，~~别的算法没学~~ 用KMP的时候注意把两个串连起来，求得长度满足$ans<=min(lena,lenb)$ ## T2 回家 $tarjan$板子忘了，调了许久也没调出来，，，， tarjan求割点，唯一的坑点是割点不一定是必经路径，所以求点双再$dfs$即可 还有一种强大的思路，在跑$tarjan$的时候判断合法方案 即维护一个标记数组，若$n$号节点在割点指向的联通分量中，此割点有效，标记1;否则割点无效，标记0 最后遍历$n$个点即可 ## T3寿司 实在想不出怎么做，主要是因为剩下半个多小时，心态不好了，然后匆匆打了个冒泡排序 **环状**，考虑退化成$n$条**链** 由于在做交换，那么一定满足有一个点使交换都不经过 否则若不存在交换不经过的点，则整个环每个位置都进行了交换，环的形状与某个只有部分位置交换的情况一致 这样的话，每条链开始和结束的位置即为断点，只需要枚举断点，求每条链中的最小移动次数 由于序列最终一定是两边‘R'中间'B'，或中间’R'两边‘B'，只需考虑’R'或‘B’到两边的距离 由于交换是双对象的，所以只要考虑每次交换中 **‘B'或’R‘中一个的移动情况**，即可确定这次交换 这里全部考虑’R' 那么只需要确定$n$条链每条链中‘R'到两边距离的最小值，**即该’R'左右两边‘B'的数量的最小值** 定义l[i]，r[i]分别为i左右两边’B' 的数量，$ans=min\sum_{i}^{totR}min(l[i],r[i])$ ### 暴力做法1 预处理每个位置到两边’B'的数量 枚举断点，直接枚举每个‘R'的到两边距离最小值，时间复杂度O($n^2$)，可以40$pts$ 需要**注意**，字符串直接读入不用清零，数组清零时在数组大小很大或清零次数很多时，不要用$memset$，否则可能$tle$，降到20$pts$ ### 优化 再回到原始式子，变形 $ans=\sum_{i}^{totR}min(l[i],r[i])$ =$\sum_{i}^{totR} \frac{r[i]+l[i]-|l[i]-r[i]|} {2}$ =$\sum_{i}^{totR}\frac{totB-|l[i]-r[i]|}{2}$ =$\frac{totB*totR}{2}$ $-$ $\sum_{i}^{totR} \frac{|l[i]-r[i]|}{2}$ 要求整体最小值，只需要考虑后面式子的最大值 设$l[i]-r[i]=x$ 考虑每次移动断点时变化的量。 分别考虑断点是’B'和‘R'对答案的贡献变化 1.若为‘R'，则有一个值为$totB$的x变为$-totB$ 2.若为’B'，则每个x值+2 3.令sum0为序列中x为正的数量，sum1为x为负的数量$sum=sum+sum0*2-sum1*2$ 由于套上了绝对值，则正数变大，负数变小，用优先队列维护负数，优先级为绝对值小的大 将堆中每个元素弹出都+2再压回去不现实，引入偏移值$delta$，表示队列中一个元素$x$，实际大小为$x+delta$ 对于1.将$-totB-delta$压如队列即可 对于2.不断弹出元素直到元素为负 操作二需要注意，若加上偏移值后为1,则说明上一次操作时为-1，绝对值没变，而考虑答案时-2，所以sum+=2 最终答案为$ans=\frac{totR*torB-sum}{2}$ 感谢zero4338大佬的博客，具体请见[这篇题解](https://www.luogu.com.cn/blog/174469/ti-xie-shou-si) 这种方法时间卡的有点紧，注意卡常和‘B'与’R'和选择，以及long long的适当使用保证答案的正确性