Stephen Horizon
Stephen Horizon

「OI笔记」2021.8.14

Day6

上午

  T1一开始题意理解错了,以为被替换成Backspace的字母不会被删,也就是说一次只会删一个字母。后来才发现样例中有一个点本来是NO我输出YES,所以发现了问题。
  之后发现规律:如果两个字符串长度的奇偶性不同,就必须先删掉首位,因为首位是一定要被删掉的,因为除了首位,其它字符被替换成Backspace会同时删除两个字符。
  然后就是一个for循环就完成的事情了。话说以后匹配字符串都可以这么用一个字符串代替了啊,之前貌似SB一样用双重for。
  话说cin是真的老了吗?为什么加了ios还是这么慢?(大雾

https://pro.goforit.top/stephen-zeng/img/master/202108141.png

  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。

https://pro.goforit.top/stephen-zeng/img/master/202108142.png

之后尝试着改了改昨天的T3,嗯,还是忒难了,蒟蒻做不到啊。慢慢改吧。
最后放上做题记录

撒花~

https://gimg2.baidu.com/image_search/src=http%3A%2F%2Fhbimg.b0.upaiyun.com%2F96a7e555ac545659b66f92581ed8f23b29c02b69e40a2-Tt1nrh_fw658&refer=http%3A%2F%2Fhbimg.b0.upaiyun.com&app=2002&size=f9999,10000&q=a80&n=0&g=0n&fmt=jpeg?sec=1631535424&t=91d60f9807851b8a64c76ac0d2d3d9f6

Stephen Zeng

文章作者

发表评论

textsms
account_circle
email

Stephen Horizon

「OI笔记」2021.8.14
Day6 上午   T1一开始题意理解错了,以为被替换成Backspace的字母不会被删,也就是说一次只会删一个字母。后来才发现样例中有一个点本来是NO我输出YES,所以发现了问题。   之后发现规…
扫描二维码继续阅读
2021-08-14