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,嗯,还是忒难了,蒟蒻做不到啊。慢慢改吧。
最后放上做题记录
撒花~
回复 Stephen Zeng 取消回复