首页 > 其他 > 详细

Atcoder Code Festival 2017 qual C 10.22 D题题解

时间:2017-10-23 17:15:59      阅读:289      评论:0      收藏:0      [点我收藏+]

技术分享

技术分享

技术分享

技术分享

【题意概述】

给出一个只有小写字母的序列,问最少把序列分成几段可以满足每一段可以通过变换成为回文串。变换指的是交换子序列中的字母的位置。

【题解】

我们把a~z分别设为2^0~2^25,每个子序列满足条件当且仅当子序列亦或和为0或2的n次幂。

我们用sum[i]表示前缀亦或和,用f[i]表示1~i的序列最少分成几段能满足条件,用g[i]表示状态为i的序列的最小的f

技术分享
 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4  
 5 using namespace std;
 6 const int maxn=300010;
 7 int ans=0,tot=0,sum[maxn],a[maxn],f[maxn],g[1<<26],n,l,r;
 8 char s[maxn];
 9 void read(int &k){
10     k=0; int f=1; char c=getchar();
11     while (c<0||c>9)c==-&&(f=-1),c=getchar();
12     while (0<=c&&c<=9)k=k*10+c-0,c=getchar();
13     k*=f;
14 }
15 int main(){
16     scanf("%s",s+1);
17     int n=strlen(s+1);
18     for (int i=1;i<=n;i++) sum[i]=sum[i-1]^(1<<(s[i]-a));
19     memset(f,32,sizeof(f)); memset(g,32,sizeof(g));
20     g[0]=0;
21     for (int i=1;i<=n;i++){
22         f[i]=min(f[i],g[sum[i]]+1);
23         for (int j=0;j<26;j++) f[i]=min(f[i],g[sum[i]^(1<<j)]+1);
24         g[sum[i]]=min(g[sum[i]],f[i]);
25     }
26     printf("%d\n",f[n]);
27     return 0;
28 }
View Code

 

Atcoder Code Festival 2017 qual C 10.22 D题题解

原文:http://www.cnblogs.com/DriverLao/p/7717536.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!