找一个最长字符串区间,满足里面每个字母出现的次数为偶数巧妙的利用了位运算的性质将所有的状态存在一个整数里,二进制数的每位是0 1 分别表示字母出现的偶 奇次,在利用前缀和
#include <cstdio> #include <string.h> #include <algorithm> using std::sort; const int maxn=10005; char str[105]; int cnt[maxn]; int pin[maxn]; int assist[maxn]; bool cmp(int a,int b) { if(cnt[a]!=cnt[b])return cnt[a]<cnt[b]; return a<b; } int main () { int n,i,j; int start , end , maxl , tmpl,s,e; while (~scanf("%d",&n)) { memset (cnt,0,sizeof(cnt)); pin[0]=0; for (i=1 ; i<=n ; ++i) { scanf("%s",str); int len =strlen (str); cnt[i]^=cnt[i-1]; for (j=0 ; j<len ; ++j) { cnt[i]^=(1<<(str[j]-'a')); //printf("%d ",cnt[i]); } pin[i]=i; assist[i]=i; } sort(assist , assist+n+1 , cmp); start=end=0;maxl=0; for (i=1 ; i<=n ; ++i) { //printf("%o ",cnt[i]); if(cnt[assist[i]]==cnt[assist[i-1]]) { tmpl=pin[assist[i]]-pin[assist[i-1]]; //printf("t=%d %d %d\n",tmpl,assist[i],assist[i-1]); if(maxl<tmpl) { start=pin[assist[i-1]]; end=pin[assist[i]]; maxl=tmpl; } pin[assist[i]]=pin[assist[i-1]]; } } if(start || end )printf("%d %d\n" ,start+1,end); else printf("No one\n"); } return 0; }