题目描述

Let s be a given string of up to 106 digits. Find the maximal k for which it is possible to partition s into k consecutive contiguous substrings, such that the k parts form a palindrome.
More precisely, we say that strings s0, s1, . . . , sk−1 form a palindrome if si = sk−1−i for all 0 ≤ i < k.
In the first sample case, we can split the string 652526 into 4 parts as 6|52|52|6, and these parts together form a palindrome. It turns out that it is impossible to split this input into more than 4 parts while still making sure the parts form a palindrome.

 

输入

A nonempty string of up to 106 digits.

 

输出

Print the maximal value of k on a single line.

 

样例输入

复制样例数据

652526

样例输出

4

题目大意:给你一个字符串s,最多可以把字符串s划分为多少个部分使得划分的部分也组成一个回文.

题目思路:

贪心+模拟+哈希

只要找到子串相同就立即开始划分两条线 .注意操作有点麻烦 ,分几和偶讨论就可以了.

具体提供几组样例:

124241 answer:4

1242424241 answer: 6

12345 answer: 1

12221 answer:5

12341 answer:3

1221 answer:4

12431 answer:3

这几组样例过了基本没什么问题,对着这几组去做这个题就比较好想了

AC代码: 

写麻烦了,其实可以合并的

#include <queue>
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#define MIN(x,y) ((x)<(y)?(x) : (y))
#define MAX(x,y) ((x)>(y)?(x) : (y))
#define PI 3.141592653589793
#include <sstream>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int INF=1e9;
const int maxn=1e6+5;
ll n,m;
char str[maxn];
ll H[maxn];
ll qpow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a)%mod;
        b/=2;a=(a*a)%mod;
    }
    return ans;
}
int main()
{
    scanf("%s",str+1);
    int s=1,len=strlen(str+1);
    for(int i=1;i<=len;i++)
    {
        H[i]=H[i-1]*97+str[i]-'0';
        H[i]%=mod;
    }
    if(len%2)
    {
        ll cnt=0;
        int s=1,e=len;
        while(1)
        {
            if(s==e) break;
            if(str[s]==str[e]){
                s++;e--;
                cnt+=2;
            }
            else
            {
                for(int i=2;i;i++)// 以当前节点为起点 or 终点的子串长度
                {
                    ll f=qpow(97,(ll)i);
                    if(s+i-1==e-i+1){
                        s=s+i-1;e=e-i+1;
                        break;
                    }
                    ll cur=(H[e]-(H[e-i]*f)%mod+mod)%mod,pre=(H[s+i-1]-(H[s-1]*f)%mod+mod)%mod;
                    if(cur==pre){
                        cnt+=2;
                        s=s+i;
                        e=e-i;
                        break;
                    }
                }
            }
        }
        printf("%lld\n",cnt+1);
    }
    else
    {
        ll cnt=0;
        int s=1,e=len;
        while(1)
        {
            if(s>e) break;
            if(str[s]==str[e])
            {
                if(s+1==e) cnt++;
                else cnt+=2;
                s++;e--;
            }
            else
            {
                for(int i=2;i;i++)// 同上
                {
                    ll f=qpow(97,(ll)i);
                    if(s+i-1>e-i+1){
                        s=s+i-1;e=e-i+1;
                        break;
                    }
                    ll cur=(H[e]-(H[e-i]*f)%mod+mod)%mod,pre=(H[s+i-1]-(H[s-1]*f)%mod+mod)%mod;
                    if(cur==pre){
                        if(s+i==e-i+1) cnt++;
                        else cnt+=2;
                        s=s+i;
                        e=e-i;
                        break;
                    }
                }
            }
        }
        printf("%lld\n",cnt+1);
    }
    return 0;
}

总结:这个题交两遍错了,最后改了取模就AC了,卡到了哈希碰撞,经学长指导,以后哈希可以进行双哈希,两个进制数完全一样则代表相同.