程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4909 String（組合數學)

HDU 4909 String（組合數學)

編輯：C++入門知識

HDU 4909 String（組合數學)

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<