「OI笔记」2021.8.14

Day6

¶上午

T1一开始题意理解错了，以为被替换成Backspace的字母不会被删，也就是说一次只会删一个字母。后来才发现样例中有一个点本来是NO我输出YES，所以发现了问题。   之后发现规律：如果两个字符串长度的奇偶性不同，就必须先删掉首位，因为首位是一定要被删掉的，因为除了首位，其它字符被替换成Backspace会同时删除两个字符。   然后就是一个for循环就完成的事情了。话说以后匹配字符串都可以这么用一个字符串代替了啊，之前貌似SB一样用双重for。   话说cin是真的老了吗？为什么加了ios还是这么慢？（大雾   T2刚开始想歪了，就想着把原数组延长到2n-1位形成一个环，然后再做。好像关于环的题都是这么做的诶。后来发现复杂度下不来，一路挺到O(n2)，所以不了了之。   后来想到了一般情况下的交换以排序我们可以通过建图连边来操作 手动连编 而这里我们不能将a[i]与b[i]连起来，所以我们就把a[i]和i连起来，交换之后a[i]就等于i+k。接着看m。

m<=n/3 <=> n-cnt<=n/3 <=> cnt>=2n/3

由m的取值范围可知，最后k的结果肯定不会超过三个，所以直接判断那三个就可以了。O(3n)拿下。

¶下午

下午这道数论题琢磨了好一会，还是有一点似懂非懂，数论还得过一遍。

¶晚上

一直在调T4。拿Diwanul的程序对拍了两个小时，才发现初始化没有初始化全。。。并查集应该初始化到mx+1，我就直接初始化到了n。真TMZZ。 之后尝试着改了改昨天的T3，嗯，还是忒难了，蒟蒻做不到啊。慢慢改吧。 最后放上做题记录

撒花~