关于CSPS2023 T2
  • 板块学术版
  • 楼主fdc99
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/10/27 19:34
  • 上次更新2023/11/2 11:12:15
查看原帖
关于CSPS2023 T2
245712
fdc99楼主2023/10/27 19:34

当时在赛场上没想到DP的做法,最后想到了一种模拟的做法(但是不对,也没想到反例)

简单来说就是开个for扫一下这个字符串,边扫边比较第i个字符和第i-1个字符,如果发现这俩相等就开个while,记l=i-1,r=i,然后就l--,i++向两边边拓展边比较,然后计算可以消除的数目(也就是每拓展一次加一次)直到两个不相同的时候,看看l-1的位置上有没有其他字符串,这个我当时想的是拿一个数组a存在第l-1的位置上,存前面有的字符串数量,这样每次有相邻字串的时候只需要将a[r]=a[l-1]+1,然后计算可消除的子串只需要加上a[l-1]就行了

当时是根据样例1想出来的,也只有样例1过了,样例2太长了没办法找问题出在哪了

2023/10/27 19:34
加载中...