首页 > 代码库 > 【BZOJ 4180】 4180: 字符串计数 (SAM+二分+矩阵乘法)

【BZOJ 4180】 4180: 字符串计数 (SAM+二分+矩阵乘法)

4180: 字符串计数

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 164  Solved: 75

Description

SD有一名神犇叫做Oxer,他觉得字符串的题目都太水了,于是便出了一道题来虐蒟蒻yts1999。
他给出了一个字符串T,字符串T中有且仅有4种字符 ‘A‘, ‘B‘, ‘C‘, ‘D‘。现在他要求蒟蒻yts1999构造一个新的字符串S,构造的方法是:进行多次操作,每一次操作选择T的一个子串,将其加入S的末尾。
对于一个可构造出的字符串S,可能有多种构造方案,Oxer定义构造字符串S所需的操作次数为所有构造方案中操作次数的最小值。
Oxer想知道对于给定的正整数N和字符串T,他所能构造出的所有长度为N的字符串S中,构造所需的操作次数最大的字符串的操作次数。
蒟蒻yts1999当然不会做了,于是向你求助。

Input

第一行包含一个整数N,表示要构造的字符串长度。
第二行包含一个字符串T,T的意义如题所述。

Output

输出文件包含一行,一个整数,为你所求出的最大的操作次数。

Sample Input

5
ABCCAD

Sample Output

5

HINT

【样例说明】


例如字符串"AAAAA",该字符串所需操作次数为5,不存在能用T的子串构造出的,且所需操作次数比5大的字符串。


【数据规模和约定】

对于100%的数据,1 ≤ N ≤ 10^18,1 ≤ |T| ≤ 10^5。

Source

By yts1999

 

 

【分析】

  好题啊。我没想到。。

  要用一种稍微转化一下的思维?

  要算n最多操作次数,可以二分答案,然后询问操作次数为x的区间最小长度是多少。【我个人觉得这样想也不简单啊。

  考虑如果S确定的话,其实是贪心的,匹配到不能匹配的时候断掉,成为新的一段。

  在SAM上就是没有儿子的后继之后,就跳回根。

  所以其实(10^18的时候你应该看出来要矩乘了),矩阵中不需要存SAM的每个点,也不能存,只要存现在是什么颜色就好了。

  保证断掉的话,就是f[i][j]表示第i为开头的子串最短多少后面接j就会断。

  这个很好求,先做SAM,求出mn[x][i]表示x这个点后面接最短多少的子串再接j之后就会断。

  mn[x][i]=min(mn[son][i]+1)。

  f[i][j]=mn[1的i儿子][j]。

  然后x次操作就是f[i][j]^x,矩阵“乘法”的运算实际上是求和取min。

  【看代码吧!

 

技术分享
  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 using namespace std;
  7 #define Maxn 100010
  8 #define LL long long
  9 #define INF 0xfffffff
 10 #define inf 1LL<<60
 11 
 12 LL n;
 13 int mymin(int x,int y) {return x<y?x:y;}
 14 
 15 struct node
 16 {
 17     int pre,son[6],step;
 18 }t[Maxn*2];
 19 bool vis[2*Maxn];
 20 
 21 int mn[2*Maxn][6];
 22 
 23 struct sam
 24 {
 25     int last,tot;
 26     void extend(int k)
 27     {
 28         int np=++tot,p=last;
 29         t[np].step=t[p].step+1;
 30         while(p&&!t[p].son[k])
 31         {
 32             t[p].son[k]=np;
 33             p=t[p].pre;
 34         }
 35         if(!p) t[np].pre=1;
 36         else
 37         {
 38             int q=t[p].son[k];
 39             if(t[q].step==t[p].step+1) t[np].pre=q;
 40             else
 41             {
 42                 int nq=++tot;
 43                 memcpy(t[nq].son,t[q].son,sizeof(t[nq].son));
 44                 t[nq].step=t[p].step+1;
 45                 t[nq].pre=t[q].pre;
 46                 t[q].pre=t[np].pre=nq;
 47                 while(p&&t[p].son[k]==q)
 48                 {
 49                     t[p].son[k]=nq;
 50                     p=t[p].pre;
 51                 }
 52             }
 53         }
 54         last=np;
 55     }
 56     void dfs(int x)
 57     {
 58         if(vis[x]) return;
 59         vis[x]=1;
 60         for(int i=1;i<=4;i++) mn[x][i]=INF;
 61         for(int i=1;i<=4;i++)
 62         {
 63             if(!t[x].son[i]) mn[x][i]=1;
 64             else
 65             {
 66                 dfs(t[x].son[i]);
 67                 for(int j=1;j<=4;j++) mn[x][j]=mymin(mn[x][j],mn[t[x].son[i]][j]+1);
 68             }
 69         }
 70     }
 71 }sam;
 72 
 73 char s[Maxn];
 74 
 75 struct Matrix
 76 {
 77     LL w[6][6];
 78     Matrix() {memset(w,0,sizeof(w));}
 79     inline friend Matrix operator * (const Matrix A,const Matrix B)
 80     {
 81         Matrix ret;
 82         for(int i=1;i<=4;i++)
 83          for(int j=1;j<=4;j++)
 84          {
 85             ret.w[i][j]=inf;
 86             for(int k=1;k<=4;k++) ret.w[i][j]=min(ret.w[i][j],A.w[i][k]+B.w[k][j]);
 87          }
 88         return ret;
 89     }
 90     inline friend Matrix operator ^ (const Matrix A,LL k)
 91     {
 92         Matrix ret,tmp=A;
 93         for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) ret.w[i][j]=(i==j)?1:0;
 94         for (;k;k>>=1,tmp=tmp*tmp) if(k&1) ret=ret*tmp;
 95         return ret;
 96     }
 97 }Q;
 98 
 99 bool check(LL x)
100 {
101     Matrix B=Q^x;
102     LL mn=inf;
103     for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) mn=min(mn,B.w[i][j]);
104     return mn>=n;
105 }
106 
107 int main()
108 {
109     scanf("%lld",&n);
110     scanf("%s",s);
111     int ll=strlen(s);
112     sam.tot=sam.last=1;
113     for(int i=0;i<ll;i++) sam.extend(s[i]-A+1);
114     memset(vis,0,sizeof(vis));
115     sam.dfs(1);
116     
117     for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) Q.w[i][j]=mn[t[1].son[i]][j];
118     
119     LL l=1,r=n,ans;
120     while(l<r)
121     {
122         LL mid=(l+r)>>1;
123         if(check(mid)) r=mid;
124         else l=mid+1;
125     }
126     printf("%lld\n",r);
127     return 0;
128 }
View Code

看了CA爷的代码,感觉我的矩乘好看多啦!

写在结构体里面很有条理!!

 

2017-04-17 20:02:16

 

【BZOJ 4180】 4180: 字符串计数 (SAM+二分+矩阵乘法)