Codeforces Round #107 (Div. 2)
几个月不参加 Codeforces 的比赛了，没有紧张的气氛，做得有点没感觉。前两题水过，第三题想复杂了，第四题当时没有想法，最后一题没心情看。比赛 URL: http://codeforces.com/contest/151 .
A 题 151A Soft Drinking 的背景是几个好朋友在一起喝饮料。其问题的实质是这样的：要制造一种物品，需要不同数量的不同原料；给出各种原料的数量和每件物品需要每种原料各多少，然后求最多能制造多少个这种物品。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | #include <climits> #include <iostream> #include <algorithm> using namespace std; int main() { int n, k, l, c, d, p, nl, np, r = INT_MAX; cin >> n >> k >> l >> c >> d >> p >> nl >> np; r = min(r, k * l / nl); r = min(r, c * d); r = min(r, p / np); cout << r / n << endl; return 0; } |
B 题 151B Phone Numbers 的背景是几个好朋友的电话本。某市的电话是 6 位数，都是以 22-22-22 这样的形式给出。有三种类型的电话，一种是计程车电话，其特点是电话每个数字都相同；一种是披萨外卖电话，其特点是几个数字是递减的；其余的是妹子的电话。最后问，拥有计程车的电话、披萨外卖电话和妹子的电话最多的人分别是谁。
后来看到别人的博客，里面说 B 题如果没有人有某种类型的电话，那么这个时候要把所有人的名字输出。但是我的代码里没有考虑这种情况，似乎这样也 AC 了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 | #include <cstdio> #include <string> #include <vector> #include <cctype> #include <iostream> using namespace std; inline bool is_taxi(const string &str) { char first = str[0]; for (int i = 0; i < str.size(); ++i) if (isdigit(str[i])) if (str[i] != first) return false; return true; } inline bool is_pizza(const string &str) { char previous = str[0]; for (int i = 1; i < str.size(); ++i) if (isdigit(str[i])) if (str[i] >= previous) return false; else previous = str[i]; return true; } inline int phone_type(const string &str) { if (is_taxi(str)) return 0; if (is_pizza(str)) return 1; return 2; } const char OUTPUT_FORMAT[3][128] = { "If you want to call a taxi, you should call: ", "If you want to order a pizza, you should call: ", "If you want to go to a cafe with a wonderful girl, you should call: " }; int best_count[3] = {0}; vector<string> best_names[3]; int main() { // freopen("input.txt", "r", stdin); int n; cin >> n; while (n--) { int s, cnt[3] = {0}; string name, phone; cin >> s >> name; while (s--) { cin >> phone; ++cnt[phone_type(phone)]; } for (int i = 0; i < 3; ++i) { if (cnt[i] > best_count[i]) { best_count[i] = cnt[i]; best_names[i].clear(); best_names[i].push_back(name); } else if (cnt[i] == best_count[i]) { best_names[i].push_back(name); } } } for (int i = 0; i < 3; ++i) { cout << OUTPUT_FORMAT[i]; if (!best_names[i].empty()) { cout << best_names[i][0]; for (int j = 1; j < best_names[i].size(); ++j) cout << ", " << best_names[i][j]; } cout << "." << endl; } return 0; } |
C 题 150A Win or Freeze 说的是两个人玩游戏，一开始 1 号玩家面临一个数 p, 如果他能写出 p 的一个非平凡因数 q, 就可以轮到玩家 2, 让他写出 q 的非平凡因数 r, … 直到某个玩家不能写为止，然后那个不能继续写数的玩家获胜。输入数据给出数 p, 问哪个玩家能获胜；如果 1 号玩家获胜，第二行要输出 1 号玩家应该写的数字是什么。如果 1 号玩家一开始就赢了，那么就在第二行输出 0.
这题一开始我的想法是，如果一个数是质数或者 1, 那么 1 号玩家就没法写数了，他就直接赢了。如果开始的数是两个质数的乘积，那么 1 号玩家只能写其中一个质因数，那 2 号玩家就赢了。如果是 > 2 个质因数，那 1 号玩家可以找出其中两个质因数，相乘，写出那个数给 2 号玩家，这样 2 号玩家只能写一个质数，然后 1 号就赢了。
这题的数据范围比较大，当时我居然想到用 Miller-Rabin 算法。开始的时候 pretest 7 总是过不了，赛后发现那个数据是 445538663413, 是一个比较大的质数，似乎让 Miller-Rabin 判断了几次都没判断出来，比赛时我也没发现，后来用一些小 trick 也算解决了这个问题（只是不能一开始就判断出是不是素数，浪费了一些时间罢了，算法看起来似乎还是对的）。后来赛后的 test 28 把我这题 WA 了，数据是 9999926826034, 这是 2 和一个 4999963413017 的乘积，似乎后者是质数，然后 Miller-Rabin 也把它判错了。
其实这题根本不用这么复杂的方法，直接试除就可以了，管你质数不质数的，找到两个约数，发现原数除完它们后不是 1, 玩家 1 就赢了；反之若是 1 就玩家 2 赢。如果找到 [latex]\sqrt{p}[/latex] 还是没有约数，那 p 就是质数了，还是玩家 1 赢。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | #include <iostream> using namespace std; typedef long long ll; int main() { int cnt = 0; ll p, d[2]; cin >> p; for (ll i = 2; i * i <= p; ++i) { while (p % i == 0) { p /= i; d[cnt] = i; if (++cnt >= 2) goto out; } } out: if (cnt == 0) cout << 1 << endl << 0 << endl; else if (p == 1 || cnt == 1) cout << 2 << endl; else cout << 1 << endl << d[0] * d[1] << endl; return 0; } |
D 和 E 到时候再研究一下吧，要加油啊。
2012 年 2 月 19 日更新：D 题 150B Quantity of Strings 的题解请点击这里。
原创文章，转载请注明来源：http://euyuil.com/3254/codeforces-round-107-div-2/
[...] 这道题是 Codeforces Round #107 (Div. 2) 中的 D 题。其题意是，给出 n, m, k 三个整数，问在字母表有 m [...]