【Atcoder】CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning

【題意】給定隻含小寫字母的字元串，要求分割成若幹段使段内字母重組順序後能得到回文串，求最少分割段數。n<=2*10^5

【算法】DP

【題解】關鍵在于快速判斷一個字元子串是否合法，容易發現合法僅當不存在或隻存在一個奇數字元，其餘字元均為偶數。

當涉及到奇偶性（%2）時，很自然能想到異或。

将小寫字母a~z轉化2^0~2^25，那麼一個字元子串合法當且僅當其連續異或值是0或2^i（0<=i<=25）。

令f[i]表示前i個合法的最少段數，sum[i]表示異或字首和，則有：

f[i]=min(f[j])+1,sum[i]^sum[j]=0||2^i，也就是在前面所有合法的j中取最小的f[j]。

将合法條件移項，得到sum[i]^(0||2^i)=sum[j]，那麼對于目前的i，可以快速算出需要的sum[j]。

而sum值隻有2*10^5個，可以用map存起來，然後就可以快速取用。

或者sum值本身不大，根據題目空間直接開數組也沒問題。

複雜度O(26*n)。

#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<map>
#define ll long long
using namespace std;
int read(){
    char c;int s=0,t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a<b?b:a;}
int abs(int x){return x>0?x:-x;}
void mins(int &a,int b){if(a>b)a=b;}
void maxs(int &a,int b){if(a<b)a=b;}
//void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
/*------------------------------------------------------------*/
const int inf=0x3f3f3f3f,maxn=200010,maxN=70000010;
 
int n,p[maxN],f[maxn],sum;
char s[maxn];
 
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    f[0]=0;
    memset(p,0x3f,sizeof(p));
    p[0]=0;
    for(int i=1;i<=n;i++){
        int x=1<<(s[i]-'a');
        sum^=x;
        f[i]=inf;
        f[i]=min(f[i],p[sum]+1);
        for(int j=0;j<26;j++)f[i]=min(f[i],p[sum^(1<<j)]+1);
        p[sum]=min(p[sum],f[i]);
    }
    printf("%d",f[n]);
    return 0;
}      

View Code

轉載于:https://www.cnblogs.com/onioncyc/p/7725875.html