首页 > 代码库 > Codeforces Round #279 (Div. 2) 题解集合
Codeforces Round #279 (Div. 2) 题解集合
终于有场正常时间的比赛了。。。毛子换冬令时还正是好啊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\n", ans);20 a = first[1], b = first[2], c = first[3];21 for (i = 1; i <= ans; ++i) {22 printf("%d %d %d\n", 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\n", 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\n", 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\n%I64d %I64d\n", 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", &n);39 ans[0] = 0;40 len = 0;41 for (i = 1; i <= n; ++i) {42 scanf("%s\n", 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\n", 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跪
Codeforces Round #279 (Div. 2) 题解集合
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。