链接：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 node 17 { 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 do 28 { 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 else 66 { 67 for(int i=0;i<n;++i) 68 printf("%c",ans_str[i]); 69 puts(""); 70 } 71 } 72 return 0; 73 }