http://acm.hdu.edu.cn/showproblem.php?pid=2825
hdu 有必要卡時間卡的那么厲害嗎 無語了
剛開始為了方便,我把各個字符串的首字符中沒有出現的字符,又加在了根節點上,這樣理解起來方便
誰知道在這里就讓我超時超到死呀,后來把那些本來想加的字符集成到根節點上就可以了,不就是多了20左右個字符嗎 有必要讓我超時
超的那么惡心嗎 無語了
代碼:
#include<iostream> #include<cmath> #include<cstdio> #include<string> #include<cstring> #include<vector> #include<stack> #include<queue> #include<set> #include<map> #include<algorithm> #define LL long long using namespace std; const int INF=0x3f3f3f3f; const int MOD=20090717; const LL LMOD=100000; const int N=105; const int M=135; const int K=26; struct nodeTrie { int v; int fail; int next[K]; void initialize() { v=0; fail=-1; memset(next,-1,sizeof(next)); } }trie[M]; int cnt,root; char s[N]; int to[M][K],num[1<<10]; int dp[26][M][1<<10]; inline int getNewNode() { ++cnt; trie[cnt].initialize(); return cnt; } inline void addWord(int p,char *s,int k) { if(s[0]=='\0') return ; for(int i=0;s[i]>='a'&&s[i]<='z';++i) { if(trie[p].next[s[i]-'a']==-1) trie[p].next[s[i]-'a']=getNewNode(); p=trie[p].next[s[i]-'a']; } if(k>0) (trie[p].v)=((trie[p].v)|(1<<(k-1))); } void init(int m) { cnt=0; root=getNewNode();/* for(int i=0;i<K;++i) { s[0]='a'+i;s[1]='\0'; addWord(root,s,0); }*/ for(int i=1;i<=m;++i) { gets(s); addWord(root,s,i); } } void bfs(int p) { trie[p].fail=root; queue<int>qt; qt.push(p); while(!qt.empty()) { int y; int x=qt.front();qt.pop(); for(int i=0;i<K;++i) if(trie[x].next[i]!=-1) { qt.push(trie[x].next[i]); if(x==root) {trie[trie[x].next[i]].fail=root;continue;} y=trie[x].fail; while(y!=root&&trie[y].next[i]==-1) y=trie[y].fail; if(trie[y].next[i]!=-1) trie[trie[x].next[i]].fail=trie[y].next[i]; else trie[trie[x].next[i]].fail=root; } } } void makeTo(int n) { for(int i=1;i<=n;++i) for(int j=0;j<K;++j) { int p=i; while(p!=root&&trie[p].next[j]==-1) p=trie[p].fail; if(trie[p].next[j]!=-1) to[i][j]=trie[p].next[j]; else to[i][j]=1; } for(int i=1;i<=n;++i) { int p=i; while(p!=root) { p=trie[p].fail; trie[i].v=(trie[i].v|trie[p].v); } } } inline int fNum(int x) { int sum=0; while(x>0) { if((x&1)==1) ++sum; x=x>>1; } return sum; } int main() { //freopen("data.in","r",stdin); for(int i=0;i<(1<<10);++i) num[i]=fNum(i); int n,m,k; while(scanf("%d %d %d ",&n,&m,&k)!=EOF) { if(n==0&&m==0&&k==0) break; if(m<k) {printf("0\n");continue;} if(m==0) { int tmp=1; for(int i=1;i<=n;++i) tmp=(tmp*26)%MOD; printf("%d\n",tmp); continue; } init(m); m=(1<<m); bfs(root); makeTo(cnt); dp[0][1][0]=1; for(int i=0;i<n;++i) for(int j=1;j<=cnt;++j) for(int l=0;l<m;++l) if(dp[i][j][l]>0) { for(int w=0;w<K;++w) { int k=to[j][w]; int r=(l|trie[k].v); dp[i+1][k][r]=(dp[i+1][k][r]+dp[i][j][l])%MOD; } dp[i][j][l]=0; } int ans=0; for(int j=1;j<=cnt;++j) for(int l=0;l<m;++l) if(dp[n][j][l]>0) { if(num[l]>=k) ans=(ans+dp[n][j][l])%MOD; dp[n][j][l]=0; } printf("%d\n",ans); } return 0; }
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
