ZOJ 7th Anniversary Contest

6/6

水了一场比赛，得空写个简单题解，分别是ZOJ3167-3172

传送门

题A ZOJ 3167

题意：貌似是给你m ^ n 的第k位为7的最小的n是什么？

题解：大数模拟吧，我懒得写~~

题B ZOJ3168

题意：先对Z排序，再对O，对J，对7，其他不变放在后面。

题解：水题，直接模拟。

 1 /*zhen hao*/
 2 #include 
 3 using namespace std;
 4 
 5 #define lson l, m, rt << 1
 6 #define rson m + 1, r, rt << 1  1
 7 #define ll long long
 8 
 9 char s[1111];
10 
11 int main() {
12 //  freopen("case.in", "r", stdin);
13   while (scanf("%s", s) > 0) {
14     int n = strlen(s), nz, no, nj, n7;
15     nz = no = nj = n7 = 0;
16     for (int i = 0; i < n; i++) {
17       if (s[i] == 'Z') nz++;
18       else if (s[i] == 'O') no++;
19       else if (s[i] == 'J') nj++;
20       else if (s[i] == '7') n7++;
21     }
22     for (int i = 0; i < nz; i++) putchar('Z');
23     for (int i = 0; i < no; i++) putchar('O');
24     for (int i = 0; i < nj; i++) putchar('J');
25     for (int i = 0; i < n7; i++) putchar('7');
26     for (int i = 0; i < n; i++) {
27       if (s[i] != 'Z' && s[i] != 'O' && s[i] != 'J' && s[i] != '7') putchar(s[i]);
28     }
29     puts("");
30   }
31 }

题C ZOJ3169

题意：给你n个数，代表hash后的表，hash的函数是h（x） = （x + 7） %  n，最后问你它原来的序列长什么样？

题解：首先对于一个数求出x（应该插入的位置），y是当前的位置，然后当[x,y)的数都插完之后才能才放当前这个数，所以这是一个简单的拓扑排序。有两个问题要解决：

第一：边太多，用vector也超了内存；这个应该考虑的是什么位置是最后放的，答案就是[x,y)的每个块的最后一个位置，也就是中间一块块的末尾才是应该考虑的地方。这样就可以减少很多边。

第二：题目要求的是如果有多个可能，应该安排最小的那个先插，这个就要用一个优先队列来实现拓扑排序即可。

 1 /*zhen hao*/
 2 #include 
 3 using namespace std;
 4 
 5 #define lson l, m, rt << 1
 6 #define rson m + 1, r, rt << 1 | 1
 7 #define long long ll
 8 
 9 const int maxn = 5e4 + 10;
10 int n;
11 int val[maxn], head[maxn], in[maxn], tot, mark[maxn];
12 
13 struct Edge {
14   int v, next;
15 };
16 
17 vector e;
18 
19 void init() {
20   tot = 0;
21   memset(head, -1, sizeof head);
22   memset(in, 0, sizeof in);
23   e.clear();
24 }
25 
26 void add_edge(int u, int v) {
27   e.push_back((Edge){v, head[u]});
28   head[u] = tot++;
29 }
30 
31 struct Node {
32   int d, u;
33   bool operator < (const Node& o) const {
34     return d > o.d;
35   }
36 };
37 
38 priority_queue pq;
39 
40 void toposort() {
41   while (!pq.empty()) pq.pop();
42   for (int i = 0; i < n; i++) if (val[i] > 0 && !in[i]) {
43     pq.push((Node){val[i], i});
44   }
45   bool first = false;
46   while (!pq.empty()) {
47     if (first) putchar(' ');
48     Node x = pq.top(); pq.pop();
49     printf("%d", x.d);
50     first = true;
51     for (int i = head[x.u]; i != -1; i = e[i].next) {
52       int v = e[i].v;
53       in[v]--;
54       if (!in[v]) pq.push((Node){val[v], v});
55     }
56   }
57   puts("");
58 }
59 
60 int main() {
61 //  freopen("case.in", "r", stdin);
62   while (scanf("%d", &n) != EOF) {
63     init();
64     memset(mark, 0, sizeof mark);
65     for (int i = 0; i < n; i++) {
66       scanf("%d", val + i);
67       if ((val[i] + 7) % n == i) mark[i] = 1;
68     }
69     for (int i = 0; i < n; i++) {
70       if (val[i] <= 0) continue;
71       int x = (val[i] + 7) % n;
72       while (x != i) {
73         if (mark[(x + 1) % n] || (x + 1) % n == i) {
74           add_edge(x, i);
75           in[i]++;
76         }
77         x = (x + 1) % n;
78       }
79     }
80     toposort();
81   }
82 }

题D ZOJ3170

题意：给你n个点，表示平衡二叉树的结点的权值，然后给你这个二叉树的左右儿子的数量，最后让你输出后序序列。

题解：递归建树，dfs（fa， L， R， cnt， le， dir）其中1是当前这个结点的父亲是什么，2是这个子树的结点在序列的范围是[L,R]，4是这个子树的结点数，5是这个结点的深度，6是这个结点是上一个结点的左或者右；

 1 /*zhen hao*/
 2 #include 
 3 using namespace std;
 4 
 5 #define lson l, m, rt << 1
 6 #define rson m + 1, r, rt << 1 | 1
 7 #define ll long long
 8 
 9 const int maxl = 18, maxn = 230;
10 vector<int> v[maxl];
11 int val[maxn], n, l, lch[maxn], rch[maxn], cnt[maxl];
12 char s[111111];
13 bool first;
14 
15 void dfs(int u, int L, int R, int num, int le, int f) {
16 //  cout << u << ' ' << L << ' ' << R << ' ' << num << ' ' << le << endl;
17   if (num == 1) { if (f == 0) lch[u] = L; else rch[u] = L; return; }
18   int lcnt = v[le][cnt[le]], rcnt = v[le][cnt[le] + 1];
19   cnt[le] += 2;
20   int v = L + lcnt;
21 //  cout << lcnt << ' ' << rcnt << ' ' << v << endl;
22   if (f == 0) lch[u] = v; else rch[u] = v;
23   if (lcnt) {
24     dfs(v, L, L + lcnt - 1, lcnt, le + 1, 0);
25   }
26   if (rcnt) {
27     dfs(v, R - rcnt + 1, R, rcnt, le + 1, 1);
28   }
29 }
30 
31 void print(int u) {
32   if (lch[u] != -1) print(lch[u]);
33   if (rch[u] != -1) print(rch[u]);
34   if (first) putchar(' ');
35   printf("%d", val[u]);
36   first = true;
37 }
38 
39 int main() {
40 //  freopen("case.in", "r", stdin);
41   while (scanf("%d", &n) == 1) {
42     for (int i = 0; i < n; i++) scanf("%d", val + i);
43     sort(val, val + n);
44     scanf("%d", &l);
45     for (int i = 0; i < l; i++) v[i].clear();
46     string line;
47     getchar();
48     for (int i = 0; i < l - 1; i++) {
49       getline(cin, line);
50       stringstream ss(line);
51       int x;
52       while (ss >> x) v[i].push_back(x);
53     }
54     memset(lch, -1, sizeof lch);
55     memset(rch, -1, sizeof rch);
56     memset(cnt, 0, sizeof cnt);
57     dfs(n, 0, n - 1, n, 0, 0);
58     first = false;
59     print(lch[n]);
60     puts("");
61   }
62 }

题E ZOJ3171

题意：找一个序列能够组成seven的所有方式有几种？

题解：dp[i][j]表示前i个字符，长度为j的有多少种。直接转移就好了，最后注意一下seven是怎么拼的。不说了，背单词去了。。。。

 1 /*zhen hao*/
 2 #include 
 3 using namespace std;
 4 
 5 #define lson l, m, rt << 1
 6 #define rson m + 1, r, rt << 1 | 1
 7 #define ll long long
 8 
 9 const int maxn = 1e4 + 10;
10 char s[maxn];
11 ll dp[maxn][6];
12 
13 int main() {
14 //  freopen("case.in", "r", stdin);
15   while (scanf("%s", s + 1) > 0) {
16     int n = strlen(s + 1);
17     memset(dp, 0, sizeof dp);
18     dp[0][0] = 1;
19     for (int i = 1; i <= n; i++) {
20       for (int j = 0; j <= 5; j++) dp[i][j] = dp[i - 1][j];
21       if (s[i] == 's' || s[i] == 'S') {
22         dp[i][1] += dp[i - 1][0];
23       }
24       else if (s[i] == 'v' || s[i] == 'V') {
25         dp[i][3] += dp[i - 1][2];
26       }
27       else if (s[i] == 'e' || s[i] == 'E') {
28         dp[i][2] += dp[i - 1][1];
29         dp[i][4] += dp[i - 1][3];
30       }
31       else if (s[i] == 'n' || s[i] == 'N') {
32         dp[i][5] += dp[i - 1][4];
33       }
34 //      for (int j = 0; j <= 5; j++) cout << dp[i][j] << ' '; puts("");
35     }
36     cout << dp[n][5] << endl;
37   }
38 }

题F ZOJ3172

题意：给你n个结点，m条边。问你最远的两个点距离是多少？

题解：直接跑一次树的直径即可。图的话就把dep更新的时候改成max，具体看代码。

 1 /*zhen hao*/
 2 #include 
 3 using namespace std;
 4 
 5 #define lson l, m, rt << 1
 6 #define rson m + 1, r, rt << 1  1
 7 #define ll long long
 8 
 9 const int maxn = 1e3 + 10, maxm = 1e6 + 10;
10 int n, m, tot;
11 int head[maxn], dep[maxn];
12 
13 struct Edge {
14   int v, next;
15 } edges[maxm];
16 
17 void init() {
18   tot = 0;
19   memset(head, -1, sizeof head);
20 }
21 
22 void add_edge(int u, int v) {
23   edges[tot] = (Edge){v, head[u]};
24   head[u] = tot++;
25 }
26 
27 void dfs(int u, int fa, int d) {
28   dep[u] = max(dep[u], d);
29   for (int i = head[u]; i != -1; i = edges[i].next) {
30     int v = edges[i].v;
31     if (v == fa) continue;
32     dfs(v, u, d + 1);
33   }
34 }
35 
36 int main() {
37 //  freopen("case.in", "r", stdin);
38   while (scanf("%d%d", &n, &m) == 2) {
39     init();
40     for (int i = 0; i < m; i++) {
41       int u, v;
42       scanf("%d%d", &u, &v);
43       add_edge(u, v);
44       add_edge(v, u);
45     }
46     memset(dep, 0, sizeof dep);
47     dfs(1, -1, 1);
48     int best = 0, bestid = 0;
49     for (int i = 0; i < n; i++) if (best < dep[i]) best = dep[bestid = i];
50     memset(dep, 0, sizeof dep);
51     dfs(bestid, -1, 1);
52     int temp = *max_element(dep, dep + n);
53     if (temp <= 7) puts("Impossible");
54     else printf("%d\n", temp);
55   }
56   return 0;
57 }