pJ. Inverse Factorial
- 給定一個長度不超過 1e6 的字串，代表 n!，求 n 是多少？
- 答案的範圍不超過 1e6，所以可以直接 mod 一個夠大的質數
1#include<bits/stdc++.h>
2using namespace std;
3#define mod 1000000007
4typedef long long ll;
5int main () {
6 ios_base::sync_with_stdio(0); cin.tie(0);
7 string s; cin >> s;
8 ll sum = 0;
9 for (int i = 0; s[i]; i++)
10 sum = (sum * 10 + s[i] - '0') % mod;
11 for (ll i = 1, frac = 1; ; i++) {
12 frac = (frac * i) % mod;
13 if (frac == sum) {
14 cout << i << "\n"; break;
15 }
16 }
17 return 0;
18}Tic Tac Toe
給定一個 3x3 的棋盤，問是不是合法的。
1#include<bits/stdc++.h>
2using namespace std;
3
4bool check(char t[3][4]) {
5 for (int i = 0; i < 3; i++) {
6 if (t[i][0] != '.' && t[i][0] == t[i][1]
7 && t[i][1] == t[i][2]) return false;
8 if (t[0][i] != '.' && t[0][i] == t[1][i]
9 && t[1][i] == t[2][i]) return false;
10 }
11 if (t[0][0] != '.' && t[0][0] == t[1][1]
12 && t[1][1] == t[2][2]) return false;
13 if (t[0][2] != '.' && t[0][2] == t[1][1]
14 && t[1][1] == t[2][0]) return false;
15 return true;
16}
17
18bool solve() {
19 char c[3][4];
20 int cnt[2] = {};
21 for (int i = 0; i < 3; i++) {
22 cin >> c[i];
23 for (int j = 0; j < 3; j++) {
24 if (c[i][j] == 'X') cnt[0]++;
25 if (c[i][j] == 'O') cnt[1]++;
26 }
27 }
28 if (!cnt[0] && !cnt[1]) return true;
29 if (cnt[0] < cnt[1] || cnt[0] - cnt[1] > 1)
30 return false;
31 char last = "XO"[cnt[0] == cnt[1]];
32 for (int i = 0; i < 3; i++) {
33 for (int j = 0; j < 3; j++) {
34 if (c[i][j] != last) continue;
35 c[i][j] = '.';
36 if (check(c)) return true;
37 c[i][j] = last;
38 }
39 }
40 return false;
41}
42
43int main () {
44 ios::sync_with_stdio(0), cin.tie(0);
45 int n; cin >> n;
46 while (n--) {
47 if (solve()) cout << "yes\n";
48 else cout << "no\n";
49 }
50 return 0;
51}Skener
1#include<bits/stdc++.h>
2using namespace std;
3int main () {
4 int r, c, a, b;
5 scanf("%d%d%d%d", &r, &c, &a, &b);
6 char s[55];
7 for (int i = 0; i < r; i++) {
8 scanf(" %s", s);
9 for (int j = 0; j < a; j++) {
10 for (int k = 0; k < c; k++)
11 for (int p = 0; p < b; p++)
12 putchar(s[k]);
13 putchar('\n');
14 }
15 }
16 return 0;
17}Printing Costs
1#include<bits/stdc++.h>
2using namespace std;
3int main () {
4 string s = " !\"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~";
5 int a[] = {0, 9, 6, 24, 29, 22,
6 24, 3, 12, 12 ,17, 13,
7 7, 7, 4, 10, 22, 19,
8 22, 23, 21, 27, 26, 16,
9 23, 26, 8, 11, 10, 14,
10 10, 15, 32, 24, 29, 20,
11 26, 26, 20, 25, 25, 18,
12 18, 21, 16, 28, 25, 26,
13 23, 31, 28, 25, 16, 23,
14 19, 26, 18, 14, 22, 18,
15 10, 18, 7, 8, 3, 23,
16 25, 17, 25, 23, 18, 30,
17 21, 15, 20, 21, 16, 22,
18 18, 20, 25, 25, 13, 21,
19 17, 17, 13, 19, 13, 24,
20 19, 18, 12, 18, 9 };
21 ios::sync_with_stdio(0); cin.tie(0);
22 string input;
23 while (1) {
24 getline(cin, input);
25 if (cin.fail()) break;
26 int cnt = 0;
27 for (int i = 0; input[i]; i++)
28 for (int j = 0; s[j]; j++)
29 if (input[i] == s[j]) {
30 cnt += a[j];
31 break;
32 }
33 cout << cnt << "\n";
34 }
35 return 0;
36}Touchscreen Keyboard
1#include<bits/stdc++.h>
2using namespace std;
3
4string board[3] = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
5
6int x[26], y[26];
7
8int main () {
9 for (int i = 0; i < 3; i++) {
10 for (int j = 0; board[i][j]; j++) {
11 int k = board[i][j] - 'a';
12 x[k] = i, y[k] = j;
13 }
14 }
15 ios::sync_with_stdio(0); cin.tie(0);
16 int T; cin >> T;
17 while (T--) {
18 string key; cin >> key;
19 int n; cin >> n;
20 vector< pair<int, string> > v;
21 for (int i = 0; i < n; i++) {
22 string s; cin >> s;
23 int cnt = 0;
24 for (int j = 0; s[j] && key[j]; j++) {
25 int a = s[j] - 'a', b = key[j] - 'a';
26 cnt += abs(x[a] - x[b]) + abs(y[a] - y[b]);
27 }
28 v.push_back(pair<int, string>(cnt, s));
29 }
30 sort(v.begin(), v.end());
31 for (auto r : v)
32 cout << r.second << " " << r.first << "\n";
33 }
34 return 0;
35}Kattis - Pivot
1#include<bits/stdc++.h>
2using namespace std;
3int main () {
4 ios::sync_with_stdio(0), cin.tie(0);
5 int n; cin >> n;
6 vector<int> a(n);
7 for (int i = 0; i < n; i++) cin >> a[i];
8 vector<bool> check(n, true);
9 int mx = a[0];
10 for (int i = 0; i < n; i++) {
11 if (a[i] < mx) check[i] = false;
12 mx = max(mx, a[i]);
13 }
14 int mn = a[n - 1];
15 for (int i = n - 1; i >= 0; i--) {
16 if (a[i] > mn) check[i] = false;
17 mn = min(mn, a[i]);
18 }
19 int cnt = 0;
20 for (int i = 0; i < n; i++)
21 cnt += check[i];
22 cout << cnt << "\n";
23 return 0;
24}Prva
1#include<bits/stdc++.h>
2using namespace std;
3int main () {
4 ios::sync_with_stdio(0), cin.tie(0);
5 int r, c;
6 cin >> r >> c;
7 vector<string> v(r);
8 for (int i = 0; i < r; i++)
9 cin >> v[i];
10 string ans = "{";
11 for (int i = 0; i < r; i++) {
12 string tmp = "";
13 for (int j = 0; j < c; j++) {
14 if (v[i][j] == '#') {
15 if (tmp.length() >= 2)
16 ans = min(ans, tmp);
17 tmp = "";
18 } else tmp += v[i][j];
19 }
20 if (tmp.length() >= 2)
21 ans = min(ans, tmp);
22 }
23 for (int j = 0; j < c; j++) {
24 string tmp = "";
25 for (int i = 0; i < r; i++) {
26 if (v[i][j] == '#') {
27 if (tmp.length() >= 2)
28 ans = min(ans, tmp);
29 tmp = "";
30 } else tmp += v[i][j];
31 }
32 if (tmp.length() >= 2)
33 ans = min(ans, tmp);
34 }
35 cout << ans << "\n";
36 return 0;
37}Jane Eyre
覺得 input 格式很難處理～
1#include<bits/stdc++.h>
2using namespace std;
3typedef pair<string, int> psi;
4typedef pair<int, psi> pisi;
5typedef long long ll;
6psi split(string s) {
7 bool flag = false;
8 for (int i = 0; s[i]; i++) {
9 if (flag && s[i] == ' ') s[i] = '$';
10 else if (s[i] == '\"') {
11 if (flag) break;
12 flag = true;
13 }
14 }
15 stringstream ss;
16 ss.clear(); ss.str(s);
17 string name;
18 int page;
19 ss >> name >> page;
20 for (int i = 0; name[i]; i++)
21 if (name[i] == '$') name[i] = ' ';
22 return psi(name, page);
23}
24int main () {
25 ios::sync_with_stdio(0), cin.tie(0);
26 int n, m, k; cin >> n >> m >> k;
27 priority_queue<psi, vector<psi>, greater<psi> > pq;
28 psi goal = psi("\"Jane Eyre\"", k);
29 pq.push(goal);
30 for (int i = 0; i < n; i++) {
31 string s1, s2;
32 cin >> s1;
33 getline(cin, s2);
34 pq.push(split(s1 + s2));
35 }
36 priority_queue<pisi, vector<pisi>, greater<pisi> > pq2;
37 for (int i = 0; i < m; i++) {
38 int t; cin >> t;
39 string s; getline(cin, s);
40 pq2.push(pisi(t, split(s)));
41 }
42 ll time = 0;
43 while (1) {
44 while (!pq2.empty()) {
45 if (pq.empty() || pq2.top().first <= time) {
46 pq.push(pq2.top().second);
47 pq2.pop();
48 } else break;
49 }
50 if (pq.empty()) break;
51 time += pq.top().second;
52 if (pq.top() == goal) break;
53 pq.pop();
54 }
55 cout << time << "\n";
56 return 0;
57}Sim
原本想用 Linked List 做，但後來發現 deque 比較好寫。
1#include<bits/stdc++.h>
2using namespace std;
3int main () {
4 ios::sync_with_stdio(0); cin.tie(0);
5 int T; cin >> T; cin.ignore();
6 while (T--) {
7 string s;
8 getline(cin, s);
9 deque<string> dq;
10 dq.push_front("");
11 int state = 0;
12 for (int i = 0; s[i]; i++) {
13 if (s[i] == '<') {
14 if (!state) {
15 if (dq.front() != "")
16 dq.front().pop_back();
17 } else {
18 if (dq.back() != "")
19 dq.back().pop_back();
20 }
21 } else if (s[i] == '[') {
22 if (dq.front() != "")
23 dq.push_front("");
24 state = 0;
25 } else if (s[i] == ']') {
26 state = -1;
27 } else {
28 if (state) dq.back().push_back(s[i]);
29 else dq.front().push_back(s[i]);
30 }
31 }
32 string ans;
33 while (!dq.empty()) {
34 ans += dq.front();
35 dq.pop_front();
36 }
37 cout << ans << "\n";
38 }
39 return 0;
40}Teque
1#include<bits/stdc++.h>
2using namespace std;
3int main () {
4 ios::sync_with_stdio(0); cin.tie(0);
5 int N; cin >> N;
6 deque<int> dq1, dq2;
7 while (N--) {
8 string op; cin >> op;
9 int x; cin >> x;
10 if (op == "push_back") {
11 dq2.push_back(x);
12 } else if (op == "push_front") {
13 dq1.push_front(x);
14 } else if (op == "push_middle") {
15 int sz1 = (dq1.size() + dq2.size() + 1) / 2;
16 while (dq1.size() < sz1) {
17 dq1.push_back(dq2.front());
18 dq2.pop_front();
19 }
20 while (dq1.size() > sz1) {
21 dq2.push_front(dq1.back());
22 dq1.pop_back();
23 }
24 dq1.push_back(x);
25 } else if (op == "get") {
26 if (dq1.size() > x)
27 cout << dq1[x] << "\n";
28 else cout << dq2[x - dq1.size()] << "\n";
29 }
30 }
31 return 0;
32}Continuous Median
1#include<bits/stdc++.h>
2using namespace std;
3int main () {
4 ios::sync_with_stdio(0); cin.tie(0);
5 int T; cin >> T;
6 while (T--) {
7 int n; cin >> n;
8 priority_queue<int> pq1;
9 priority_queue<int, vector<int>, greater<int> > pq2;
10 pq1.push(-1), pq2.push(2e9);
11 long long ans = 0;
12 for (int i = 0; i < n; i++) {
13 int x; cin >> x;
14 if (pq2.size() >= pq1.size()) pq1.push(x);
15 else pq2.push(x);
16 while (pq1.top() > pq2.top()) {
17 pq1.push(pq2.top());
18 pq2.push(pq1.top());
19 pq1.pop(), pq2.pop();
20 }
21 if (i & 1) ans += (pq1.top() + pq2.top()) / 2;
22 else ans += pq1.top();
23 }
24 cout << ans << "\n";
25 }
26 return 0;
27}Almost Union-Find
1 ≤ n, m ≤ 1e5，有三種操作：
1 p q代表將 p 和 q 所屬的集合合併。2 p q代表將 p 移到 q 所屬的集合。3 p為查詢 p 所屬集合大小及元素和。
操作 2 較難處理，方法為創出新的節點，並將元素指向新的節點。
1#include<bits/stdc++.h>
2using namespace std;
3int main () {
4 ios::sync_with_stdio(0); cin.tie(0);
5 int n, m;
6 while (cin >> n >> m) {
7 vector<long long> sum(n + 1);
8 vector<int> sz(n + 1, 1), par(n + 1), point(n + 1);
9 for (int i = 1; i <= n; i++)
10 par[i] = sum[i] = point[i] = i;
11 while (m--) {
12 int op, p, q; cin >> op;
13 if (op == 2) {
14 cin >> p >> q;
15 int pp = p;
16 pp = point[pp], q = point[q];
17 while (pp != par[pp]) pp = par[pp];
18 while (q != par[q]) q = par[q];
19 if (pp == q) continue;
20 sz[pp]--, sum[pp] -= p;
21 point[p] = par.size();
22 par.push_back(q);
23 sz[q]++, sum[q] += p;
24 } else if (op == 1) {
25 cin >> p >> q;
26 p = point[p], q = point[q];
27 while (p != par[p]) p = par[p];
28 while (q != par[q]) q = par[q];
29 if (p == q) continue;
30 if (sz[p] > sz[q]) {
31 int t = p; p = q; q = t;
32 }
33 par[p] = q;
34 sum[q] += sum[p];
35 sz[q] += sz[p];
36 } else if (op == 3) {
37 cin >> p;
38 p = point[p];
39 while (p != par[p]) p = par[p];
40 cout << sz[p] << " " << sum[p] << "\n";
41 }
42 }
43 }
44 return 0;
45}Thank God it’s Friday
1#include<bits/stdc++.h>
2using namespace std;
3string M[12] = {"JAN", "FEB", "MAR", "APR", "MAY", "JUN",
4 "JUL", "AUG", "SEP", "OCT", "NOV", "DEC"};
5int cnt[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
6string W[7] = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"};
7int main () {
8 int d;
9 string m, w;
10 cin >> d >> m >> w;
11 for (int i = 0; M[i] != m; i++)
12 d += cnt[i];
13 int day = d - 1;
14 for (int i = 0; W[i] != w; i++)
15 day++;
16 day %= 7;
17 if (m == M[0] || m == M[1]) {
18 if (day == 4) cout << "TGIF\n";
19 else cout << ":(\n";
20 } else {
21 if (day == 4 || day == 3) cout << "not sure\n";
22 else cout << ":(\n";
23 }
24 return 0;
25}Natrij
1h1, m1, s1 = [int(i) for i in input().split(':')]
2h2, m2, s2 = [int(i) for i in input().split(':')]
3s = ((h2 - h1 + 24) * 60 + m2 - m1) * 60 + s2 - s1
4if s % (24 * 3600) == 0:
5 print("24:00:00")
6else:
7 print('%02d:%02d:%02d' % (s // 3600 % 24, s // 60 % 60, s % 60) )Semafori
1#include<bits/stdc++.h>
2using namespace std;
3typedef pair<int, int> pii;
4typedef pair<int, pii> piii;
5#define x first
6#define y second
7int main () {
8 ios::sync_with_stdio(0), cin.tie(0);
9 int n, L; cin >> n >> L;
10 vector<piii> p(n);
11 for (int i = 0; i < n; i++)
12 cin >> p[i].x >> p[i].y.x >> p[i].y.y;
13 sort(p.begin(), p.end());
14 int cnt = 0;
15 for (int i = 0; i < n; i++) {
16 int t = p[i].x + cnt;
17 int cycle = p[i].y.x + p[i].y.y;
18 if (t % cycle < p[i].y.x)
19 cnt += p[i].y.x - t % cycle;
20 }
21 cout << L + cnt << "\n";
22 return 0;
23}Triple Texting
1s = input()
2L = len(s) // 3
3for i in range(L):
4 if s[i] == s[i + L]:
5 print(s[i], end = '')
6 else:
7 print(s[i + L + L], end = '')Functional Fun
1#include<bits/stdc++.h>
2using namespace std;
3bool input(set<string> &st) {
4 string s; cin >> s;
5 if (cin.fail()) return false;
6 getline(cin, s);
7 stringstream ss;
8 ss.clear(); ss.str(s);
9 while (ss >> s) st.insert(s);
10 return true;
11}
12int main () {
13 ios::sync_with_stdio(0); cin.tie(0);
14 while (1) {
15 set <string> domain, codomain;
16 if (!input(domain) || !input(codomain)) break;
17 int sz1 = domain.size(), sz2 = codomain.size();
18 int m; cin >> m;
19 bool surjective = true, injective = true;
20 bool function = true;
21 map<string, string> mp;
22 while (m--) {
23 string x, y, tmp; cin >> x >> tmp >> y;
24 if (mp.find(x) != mp.end()) {
25 if (mp[x] != y) function = false;
26 else continue;
27 }
28 mp[x] = y;
29 if (!codomain.count(y)) injective = false;
30 else codomain.erase(y);
31 }
32 if (codomain.size()) surjective = false;
33 if (!function) cout << "not a function\n";
34 else if (injective && surjective) cout << "bijective\n";
35 else if (injective) cout << "injective\n";
36 else if (surjective) cout << "surjective\n";
37 else cout << "neither injective nor surjective\n";
38 }
39 return 0;
40}Timebomb
1#include<bits/stdc++.h>
2using namespace std;
3string digit[5] = {"*** * *** *** * * *** *** *** *** *** ",
4 "* * * * * * * * * * * * * * ",
5 "* * * *** *** *** *** *** * *** *** ",
6 "* * * * * * * * * * * * * ",
7 "*** * *** *** * *** *** * *** *** "};
8int main () {
9 string s[5];
10 for (int i = 0; i < 5; i++) {
11 getline(cin, s[i]);
12 s[i] += " ";
13 }
14 int cnt = 0, len = s[0].length() / 4;
15 for (int i = 0; i < len; i++) {
16 int d = -1;
17 for (int j = 0; j <= 9; j++) {
18 bool check = true;
19 for (int x = 0; x < 5 && check; x++)
20 for (int y = 0; y < 4 && check; y++)
21 if (s[x][i * 4 + y] != digit[x][j * 4 + y])
22 check = false;
23 if (check) {d = j; break;}
24 }
25 if (d == -1) { cout << "BOOM!!\n"; return 0;}
26 else cnt = cnt * 10 + d;
27 }
28 if (cnt % 6) cout << "BOOM!!\n";
29 else cout << "BEER!!\n";
30 return 0;
31}Average Speed
1#include<bits/stdc++.h>
2using namespace std;
3int T(string s) {
4 int h = (s[0] - '0') * 10 + s[1] - '0';
5 int m = (s[3] - '0') * 10 + s[4] - '0';
6 int ss = (s[6] - '0') * 10 + s[7] - '0';
7 return (h * 60 + m) * 60 + ss;
8}
9void input(string s, int &op, int &speed, int &time) {
10 stringstream ss;
11 ss.clear(); ss.str(s);
12 ss >> s;
13 if (ss >> speed) op = 0;
14 else op = 1;
15 time = T(s);
16}
17int main () {
18 int cnt = 0, speed = 0, last = 0;
19 while (1) {
20 string s;
21 getline(cin, s);
22 if (cin.fail()) break;
23 int op, time, new_speed;
24 input(s, op, new_speed, time);
25 if (op) {
26 double dis = (cnt + (time - last) * speed) / 3600.0;
27 cout << s << " " << fixed << setprecision(2) << dis << " km\n";
28 } else {
29 cnt += (time - last) * speed;
30 speed = new_speed;
31 last = time;
32 }
33 }
34 return 0;
35}Circuit Math
1#include<bits/stdc++.h>
2using namespace std;
3int main () {
4 ios::sync_with_stdio(0); cin.tie(0);
5 int n; cin >> n;
6 vector<char> r(n);
7 for (int i = 0; i < n; i++)
8 cin >> r[i];
9 char c;
10 vector<bool> v;
11 while (cin >> c) {
12 if (c == '*') {
13 bool t = v.back();
14 v.pop_back();
15 v.back() = v.back() && t;
16 } else if (c == '+') {
17 bool t = v.back();
18 v.pop_back();
19 v.back() = v.back() || t;
20 } else if (c == '-') {
21 v.back() = !v.back();
22 } else {
23 v.push_back(r[c - 'A'] == 'T');
24 }
25 }
26 cout << "FT"[v.back()] << "\n";
27 return 0;
28}Three Powers
1while True:
2 n = int(input())
3 if n == 0:
4 break
5 n -= 1
6 now = 1
7 L = []
8 while n != 0:
9 if n & 1 == 1:
10 L.append(now)
11 n >>= 1
12 now *= 3
13 ans = ''
14 for i in L:
15 ans += ' ' + str(i) + ','
16 print('{' + ans[:-1] + ' }')Quick Brown Fox
1#include<bits/stdc++.h>
2using namespace std;
3int main () {
4 ios::sync_with_stdio(0); cin.tie(0);
5 int T; cin >> T; cin.ignore();
6 while (T--) {
7 string s; getline(cin, s);
8 int cnt[26] = {};
9 for (char c : s)
10 if (isupper(c)) cnt[c - 'A']++;
11 else if (islower(c)) cnt[c - 'a']++;
12 string ans = "";
13 for (int i = 0; i < 26; i++)
14 if (!cnt[i]) ans += i + 'a';
15 if (ans.length()) cout << "missing " << ans << "\n";
16 else cout << "pangram\n";
17 }
18 return 0;
19}Square Peg in a Round Hole
1#include<bits/stdc++.h>
2using namespace std;
3int main () {
4 int n, m, k; cin >> n >> m >> k;
5 vector<int> R(n);
6 for (int i = 0; i < n; i++) {
7 cin >> R[i];
8 R[i] *= 4 * R[i];
9 }
10 priority_queue<int> pq;
11 for (int i = 0; i < m; i++) {
12 int c; cin >> c;
13 pq.push(4 * c * c);
14 }
15 for (int i = 0; i < k; i++) {
16 int s; cin >> s;
17 pq.push(2 * s * s);
18 }
19 sort(R.begin(), R.end());
20 reverse(R.begin(), R.end());
21 int ans = 0;
22 for (int i = 0; i < n; i++) {
23 while (!pq.empty() && pq.top() >= R[i])
24 pq.pop();
25 if (!pq.empty())
26 pq.pop(), ans++;
27 }
28 cout << ans << '\n';
29 return 0;
30}Radio Commercials
1#include<bits/stdc++.h>
2using namespace std;
3int main () {
4 int n, p; cin >> n >> p;
5 int ans = 0, cnt = 0;
6 for (int i = 0; i < n; i++) {
7 int x; cin >> x;
8 cnt += x - p;
9 ans = max(ans, cnt);
10 cnt = max(cnt, 0);
11 }
12 cout << ans << "\n";
13 return 0;
14}Ultra-QuickSort
算逆序數對數量，9 ~ 11 行寫起來略卡。
1#include<bits/stdc++.h>
2using namespace std;
3typedef long long ll;
4vector<ll> v, tmp;
5ll inv(int l, int r) {
6 if (l >= r) return 0;
7 int m = (l + r) >> 1;
8 ll ret = inv(l, m) + inv(m + 1, r);
9 for (int i = l, j = m + 1, k = l; k <= r; k++)
10 if (i > m || (j <= r && v[i] > v[j])) tmp[k] = v[j++];
11 else tmp[k] = v[i++], ret += j - m - 1;
12 for (int i = l; i <= r; i++) v[i] = tmp[i];
13 return ret;
14}
15int main () {
16 int n; cin >> n;
17 v.resize(n), tmp.resize(n);
18 for (int i = 0; i < n; i++) cin >> v[i];
19 cout << inv(0, n - 1) << '\n';
20 return 0;
21}The Dragon of Loowater
1#include<bits/stdc++.h>
2using namespace std;
3int main () {
4 int n, m;
5 while (cin >> n >> m) {
6 if (!n && !m) break;
7 vector<int> a(n), b(m);
8 for (int i = 0; i < n; i++) cin >> a[i];
9 for (int i = 0; i < m; i++) cin >> b[i];
10 sort(a.begin(), a.end());
11 sort(b.begin(), b.end());
12 int ans = 0;
13 for (int i = 0, j = 0; i < n; i++) {
14 while (j < m && a[i] > b[j]) ++j;
15 if (j < m) ans += b[j++];
16 else { ans = -1; break;}
17 }
18 if (ans == -1) cout << "Loowater is doomed!\n";
19 else cout << ans << "\n";
20 }
21 return 0;
22}Postal Delivery
1#include<bits/stdc++.h>
2using namespace std;
3typedef pair<int, int> pii;
4typedef long long ll;
5ll solve(vector<pii> &v, int k) {
6 ll ret = 0;
7 sort(v.begin(), v.end());
8 while (v.size()) {
9 int cap = k;
10 ret += v.back().first;
11 while (v.size() && cap) {
12 int load = min(cap, v.back().second);
13 v.back().second -= load, cap -= load;
14 if (!v.back().second) v.pop_back();
15 }
16 }
17 return ret;
18}
19int main () {
20 int n, k; cin >> n >> k;
21 vector<pii> v[2];
22 for (int i = 0; i < n; i++) {
23 int x, t; cin >> x >> t;
24 if (x < 0) v[1].push_back(pii(-x, t));
25 else v[0].push_back(pii(x, t));
26 }
27 cout << (solve(v[0], k) + solve(v[1], k)) * 2 << "\n";
28 return 0;
29}Ladice
- Union-Find Tree，覺得題目出得很好。
1#include<bits/stdc++.h>
2using namespace std;
3struct UnionFind {
4 vector<int> p, r, sz;
5 UnionFind(int n) {
6 p.resize(n), r.resize(n, 1), sz.resize(n, 1);
7 for (int i = 0; i < n; i++) p[i] = i;
8 }
9 int par(int x) {
10 while (x != p[x]) x = p[x];
11 return x;
12 }
13 int size(int x) { return sz[par(x)]; }
14 void add(int x) { sz[par(x)]--; }
15 void uni(int a, int b) {
16 a = par(a), b = par(b);
17 if (a == b) return;
18 if (r[a] > r[b]) { int t = a; a = b; b = t; }
19 else if (r[a] == r[b]) r[b]++;
20 p[a] = b, sz[b] += sz[a];
21 }
22};
23int main () {
24 ios::sync_with_stdio(0), cin.tie(0);
25 int n, L; cin >> n >> L;
26 UnionFind uf(L);
27 for (int i = 0; i < n; i++) {
28 int a, b; cin >> a >> b;
29 uf.uni(--a, --b);
30 if (uf.size(a)) uf.add(a), cout << "LADICA\n";
31 else cout << "SMECE\n";
32 }
33 return 0;
34}Misa
1#include<bits/stdc++.h>
2using namespace std;
3int main () {
4 int r, s; cin >> r >> s;
5 vector<string> a(r);
6 for (int i = 0; i < r; i++) cin >> a[i];
7 int mx = 0, sum = 0;
8 for (int i = 0; i < r; i++) {
9 for (int j = 0; j < s; j++) {
10 int cnt = 0;
11 for (int dx = -1; dx <= 1; dx++) {
12 for (int dy = -1; dy <= 1; dy++) {
13 int x = i + dx, y = j + dy;
14 if (x < 0 || y < 0 ||
15 x >= r || y >= s) continue;
16 if (a[x][y] == 'o') cnt++;
17 }
18 }
19 if (a[i][j] == 'o') sum += cnt - 1;
20 else mx = max(mx, cnt);
21 }
22 }
23 cout << sum / 2 + mx << "\n";
24 return 0;
25}Relocation
1#include<bits/stdc++.h>
2using namespace std;
3int main () {
4 ios::sync_with_stdio(0), cin.tie(0);
5 int n, q; cin >> n >> q;
6 vector<int> v(n + 1);
7 for (int i = 1; i <= n; i++)
8 cin >> v[i];
9 while (q--) {
10 int op, a, b; cin >> op >> a >> b;
11 if (op == 1) v[a] = b;
12 else cout << abs(v[a] - v[b]) << "\n";
13 }
14 return 0;
15}Firefly
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3using namespace std;
4int main() {
5 ios::sync_with_stdio(0), cin.tie(0);
6 int n, h; cin >> n >> h;
7 vector<int> a(n);
8 for (int i = 0; i < n; i++) cin >> a[i];
9 vector<int> even(h + 1), odd(h + 1);
10 for (int i = 0; i < n; i += 2)
11 even[a[i]]++, odd[a[i + 1]]++;
12 for (int i = h - 2; i >= 1; i--)
13 even[i] += even[i + 1], odd[i] += odd[i + 1];
14 int ans = n, cnt = 0;
15 for (int i = 1; i <= h; i++) {
16 int sum = odd[h - i + 1] + even[i];
17 if (sum < ans) ans = sum, cnt = 1;
18 else if (sum == ans) cnt++;
19 }
20 cout << ans << " " << cnt << "\n";
21 return 0;
22}Alphabet
1#include<bits/stdc++.h>
2using namespace std;
3int main () {
4 string s; cin >> s;
5 int dp[30][55] = {};
6 for (int i = 0; i < 26; i++)
7 for (int j = 0; s[j]; j++)
8 if (s[j] == i + 'a')
9 dp[i + 1][j + 1] = dp[i][j] + 1;
10 else
11 dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
12 cout << 26 - dp[26][s.length()] << "\n";
13 return 0;
14}Walrus Weights
1#include<bits/stdc++.h>
2using namespace std;
3int main () {
4 ios::sync_with_stdio(0), cin.tie(0);
5 int n; cin >> n;
6 bool dp[2005] = {true};
7 for (int i = 0; i < n; i++) {
8 int x; cin >> x;
9 for (int j = 2000; j >= x; j--)
10 dp[j] = dp[j] | dp[j - x];
11 }
12 for (int i = 0; i <= 1000; i++)
13 if (dp[1000 + i]) {
14 cout << 1000 + i << "\n";
15 return 0;
16 } else if (dp[1000 - i]) {
17 cout << 1000 - i << "\n";
18 return 0;
19 }
20 return 0;
21}Add Two Numbers
1private fun readLn() = readLine()!!
2fun main() {
3 val (a, b) = readLn().split(' ').map { it.toInt() }
4 println(a + b)
5}Which is Greater?
1private fun readInts() = readLine()!!.split(' ').map{ it.toInt() }
2fun main() {
3 val (a, b) = readInts()
4 val ans = if (a > b) 1 else 0
5 println(ans)
6}Triangle Area
1private fun readLn() = readLine()!!
2fun main() {
3 val (a, b) = readLn().split(' ').map { it.toInt() }
4 println(a * b * 0.5)
5}