EOJ 1443 Code (十进制格雷码&欧拉回路)


http://acm.cs.ecnu.edu.cn/problem.php?problemid=1443

题目的大意就是说密码是n位的,所以有10^n种情况,然后由于当输入密码长度大于n时,只有最后n为有效。这样我们只要用一个(10^n+n-1)长的数字序列,就能破解这个密码。

用DFS找一个欧拉回路,按照字典序输出路径。由于状态过多,不能用递归,要用非递归实现DFS,然后用stack会超时,那就自己写个数组吧

 

EOJ 1443 Code (十进制格雷码&欧拉回路)
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <string>
10 #include <set>
11 #include <cctype>
12 #include <cstdlib>
13 #include <map>
14 #define maxn 1000100
15 #define inf 0x3f3f3f
16 #define mod 9997
17 #define pi 3.1415926535898
18 #define LL long long 
19 using namespace std; 
20 
21 int t[maxn], head[maxn], len[maxn], next[maxn], top, cnt, n, dk, ans[maxn];
22 bool vis[maxn];
23 int fc[8] = {1, 10, 100, 1000, 10000, 100000, 1000000};
24 struct node{
25     int x, p;    
26 }st[maxn];
27 
28 void add(int u, int v, int w){
29     t[cnt] = v;
30     len[cnt] = w;
31     next[cnt] = head[u];
32     head[u] = cnt++;
33 }
34 
35 void solve(){
36     memset(head, -1, sizeof(head));
37     memset(vis, 0, sizeof(vis));
38     cnt = 0;
39     int tmp;
40     for (int i = 0; i < fc[n - 1]; i++){
41         tmp = i % fc[n - 2];
42         for (int j = 9; j >= 0; j--)
43             add(i, tmp * 10 + j, i * 10 + j);
44     }
45     int u, pos;
46     top = 2; dk = 0;
47     st[1].x = 0; st[1].p = head[0];
48     while (top){
49         u = st[top - 1].x; pos = st[top - 1].p;
50         for (; ~pos; pos = next[pos])
51             if (!vis[pos]){
52                 st[top - 1].p = pos;
53                 vis[pos] = true;
54                 st[top].p = head[t[pos]]; st[top].x = t[pos]; top++;
55                 break;
56             }
57         if (pos == -1){
58             ans[++dk] = st[top - 1].p;
59             top--;
60         }
61     }
62     for (int i = 1; i < n; i++) printf("0");
63     for (int i = dk - 1; i >= 2; i--) printf("%d", len[ans[i]] % 10);
64     printf("\n");
65 }
66 
67 int main(){
68     while (cin >> n && n){
69         if (n == 1){            
70             printf("0123456789\n");
71             continue;
72         }else{
73             solve();
74         }
75     }
76     return 0;
77 }
View Code

EOJ 1443 Code (十进制格雷码&欧拉回路)

上一篇:AutoCAD输出完整高清的PDF文件图教程


下一篇:PS教程:绘制快乐奥运2008宣传画