A. Splitting into digits
Solved.
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int n; 5 6 void solve() 7 { 8 printf("%d\n", n); 9 for (int i = 1; i <= n; ++i) printf("%d%c", 1, " \n"[i == n]); 10 } 11 12 int main() 13 { 14 while (scanf("%d", &n) != EOF) 15 solve(); 16 return 0; 17 } View Code
B. Game with string
Solved.
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define N 100010 5 char s[N]; 6 7 int main() 8 { 9 while (scanf("%s", s + 1) != EOF) 10 { 11 stack <char> sta; 12 int cnt = 0; 13 for (int i = 1, len = strlen(s + 1); i <= len; ++i) 14 { 15 if (!sta.empty() && sta.top() == s[i]) sta.pop(), ++cnt; 16 else sta.push(s[i]); 17 } 18 puts(cnt & 1 ? "Yes" : "No"); 19 } 20 return 0; 21 } View Code
C. Grid game
Solved.
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define N 1010 5 char s[N]; 6 7 int main() 8 { 9 while (scanf("%s", s + 1) != EOF) 10 { 11 int x = 0, y = 0; 12 for (int i = 1, len = strlen(s + 1); i <= len; ++i) 13 { 14 if (s[i] == '1') 15 { 16 printf("%d %d\n", 1, x % 2 ? 3 : 1); 17 ++x; 18 } 19 else 20 { 21 printf("%d %d\n", 3, y % 4 + 1); 22 ++y; 23 } 24 } 25 } 26 return 0; 27 } View Code
D. Game with modulo
Solved.
题意：
交互题
猜数，猜一个$a$
每次询问格式为$(x, y)$
返回结果有两种
$x \;if (x \; mod\; a) >= (y \;mod\; a)$
$y \;if (x \;mod\; a) < (y \;mod\; a) $
思路：
我们考虑 从小到大倍增，去找到$a的一个单调范围$
比如说$1, 2, 4, 8, 16, 32 如果某一次询问中返回了x$
那么说明$a在询问的(x, y)范围中 并且2 \cdot a 不在这个范围内$
因为是从小到大进行倍增
那么我们考虑某一次询问是$(x, 2\cdot x)$
$a在其中$
$如果 a > x, 那么必然有x >= 2 \cdot x - a$
$如果a = x 那么必然有 x \;mod\;a = 2 \cdot x \;mod\; a$
那么这个区间就具有一个单调性，可以进行二分
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 char op[110]; 5 6 bool check(int x, int y) 7 { 8 printf("? %d %d\n", x, y); 9 fflush(stdout); 10 scanf("%s", op); 11 return op[0] == 'y'; 12 } 13 14 void solve(int l, int r) 15 { 16 int base = 1; 17 for (int i = l; i <= r; i += base, base <<= 1) 18 { 19 printf("? %d %d\n", i, i + base); 20 fflush(stdout); 21 scanf("%s", op); 22 if (op[0] == 'x') 23 { 24 int l = i + 1, r = i + base - 1, res = -1; 25 while (r - l >= 0) 26 { 27 int mid = (l + r) >> 1; 28 if (check(i, mid)) 29 { 30 l = mid + 1; 31 res = mid; 32 } 33 else 34 { 35 r = mid - 1; 36 } 37 } 38 if (res == -1) res = i; 39 printf("! %d\n", res + 1); 40 fflush(stdout); 41 return; 42 } 43 } 44 45 } 46 47 int main() 48 { 49 while (scanf("%s", op) && op[0] != 'e') 50 solve(0, 1000000000); 51 return 0; 52 } View Code
E. Johnny Solving
Upsolved.
题意：
给出一个无向图，没有重边和自环，每个点的度数至少是3
要求找出一个长度至少为$\frac{n}{k}的简单路径$
或者找出$至少k个环，每个环的长度至少为3，并且环的长度不被3整除，并且环中有一个点只属于这个环$
思路：
首先跑一棵$DFS树，如果某个叶子结点的深度>= \frac{n}{k} 那么直接输出这条简单路径$
$否则叶子结点个数肯定大于 k 个$
证明
$我们假设每个叶子结点到根节点的距离为x_1, x_2, \cdots x_c$
那么$x_1 + x_2 + \cdots + x_c >= n$
$那么根据抽屉原理 max(x_1, x_2, \cdots x_c) >= \frac{n}{c}$
$又 \frac {n}{c} < \frac{n}{k} 所以 c > k$
再考虑对于一个叶子结点u来说，它度数至少为$3$
$考虑 它的两条返祖边连向x, y 我们令deep[x] < deep[y]$
$那么这个时候有三个环 dist(x,u) + 1, dist(y, u) + 1, dist(x, y) + 2$
$首先证明三个环的长度都>= 3$
$因为没有重边，所以dist(x, u) 和 dist(y, u) >= 2 = 3 - 1$
$又x和y是不同的两点 所以 dist(x, y) >= 1 = 3 - 2$
$再证明三个环的长度至少有一个不被3整除$
$我们假设三个环的长度都被3整除，那么有$
$(dist(x, u) + 1) \% 3 == 0$
$(dist(y, u) + 1) \% 3 == 0$
$(dist(x, y) + 1) \% 3 == 0$
$又 dist(x, u) = (dist(y, u) + dist(x, y))$
$所以 dist(x, y) \% 3 == 0$
那么$(dist(x, y) + 2) \% 3 != 0$
$与已知矛盾, 得证$
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define N 300010 5 int n, m ,k; 6 vector <int> G[N]; 7 8 int fa[N], vis[N], deep[N], Max, pos; 9 void DFS(int u) 10 { 11 vis[u] = 1; 12 if (deep[u] > Max) 13 { 14 Max = deep[u]; 15 pos = u; 16 } 17 for (auto v : G[u]) if (!vis[v]) 18 { 19 fa[v] = u; 20 deep[v] = deep[u] + 1; 21 DFS(v); 22 } 23 } 24 25 vector < vector <int> > res; 26 int isleaf[N]; 27 void work(int u) 28 { 29 vis[u] = 1; 30 if (!isleaf[u]) 31 { 32 if (res.size() >= k) return; 33 int x = -1, y = -1; 34 for (auto v : G[u]) if (v != fa[u]) 35 { 36 if (x == -1) x = v; 37 else if (y == -1) y = v; 38 else break; 39 } 40 if (deep[x] > deep[y]) swap(x, y); 41 vector <int> tmp; int it = -1, top = -1; 42 if ((deep[u] - deep[y] + 1) % 3) 43 { 44 it = u; top = fa[y]; 45 } 46 else if ((deep[u] - deep[x] + 1) % 3) 47 { 48 it = u; top = fa[x]; 49 } 50 else 51 { 52 tmp.push_back(u); 53 it = y; top = fa[x]; 54 } 55 while (it != top) tmp.push_back(it), it = fa[it]; 56 res.push_back(tmp); 57 } 58 else for (auto v : G[u]) if (!vis[v]) work(v); 59 } 60 61 int main() 62 { 63 while (scanf("%d%d%d", &n, &m, &k) != EOF) 64 { 65 for (int i = 1; i <= n; ++i) G[i].clear(); 66 for (int i = 1, u, v; i <= m; ++i) 67 { 68 scanf("%d%d", &u, &v); 69 G[u].push_back(v); 70 G[v].push_back(u); 71 } 72 deep[1] = 1; Max = 1; 73 fa[1] = 0; 74 DFS(1); 75 if (Max > n / k) 76 { 77 puts("PATH"); 78 vector <int> res; 79 int it = pos; 80 while (it) 81 { 82 res.push_back(it); 83 it = fa[it]; 84 } 85 int len = res.size(); 86 printf("%d\n", len); 87 for (int i = 0; i < len; ++i) printf("%d%c", res[i], " \n"[i == len - 1]); 88 } 89 else 90 { 91 puts("CYCLES"); 92 memset(vis, 0, sizeof vis); 93 memset(isleaf, 0, sizeof isleaf); 94 for (int i = 1; i <= n; ++i) isleaf[fa[i]] = 1; 95 work(1); 96 for (int i = 0; i < k; ++i) 97 { 98 auto it = res[i]; 99 int len = it.size(); 100 printf("%d\n", len); 101 for (int j = 0; j < len; ++j) printf("%d%c", it[j], " \n"[j == len - 1]); 102 } 103 } 104 } 105 return 0; 106 } View Code
转载于:https://www.cnblogs.com/Dup4/p/10306995.html
