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

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

阅读量：6967 次

发布时间：2019-06-27

本文共 965 字，大约阅读时间需要 3 分钟。

【题意】给定只含小写字母的字符串，要求分割成若干段使段内字母重组顺序后能得到回文串，求最少分割段数。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
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #define ll long longusing 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
            
             0?x:-x;}void mins(int &a,int b){ if(a>b)a=b;}void maxs(int &a,int b){ if(a

View Code

转载于:https://www.cnblogs.com/onioncyc/p/7725875.html

你可能感兴趣的文章

《UNIX网络编程卷1：套接字联网API（第3版）》——8.9　服务器进程未运行