终于有场正常时间的比赛了。。。毛子换冬令时还正是好啊233
做了ABCD，E WA了3次最后没搞定，F不会= =
那就来说说做的题目吧= =
A. Team Olympiad
水题嘛= =
就是个贪心什么的乱搞，貌似放A题难了
1 #include <cstdio> 2 #include <algorithm> 3 4 using namespace std; 5 const int N = 5005; 6 7 int cnt[5], first[5], next[N]; 8 9 int main() { 10 int n ,i, x, ans; 11 int a, b, c; 12 scanf("%d", &n); 13 for (i = 1; i <= n; ++i) { 14 scanf("%d", &x); 15 next[i] = first[x], first[x] = i; 16 ++cnt[x]; 17 } 18 ans = min(min(cnt[1], cnt[2]), cnt[3]); 19 printf("%d ", ans); 20 a = first[1], b = first[2], c = first[3]; 21 for (i = 1; i <= ans; ++i) { 22 printf("%d %d %d ", a, b, c); 23 a = next[a], b = next[b], c = next[c]; 24 } 25 }
B. Queue
这放B题真的合适吗= =
就是模拟啦，但是但是，具体处理好麻烦的说！！！
1 #include <cstdio> 2 #include <algorithm> 3 4 using namespace std; 5 const int N = (int) 1e6 + 5; 6 int S = (int) 1e6 + 1; 7 int T = (int) 1e6 + 2; 8 9 struct edges { 10 int next, to; 11 edges() {} 12 edges(int _next, int _to) : next(_next), to(_to) {} 13 }e[N << 1]; 14 15 int n, tot, first[N]; 16 int ans[N], cnt; 17 int Cnt[N]; 18 bool v[N]; 19 20 inline void add_edges(int x, int y){ 21 e[++tot] = edges(first[x], y), first[x] = tot; 22 e[++tot] = edges(first[y], x), first[y] = tot; 23 } 24 25 int main() { 26 int i, x, y; 27 scanf("%d", &n); 28 for (i = 1; i <= n; ++i) { 29 scanf("%d%d", &x, &y); 30 ++Cnt[x], --Cnt[y]; 31 if (x == 0) x = S; 32 if (y == 0) y = T; 33 add_edges(x, y); 34 } 35 v[S] = 1, cnt = 1; 36 while (1) { 37 for (x = first[S]; x; x = e[x].next) 38 if (!v[e[x].to]) break; 39 if (x == 0) break; 40 v[S = e[x].to] = 1; 41 ans[cnt << 1] = S, ++cnt; 42 } 43 if (n & 1 == 0) { 44 v[T] = 1, cnt = 1; 45 while (1) { 46 for (x = first[T]; x; x = e[x].next) 47 if (!v[e[x].to]) break; 48 if (x == 0) break; 49 v[T = e[x].to] = 1; 50 ans[n + 1 - (cnt << 1)] = T, ++cnt; 51 } 52 } else { 53 for (i = 1; i <= N; ++i) 54 if (Cnt[i] == 1) { 55 S = i; 56 break; 57 } 58 ans[1] = S; 59 v[S] = 1, cnt = 1; 60 while (1) { 61 for (x = first[S]; x; x = e[x].next) 62 if (!v[e[x].to]) break; 63 if (x == 0) break; 64 v[S = e[x].to] = 1; 65 ans[cnt << 1 | 1] = S, ++cnt; 66 } 67 } 68 for (i = 1; i < n; ++i) 69 printf("%d ", ans[i]); 70 printf("%d ", ans[n]); 71 return 0; 72 }
C. Hacking Cypher
正这反着扫两遍，直接判断就好了，报noip高精模写错的一箭之仇！
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 5 using namespace std; 6 typedef long long ll; 7 const int N = (int) 1e6 + 5; 8 9 ll a, b; 10 int len; 11 bool ok_a[N], ok_b[N]; 12 char st[N]; 13 14 int main() { 15 ll tmp, T; 16 int i, j; 17 scanf("%s", st + 1); len = strlen(st + 1); 18 scanf("%I64d%I64d", &a, &b); 19 tmp = 0; 20 for (i = 1; i <= len; ++i) { 21 ((tmp *= 10) += st[i] - '0' ) %= a; 22 if (tmp == 0) ok_a[i] = 1; else ok_a[i] = 0; 23 } 24 tmp = 0, T = 1; 25 for (i = len; i; --i) { 26 (tmp += (ll) T * (st[i] - '0')) %= b; 27 (T *= 10) %= b; 28 if (tmp == 0) ok_b[i] = 1; else ok_b[i] = 0; 29 } 30 for (i = 2; i <= len; ++i) 31 if (ok_a[i - 1] && ok_b[i] && st[i] != '0') break; 32 if (i == len + 1) { 33 puts("NO"); 34 return 0; 35 } 36 puts("YES"); 37 for (j = 1; j < i; ++j) 38 putchar(st[j]); puts(""); 39 for (j = i; j <= len; ++j) 40 putchar(st[j]); puts(""); 41 return 0; 42 }
D. Chocolate
第一眼神题Orz
后来发现，是指1 * 1的方格一样多。。。这尼玛是在逗我！
于是计算面积s1, s2，令s1 /= gcd, s2 /= gcd
然后判断s1 * (2 / 3) ^ x1 * (1 / 2) ^ y1 = s2 * (2 / 3) ^ x2 * (1 / 2) ^ y2 是否有非负整数解(x1, x2, y1, y2)且x1, x2; y1, y2中都至少有一个0
乱搞吧2333
1 #include <cstdio> 2 3 using namespace std; 4 typedef long long ll; 5 6 ll a, b, c, d, s1, s2, G; 7 int ans; 8 int cnt[2][2]; 9 10 ll gcd(ll a, ll b) { 11 return !b ? a : gcd(b, a % b); 12 } 13 14 int abs(int x) { 15 return x < 0 ? -x : x; 16 } 17 18 void work() { 19 ans += cnt[0][1] + cnt[1][1] + abs(cnt[0][0] + cnt[0][1] - cnt[1][0] - cnt[1][1]); 20 } 21 22 int main() { 23 scanf("%I64d%I64d%I64d%I64d", &a, &b, &c, &d); 24 s1 = a * b; 25 s2 = c * d; 26 G = gcd(s1, s2); 27 s1 /= G, s2 /= G; 28 while (!(s1 & 1)) s1 >>= 1, ++cnt[0][0]; 29 while (s1 % 3 == 0) s1 /= 3, ++cnt[0][1]; 30 while (!(s2 & 1)) s2 >>= 1, ++cnt[1][0]; 31 while (s2 % 3 == 0) s2 /= 3, ++cnt[1][1]; 32 if (s1 > 1 || s2 > 1) { 33 puts("-1"); 34 return 0; 35 } 36 work(); 37 printf("%d ", ans); 38 cnt[0][0] += cnt[0][1], cnt[1][0] += cnt[1][1]; 39 if (cnt[0][0] > cnt[1][0]) cnt[0][0] -= cnt[1][0], cnt[1][0] = 0; 40 else cnt[1][0] -= cnt[0][0], cnt[0][0] = 0; 41 while (cnt[0][1]--) { 42 if (a % 3 == 0) (a /= 3) *= 2; 43 else (b /= 3) *= 2; 44 } 45 while (cnt[1][1]--) { 46 if (c % 3 == 0) (c /= 3) *= 2; 47 else (d /= 3) *= 2; 48 } 49 while (cnt[0][0]--) { 50 if (!(a & 1)) a /= 2; 51 else b /= 2; 52 } 53 while (cnt[1][0]--) { 54 if (!(c & 1)) c /= 2; 55 else d /= 2; 56 } 57 printf("%I64d %I64d %I64d %I64d ", a, b, c, d); 58 return 0; 59 }
E. Restoring Increasing Sequence
字符串处理一下，然后贪心当前最小即可，然后我的bin数组少了个0，WA到死啊！！！
我的Div.2 Rank 10-快还我。。。呜呜呜
1 #include <cstdio> 2 #include <cstring> 3 4 using namespace std; 5 const int bin[9] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000}; 6 const int N = 100005; 7 8 int n, len, len_last; 9 char st[10]; 10 int ans[N]; 11 12 int work(int p) { 13 int res = 0, i, j; 14 if (len_last > len) return 0; 15 if (len_last < len) { 16 for (i = 1; i <= len; ++i) 17 if (st[i] == '?') 18 if (i == 1) res = 1; else res *= 10; 19 else (res *= 10) += st[i] - '0'; 20 return res; 21 } 22 for (i = 1; i <= len; ++i) 23 if (st[i] == '?') 24 (res *= 10) += 9; 25 else (res *= 10) += st[i] - '0'; 26 if (res <= ans[p - 1]) return 0; 27 for (i = 1; i <= len; ++i) 28 if (st[i] == '?') 29 for (j = 1; j <= 9; ++j) 30 if (res - bin[len - i] <= ans[p - 1]) break; 31 else res -= bin[len - i]; 32 return res; 33 34 } 35 36 int main() { 37 int i; 38 scanf("%d ", &n); 39 ans[0] = 0; 40 len = 0; 41 for (i = 1; i <= n; ++i) { 42 scanf("%s ", st + 1); 43 len_last = len, len = strlen(st + 1); 44 if (!(ans[i] = work(i))) { 45 puts("NO"); 46 return 0; 47 } 48 } 49 puts("YES"); 50 for (i = 1; i <= n; ++i) 51 printf("%d ", ans[i]); 52 return 0; 53 }
F. Treeland Tour
第一反应是树上DP，每个点一个平衡树维护。。。
后来发现怎么可能，应该是点分治 + 归并数组。。。
但是真的能写的出来？不明= =（话说至今No Tags，什么东西！）
反正Div.2里只有一个人A了F，但是Div.1里A掉的貌似很多啊？以后再说吧
于是蒟蒻喜闻乐见的Div.2 Rank 44，被各位神犇D飞啦~Orz跪
话说，蒟蒻的Rating曲线越来越了难看了233
