codeforces 240 F. TorCoder (线段树)

题目链接

题意:给一个仅由小写字母组成的字符串,然后m个操作,每个操作一个区间,要求把区间中排列成字典序最小的回文串,如果不能形成回文串,就忽略该操作。

思路:和上一道线段树优化计数排序的题目很像,几乎是一样的。

同样的,26棵线段树,每种字母对应一棵。

每次统计询问区间中每种字母的个数。

然后先判断是否能形成回文(奇数长度只有一个个数为奇数的,偶数长度不能出现个数为奇数的)

能的话重置区间,然后前后分别覆盖。

注意如果是奇数长度的话,记得先覆盖中间点。

需要注意这道题的输入输出方式不是标准的。。。而是要加文件。。。不然会MLE 1

然而Tle 19….Tle了好久。。。

2016-10-05-17-43-28-%e7%9a%84%e5%b1%8f%e5%b9%95%e6%88%aa%e5%9b%be

最后换了种线段树的写法就过了。。。

然而后面这种写法就一定好么。。。。好像也不是。。。

总之是个挺玄学的东西。。。。不管了。。。

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz