比赛 NOIP模拟赛1 评测结果 WAWWWWWWWW
题目名称 叉叉 最终得分 10
用户昵称 Ays 运行时间 0.104 s
代码语言 C++ 内存使用 10.67 MiB
提交时间 2018-02-08 21:00:33
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
char s[100005];
int len,tot;
int q[100005][30],cnt;
queue<int> ss[36];
void find(){
	for(int i=0;i<26;i++){
		while(ss[i].size()){
			int fr=ss[i].front();ss[i].pop();
			int to=ss[i].front();ss[i].pop();
			for(int ii=0;ii<26;ii++){
				if(i==ii) continue;
				int p=q[to][ii]-q[fr][ii];
				if(p%2) tot++;
			}
		}
	}
}

void init(){
	for(int i=0;i<len;i++){
		int c=s[i]-'a';
		q[i][c]++;
		ss[c].push(i);
		if(i!=0) for(int d=0;d<26;d++) q[i][d]+=q[i-1][d];
	}
}


int main(){
	freopen("xxxx.in","r",stdin);
	freopen("xxxx.out","w",stdout);
	scanf("%s",s);len=strlen(s);
	init();
	find();
	printf("%d",tot/2);
	return 0;
}