首页 > 代码库 > HDU 4850 Wow! Such String!

HDU 4850 Wow! Such String!

2024-07-12 23:37:21   222人阅读

链接：http://acm.hdu.edu.cn/showproblem.php?pid=4850

题意：给定一个N(1 ≤ N ≤ 500000)，构造一个长度为N的小写字母字符串，要求所有长度大于等于4的子串只能出现一次。不能构造输出“Impossible”。

 

(1).只需要考虑长度等于4的子串的情况。

(2).长度为4的小写字母子串组合共有26^4种，故最长只可能构造出26^4+3长度的字符串。

(3).若一个一个添加字符，当N>3时，每次添加一个字符，末尾的三个字符和新的字符就会构成一个新的长度为4的子串。

(4).抽象出图的模型：末尾的3个字符共有26^3种组合，每种抽象成一个节点。每个节点添加新字符有26种情况，抽象成26条有向边，指向转化后的节点。每经过一条图中的边，就是构造一个长度为4的子串的过程。如果长度为4的子串不能重复，那么每条边就至多只能走一次。

(5).图中每个节点的出度和入度都是26，根据定理，该有向图存在欧拉回路，且可以从任意一点作为出发点。那么图中所有的边都可以走过一次，构造出长度为26^4+3的字符串。

 

有向图欧拉回路的求法可以用套圈算法，写成非递归的形式，递归的形式会爆栈。

 

 1 #include <cstdio> 2 #include <cstring> 3  4 using namespace std; 5  6 const int maxn = (26*26*26); 7 const int mod = (26*26); 8 const int maxm = 500005; 9 bool vis[maxn][26];10 11 int get_next(int now,int i)12 {13     return (now%mod)*26+i;14 }15 int cur[maxn];16 struct node17 {18     int n,c;19 }st[maxm];20 char ans_str[maxm];21 int str_len;22 void euler(int now)23 {24     int top=0;25     memset(cur,0,sizeof(cur));26     memset(vis,0,sizeof(vis));27     do28     {29         bool ff=false;30         for(int i=cur[now];i<26;++i)31         {32             if(vis[now][i])continue;33             vis[now][i]=true;34             cur[now]=i+1;35             now=get_next(now,i);36             st[++top].n=now;37             st[top].c=i;38             ff=true;39             break;40         }41         if(!ff)42         {43             ans_str[str_len++]=st[top].c+‘a‘;44             now=st[--top].n;45         }46     }while(top);47 }48 49 void init()50 {51     str_len=0;52     euler(0);53     for(int i=0;i<3;++i)54         ans_str[str_len++]=‘a‘;55     ans_str[str_len]=0;56 }57 int main()58 {59     init();60     int n;61     while(~scanf("%d",&n))62     {63         if(n>str_len)64             puts("Impossible");65         else66         {67             for(int i=0;i<n;++i)68                 printf("%c",ans_str[i]);69             puts("");70         }71     }72     return 0;73 }
View Code


联系
我们