首页 > 代码库 > CF 461E

CF 461E

2024-07-23 04:53:56   213人阅读

中文翻译：

Description

Appleman和Toastman在玩游戏。首先Appleman告诉Toastman两个仅包含“A”、“B”、“C”、“D”的两个字符串s和t，要求Toastman构造s。一开始Toastman有个空串，每次他选取t的一个连续子串连接在他的串后面，直到他得到s为止。Appleman当然希望这个构造尽量难，现在他已经想好了t，他需要一个长度为n的s使得Toastman需要连接尽量多次。现在你需要告诉Appleman，通过确定一个s，最多能使Toastman连接多少次。假设Toastman一直采用最优策略。
 

Input

第一行一个整数n。
第二行一个字符串t。

Output

一个整数：最多能使Toastman连接多少次。
 

Sample Input

输入1：
5
ABCCAD
输入2：
5
AAABACADBABBBCBDCACBCCCDDDBDCDD

Sample Output

输出1：
5
输出2：
4
[样例解释]
对于第一个样例，s可以为“AAAAA”。
对于第二个样例，s可以为“DADDA”。
 

Data Constraint

对于20%的数据，n<=10。
对于另外20%的数据，|t|<=100。
对于100%的数据，n<=10^18，|t|<=10^5。
 
 
 
用一颗trie树记录T的后缀。预理a[i][j]表示前一个串首字母为i，接在后面的串首字母为j，i串的最短长度。a[i][j]=min(dep-1,从trie[root][i]出发第一个没有j儿子的节点）
 
另外树高可以限在log之内。 因为4^l>t-l+1时（全部大于可选的），则长度为l的串中一定有串不是t的子串，那么你每选一个l-1的串就可以了
 
终上。按log 4 N的高度建树。做个类似矩阵乘法的东西处理出连2^k次的长度，再倍增就可以了.
 
#include<cstdio>#include<cstdlib>#include<algorithm>#include<cmath>#include<cstring>using namespace std;typedef long long ll;ll m,xzq,mn;int i,n,ii,j,k,root,lim,lm,tot;bool pp;ll two[63];int fr[15];ll a[5][5][64];ll b[5][5],c[5][5];char s[100011];int trie[1000111][5];void Read(){    char c;    while(c=getchar(),c<‘A‘||c>‘D‘);    s[++n]=c;    while(c=getchar(),c>=‘A‘&&c<=‘D‘)s[++n]=c;}void add(int st,int len){    int x,i,y;    x=root;    for(i=st;i<=st+len-1;i++){        y=s[i]-64;        if(trie[x][y]==0)trie[x][y]=++tot;        x=trie[x][y];    }}void dfs(int i,int j,int x,int len){    int k;    if(trie[x][j]==0){        if(len<a[i][j][0])a[i][j][0]=len;        return;    }    if(len>=a[i][j][0])return;    for(k=1;k<=4;k++)if(trie[x][k]!=0)dfs(i,j,trie[x][k],len+1);}int main(){    scanf("%I64d",&m);    Read();    root=1;    tot=1;    fr[0]=1;    for(i=1;i<=n;i++){        fr[i]=fr[i-1]*4;        if(fr[i]>=n-i+1)break;    }    lim=i;    for(i=1;i<=n;i++){        add(i,min(n-i+1,lim));    }    for(i=1;i<=4;i++)        for(j=1;j<=4;j++)if(trie[root][i]&&trie[root][j])a[i][j][0]=2147483647;    for(i=1;i<=4;i++)        for(j=1;j<=4;j++){            if(trie[root][i]&&trie[root][j])dfs(i,j,trie[root][i],1);        }    two[0]=1;    for(ii=1;ii<=2147483647;ii++){        two[ii]=two[ii-1]*2;        if(two[ii]>m)break;        for(i=1;i<=4;i++)            for(j=1;j<=4;j++)                for(k=1;k<=4;k++)if(trie[root][i]&&trie[root][j]&&trie[root][k]){                    if(a[i][j][ii]==0||a[i][k][ii-1]+a[k][j][ii-1]<a[i][j][ii])a[i][j][ii]=a[i][k][ii-1]+a[k][j][ii-1];                }    }    lm=ii-1;    pp=false;    for(ii=lm;ii>=0;ii--){        mn=m+m;        if(pp==false){            for(i=1;i<=4;i++)                for(j=1;j<=4;j++)                    if(trie[root][i]&&trie[root][j]){                        if(a[i][j][ii]<mn)mn=a[i][j][ii];                    }            if(mn<m){                pp=true;                for(i=1;i<=4;i++)                    for(j=1;j<=4;j++)                        b[i][j]=a[i][j][ii];                xzq+=two[ii];            }        }        else{            for(i=1;i<=4;i++)                for(j=1;j<=4;j++){                    c[i][j]=0;                    for(k=1;k<=4;k++)if(trie[root][i]&&trie[root][j]&&trie[root][k])                        if(c[i][j]==0||b[i][k]+a[k][j][ii]<c[i][j])                            c[i][j]=b[i][k]+a[k][j][ii];                    if(trie[root][i]&&trie[root][j])if(c[i][j]<mn)mn=c[i][j];                }            if(mn<m){                xzq+=two[ii];                for(i=1;i<=4;i++)                    for(j=1;j<=4;j++)b[i][j]=c[i][j];            }        }    }    xzq++;    printf("%I64d\n",xzq);}

 

CF 461E


联系
我们