6/6
水了一场比赛，得空写个简单题解，分别是ZOJ3167-3172
传送门
题A ZOJ 3167
题意：貌似是给你m ^ n 的第k位为7的最小的n是什么？
题解：大数模拟吧，我懒得写~~
题B ZOJ3168
题意：先对Z排序，再对O，对J，对7，其他不变放在后面。
题解：水题，直接模拟。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 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 <bits/stdc++.h> 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<Edge> 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<Node> 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 <bits/stdc++.h> 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 <bits/stdc++.h> 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 <bits/stdc++.h> 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 } 代码君
转载于:https://www.cnblogs.com/zhenhao1/p/5444822.html
