[CF 965E]Short Code
你有n个两两不同的串，你要将每个串变成其的一个前缀，使得变换后的所有串仍然两两不同，并且所有串长度和尽可能小，输出这个和。
n≤105，所有串长之和不超过105。
[BZOJ 1212]L语言
这个感觉本质上和那个Remember a Word很像吧……
不过这个只是求最长可行前缀，递推即可。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 | /************************************************************** 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，速度特别感人（同学们可以实践一下）。
这个题最容易想到的是的DP——对于
，枚举其前缀查是否为单词，然后转移。但是啊……对于
这种方法肯定会T飞。
然后我们可以考虑使用Trie优化DP。对于每个，在前缀树中查找之，就能找到所有可以作为其前缀的单词。由于每个单词最大长度也只是100，所以查找会很快辣~
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | #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;} |
