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

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

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

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

 

uva 401 Palindromes

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=96&page=show_problem&problem=342
题意:问一个字符串是不是回文串,是不是镜像串。镜像串的意思是。。从镜子里看还一样。。给定了一些存在镜像的字母和数字。。
思路:回文串的判断用c++的string要更容易一些。。直接reverse一下。。判断是否相等就行。。。然后需要注意的是。。如果某个字符补存在镜像那么一定不是镜像串

如果某个字符不存在镜像那么一定不是镜像串!

如果某个字符不存在镜像那么一定不是镜像串!

蠢哭惹好么。。。。