[数据结构与算法][题解] zelda

题目

见zelda

AC代码：

#include<bits/stdc++.h>
using namespace std;
char x;
int n,s[200005];
int f[1<<26]; 
int main(){
	scanf("%d",&n);
	scanf("%c",&x);
	for(int i=1;i<=n;i++){
		scanf("%c",&x);
		s[i]=s[i-1]^(1<<(x-97));
	}
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	for(int i=1;i<=n;i++)
		for(int k=0;k<26;k++)
			f[s[i]]=min(f[s[i]],f[s[i]^(1<<k)]+1);
	printf("%d",max(1,f[s[n]]));
	return 0;
} 

思路：

前期准备：思路的萌芽

定义数组$s[200005]$，$s[i]$表示各字母出现的次数的奇偶性的前缀异或值。什么意思呢？就是在字符串中1~i位的各个字母出现的次数的状态的高度概括。以一个26位二进制整数（大小在[0,(1<<26)-1]区间内）表示其状态，从右往左分别对应a、b、c、d…z，若其值为1，则代表对应字母出现了奇数次，否则对应偶数次。
所以易得求$s$数组的代码：

for(int i=1;i<=n;i++){
	scanf("%c",&x);
	s[i]=s[i-1]^(1<<(x-97));
}

明显易知，若一个字符串合法，则其所对应的状态最多只能有一个1。

状态转移方程：思路的涌现

定义状态$f[s[i]]$为前缀异或值为$s[i]$的字符串的最小拆分段数。若其值不为1，则它一定可以拆为两个部分，其中一部分满足$f$值为1。
而这一个合法的部分可以表达为0或2的0~25次幂的形式。
所以状态转移方程也就出来了：

for(int i=1;i<=n;i++)
	for(int k=0;k<26;k++)
		f[s[i]]=min(f[s[i]],f[s[i]^(1<<k)]+1);

初始化：思路的完善

怎么初始化呢？
一种错误的方法是：将$f[0]$和2的0~25次幂的$f$函数都初始化为1。这也是我一开始犯的错误，只能得80pts，WA了两个点。
一个极小的数据就可以干掉它：abca。具体原因大家过推一下就出来了。
正确的方法是将$f[0]$定义为0，其余都是正无穷，因为我们定义为无穷大为状态暂时不可达，而一个具体值表示该状态已被计算过，即到达过。所以这样进行递推就对了。
此外，若$s[n]$的值为0，则程序应输出1而不是0，只要让$f[s[n]]$和1取较大值即可。
ps:本题内存限制为512MB，我开的数组不会超。
完结。