题意:给定一个数字x(x<=105),不停得把数字得最后几位放到最前面去。求最多可以产生多少中不同得数字,求出这些数字与原数字比较大于、等于、小于的个数。

思路:每一个可能得数字就是:将原字符串自身复制一遍之后在其中截取的一段,其长度等于原数字长。 我们可以借助倍增、DC_3或者扩展KMP求出复制后每个后缀与原字符串的最长公共前缀长度。(受限于本题的时间限制和数据范围,倍增光荣牺牲)设X为原串自我复制一次后的字符串。如果X的后缀A和原字符串X的最长公共前缀长度为k,那么比较A和X的大小就只需要比较A[k]和X[k]。这样就可以在O(lenX)时间内求出:X的每个长度为len的后缀和X的大小关系。 需要注意的是:如果X的后缀A和X的最长公共前缀长度k>=lenX/2,那么我们就人为X和A相等。因为真正生成的数字只是A的前lenX/2位。

还有一个问题:如何处理字符串重复的问题?自己多写几个样例就会发现:字符串重复的次数总是等于原字符串的循环节数。证明:如果将串Ab经过移动变为bA,且Ab==bA,那么




依此类推。

所以每发生一次Ab==bA(b尽可能短),则原串的循环节数就会多一。同理推知,原串有w个循环节则会发生w次Ab==bA。因为原串有w个循环节,所以对于每个循环节中的第i个数字b[i],如果它在操作时出现在串的末尾,那么一定会对应一个不同答案。又因为有w个循环节,所以每个答案出现了w次,所以只需要将答案数除以w即可。w可以结合kmp的next数组在O(n)时间复杂度内求出。

在这里推荐几扩展(拓展)kmp的教程:

教程1
教程2
#include <iostream>
#include <cstdio>
#include <cstring>

#define MX 100001

char src[MX*2],tmp[MX*2];
int nxt1[MX*2],nxt2[MX*2];
int big,sma,equ,dv;

using namespace std;

void getnext1(int *dis,char *str)                   //普通kmp
{
    int j=0,len=strlen(str);
    dis[j]=0;
    for(int i=1;i<len;i++)
    {
        while(j&&str[i]!=str[j])j=dis[j-1];
        if(str[i]==str[j])j++;
        dis[i]=j;
    }
}

void getnext2(int *dis,char *str)                   //扩展kmp
{
    int len=strlen(str);
    int k=0,i=1;
    dis[0]=len;
    while(k+1<len&&str[k]==str[k+1])k++;
    dis[1]=k,k=1;
    while(++i<len/2)
    {
        int mxr=k+dis[k]-1;
        dis[i]=min(dis[i-k],max(mxr-i+1,0));
        while(i+dis[i]<len&&str[dis[i]]==str[i+dis[i]])++dis[i];
        if(i+dis[i]>k+dis[k])k=i;
    }
}

void getans(int len)
{
    big=sma=equ=0;
    for(int i=0;i<len;i++)
    {
        if(nxt2[i]>=len)equ++;
        else if(src[nxt2[i]]<src[i+nxt2[i]])big++;
        else sma++;
    }
}

int main()
{
    int t,len;
    scanf("%d",&t);
    for(int w=1;w<=t;w++)
    {
        memset(src,0,sizeof(src)),memset(nxt1,0,sizeof(nxt1)),memset(nxt2,0,sizeof(nxt2));
        scanf("%s",src);
        len=strlen(src);
        memmove(tmp,src,sizeof(src));
        strcat(src,tmp);
        getnext1(nxt1,tmp),getnext2(nxt2,src),getans(len);
        dv=len%(len-nxt1[len-1]) == 0?len/(len-nxt1[len-1]):1;  //利用next数组求出循环节数
        cout<<"Case "<<w<<": "<<sma/dv<<" "<<equ/dv<<" "<<big/dv<<endl;
    }
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *