[CF 965E]Short Code
你有\(n\)个两两不同的串,你要将每个串变成其的一个前缀,使得变换后的所有串仍然两两不同,并且所有串长度和尽可能小,输出这个和。
\(n\leq 10^5\),所有串长之和不超过\(10^5\)。
[BZOJ 1212]L语言
这个感觉本质上和那个Remember a Word很像吧……
不过这个只是求最长可行前缀,递推即可。
代码:
/************************************************************** Problem: 1212 User: danihao123 Language: C++ Result: Accepted Time:660 ms Memory:45072 kb ****************************************************************/ #include <cstdio> #include <cstring> #include <vector> using namespace std; const int maxn=1048581; const int maxW=4005,maxL=105; #define REP(i,n) for(i=0;i<(n);i++) #define REP_B(i,n) for(i=1;i<=(n);i++) #define DREP(i,n) for(i=(n)-1;i>=0;i--) #define CL_ARR(x,v) memset(x,v,sizeof(x)) vector<int> AnsList; namespace Trie{ const int maxnode=400005; const int sigma_siz=26; int Tree[maxnode][sigma_siz]; int val[maxnode]; int siz; inline int idx(char c){ return c-'a'; } inline void InitTrie(){ siz=0; val[0]=0; CL_ARR(Tree[0],0); } void Insert(char *s,int v){ register int u=0,n=strlen(s); register int i,c; REP(i,n){ c=idx(s[i]); if(!Tree[u][c]){ siz++; Tree[u][c]=siz; val[siz]=0; CL_ARR(Tree[siz],0); } u=Tree[u][c]; } val[u]=v; } void Query(char *s,int len){ register int i,c,u=0; AnsList.clear(); REP(i,len){ if(!s[i]) break; c=idx(s[i]); if(!Tree[u][c]) break; u=Tree[u][c]; if(val[u]) AnsList.push_back(val[u]); } } }; char Text[maxn]; int len[maxW]; char buf[maxL]; bool d[maxn]; int main(){ int n,m; int length; register int i,j,k; bool flag; Trie::InitTrie(); scanf("%d%d",&n,&m); REP_B(i,n){ scanf("%s",buf); len[i]=strlen(buf); Trie::Insert(buf,i); } REP_B(i,m){ scanf("%s",Text); length=strlen(Text); CL_ARR(d,0); d[0]=true; for(j=0;j<=length;j++){ if(d[j]){ Trie::Query(Text+j,length-j); REP(k,AnsList.size()){ d[j+len[AnsList[k]]]=true; } } } flag=false; for(j=length;j>=0;j--){ if(d[j]){ flag=true; printf("%d\n",j); break; } } if(!flag) puts("0"); } return 0; }
[LA 3942]Remember the Word
Trie第一题……
首先,容我吐槽一下UVa这个OJ,速度特别感人(同学们可以实践一下)。
这个题最容易想到的是[tex]O(n^2)[/tex]的DP——对于[tex]S[i\ldots n][/tex],枚举其前缀查是否为单词,然后转移。但是啊……对于[tex]n\le 300000[/tex]这种方法肯定会T飞。
然后我们可以考虑使用Trie优化DP。对于每个[tex]S[i\ldots n][/tex],在前缀树中查找之,就能找到所有可以作为其前缀的单词。由于每个单词最大长度也只是100,所以查找会很快辣~
代码:
#include <cstdio> #include <cstring> #include <vector> using namespace std; const int maxn=300005; const int maxW=4005,maxL=105; const int MOD=20071027; #define REP(i,n) for(i=0;i<(n);i++) #define REP_B(i,n) for(i=1;i<=(n);i++) #define DREP(i,n) for(i=(n)-1;i>=0;i--) #define CL_ARR(x,v) memset(x,v,sizeof(x)) int n; vector<int> AnsList; namespace Trie{ const int maxnode=400005; const int sigma_siz=26; int Tree[maxnode][sigma_siz]; int val[maxnode]; int siz; inline int idx(char c){ return c-'a'; } inline void InitTrie(){ siz=0; val[0]=0; CL_ARR(Tree[0],0); } void Insert(char *s,int v){ register int u=0,n=strlen(s); register int i,c; REP(i,n){ c=idx(s[i]); if(!Tree[u][c]){ siz++; Tree[u][c]=siz; val[siz]=0; CL_ARR(Tree[siz],0); } u=Tree[u][c]; } val[u]=v; } void Query(char *s,int len){ register int i,c,u=0; AnsList.clear(); REP(i,len){ if(!s[i]) break; c=idx(s[i]); if(!Tree[u][c]) break; u=Tree[u][c]; if(val[u]) AnsList.push_back(val[u]); } } }; char Text[maxn]; int len[maxW]; char buf[maxL]; int d[maxn]; int main(){ register int i,j,Case=0; int m; while(scanf("%s%d",Text,&m)==2){ Case++; n=strlen(Text); Trie::InitTrie(); REP_B(i,m){ scanf("%s",buf); len[i]=strlen(buf); Trie::Insert(buf,i); } d[n]=1; DREP(i,n){ d[i]=0; Trie::Query(Text+i,n-i); REP(j,AnsList.size()){ d[i]=(d[i]+d[i+len[AnsList[j]]])%MOD; } } printf("Case %d: %d\n",Case,d[0]); } return 0; }