HDU 4909 String

题目链接

题意：给定一个字符串全是小写字符，可能有一个位置为?，问号可以替代任何字符，也可以删掉，问有多少连续字串满足所有字母是偶数个

思路：组合数学，计算所有前最串的各个字母的奇偶状态，用一个01串表示，然后记录下个数，对于每个相同的状态，任选两个就能得到一个子序列，答案为所有C(num, 2)的和。

但是这个问题多了一个?的情况，但是没关系，可以枚举?,然后把序列分为3部分去考虑，?之前，?之后，和包含了?的串分开考虑即可

代码：

#include 
  
   
#include 
   
     #include 
     using namespace std; typedef int ll; const int N = 20005; int t, n, v, x; char str[N]; map
     
       hash; int main() { scanf("%d", &t); while (t--) { scanf("%s", str); v = -1; n = strlen(str); for (int i = 0; i < n; i++) { if (str[i] == '?') { v = i; break; } } int ans = 0; if (v == -1) { x = 0; hash.clear(); hash[0]++; for (int i = 0; i < n; i++) { x ^= (1<<(str[i] - 'a')); ans += hash[x]; hash[x]++; } printf("%d\n", ans); continue; } else { hash.clear(); ans = 0; x = 0; hash[0]++; for (int i = 0; i < v; i++) { x ^= (1<<(str[i] - 'a')); ans += hash[x]; hash[x]++; } hash.clear(); x = 0; hash[0]++; for (int i = v + 1; i < n; i++) { x ^= (1<<(str[i] - 'a')); ans += hash[x]; hash[x]++; } hash.clear(); x = 0; hash[0]++; for (int i = v + 1; i < n; i++) { x ^= (1<<(str[i] - 'a')); hash[x]++; } x = 0; if (hash.count(x)) ans += hash[x]; for (int j = 0; j < 26; j++) { if (hash.count(x^(1<
      
       = 0; i--) { x ^= (1<<(str[i] - 'a')); if (hash.count(x)) ans += hash[x]; for (int j = 0; j < 26; j++) { if (hash.count(x^(1<


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdu1269 迷宫城堡，有向图的强连..	下一篇：HDU 4908 BestCoder Sequence（组..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: