CodeForces 451D Count Good Substrings - 程序园
一个只包含a和b的字符串 问 它有几个长度为偶数和长度为奇数的"压缩回文串" 压缩的概念是 相邻的相同字符压缩成一个字符
思路：
串经过压缩一定满足如下形式 ……ababab…… 那么这样只要两端的字符相同则中间一定是回文的 因此对于一个a它作为左端点形成的回文串个数就等于它右边的a的个数 那么长度是奇数还是偶数呢 可以这么判断 如果a在奇数位置上和它匹配的a也在奇数位置上 那么形成的回文串就是奇数长度的 要不然就是偶数长度的 b同理 因此得到做法 统计一个字符的右边和它相同的字符在奇数位置和偶数位置的有几个 然后通过计算就可以得到结果
Read full article from CodeForces 451D Count Good Substrings - 程序园
No comments:
Post a Comment