首页 > 代码库 > Codeforces 696 D. Legen...
Codeforces 696 D. Legen...
Description
每个字符串有些价值,问生成长度为 \(l\) 的字符串最多能获得多少价值,总字符数不超过 \(200\), \(l\leqslant 10^{14}\) .
Sol
AC自动机 + 倍增Floyd.
用AC自动机统计到达每个节点会获得的权值.
然后在AC自动机从根节点开始找一条最长路,就用Floyd倍增就可以了...
发现自己AC自动机做Fail树的时候写错了,改了好久没改出来,最后发现不能直接将根扔进队列里...应该把根的所有子节点扔进去..
然后类似快速幂做就可以了.写矩阵的时候需要判断一下能否到达,我用 \(-1\) 来表示能否到达.
转移就是 \(C[i][j]=max\{C[i][j],A[i][k]+B[k][j]\},A[i][k]!=-1,B[k][j]!=-1\) .
Code
#include <bits/stdc++.h>using namespace std;const int M = 205;const int N = 20050;typedef long long LL;typedef vector< LL > Vec;typedef vector< Vec > Mat;void F(Mat &A,int v=-1) { int n=A.size(); for(int i=0;i<n;i++) for(int j=0;j<n;j++) A[i][j]=v;}Mat operator * (const Mat &A,const Mat &B) { int n=A.size();Mat C(n,Vec(n));F(C); for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(A[i][k]!=-1 && B[k][j]!=-1) C[i][j]=max(C[i][j],A[i][k]+B[k][j]); return C;}Mat operator ^ (Mat A,LL b) { int n=A.size();Mat r(n,Vec(n)); F(r);for(int i=0;i<n;i++) r[i][i]=0; for(;b;b>>=1,A=A*A) if(b&1) r=r*A; return r;}void Print(const Mat &A) { int n=A.size(); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) cout<<A[i][j]<<" "; cout<<endl; }cout<<"---------------------"<<endl;}struct AC_Auto { int rt,cnt; int f[N],ch[N][26],v[N]; int NewNode() { ++cnt;v[cnt]=f[cnt]=0,memset(ch[cnt],0,sizeof(ch[cnt]));return cnt; } void init() { cnt=rt=f[rt]=v[rt]=0;memset(ch[rt],0,sizeof(ch[rt])); } void insert(char *s,int val) { int l=strlen(s),o=rt; for(int i=0;i<l;i++) { if(!ch[o][s[i]-‘a‘]) ch[o][s[i]-‘a‘]=NewNode(); o=ch[o][s[i]-‘a‘]; }v[o]+=val; } void getFail() { queue< int > q; for(int i=0;i<26;i++) if(ch[rt][i]) q.push(ch[rt][i]); for(;!q.empty();) { int x=q.front();q.pop(); for(int i=0;i<26;i++) { if(!ch[x][i]) ch[x][i]=ch[f[x]][i]; else q.push(ch[x][i]),f[ch[x][i]]=ch[f[x]][i],v[ch[x][i]]+=v[f[ch[x][i]]]; } }// for(int i=0;i<=cnt;i++) cout<<i<<"-->"<<f[i]<<endl; } void Make(Mat &A) { A.resize(cnt+1,Vec(cnt+1)); int n=A.size();F(A); for(int i=0;i<n;i++) for(int j=0;j<26;j++) A[i][ch[i][j]]=v[ch[i][j]],A[i][ch[rt][j]]=v[ch[rt][j]]; }}ac;LL n,l,ans;LL a[N];char s[N];int main() {// freopen("in.in","r",stdin); ios::sync_with_stdio(false); ac.init(); cin>>n>>l; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>s,ac.insert(s,a[i]); ac.getFail(); Mat r; ac.Make(r); // Print(r); r=r^l; for(int i=0;i<(int)r.size();i++) ans=max(ans,r[0][i]); cout<<ans<<endl; return 0;}
Codeforces 696 D. Legen...
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。