Chapter 1
- 題意：有 12 個蟲洞，要配對成兩兩一組，一旦碰到蟲洞就會被傳送到另一端，且一直往 +X 方向移動，問有多少種組合能形成環？
- 這題是很好的題目，能練習實作暴搜。首先要會 DFS 枚舉組合，方法是每次找到第一個沒被用到的點，然後枚舉能和他匹配的點。之後再檢查每個組合是否有環，採取 BFS，每次走兩步，先一步蟲洞，再走到下一個點。
1/*
2ID: whitech1
3TASK: wormhole
4LANG: C++14
5*/
6#include <bits/stdc++.h>
7using namespace std;
8typedef pair<int, int> pii;
9#define x first
10#define y second
11int n, ans = 0;
12vector<pii> p;
13vector<vector<bool> > G;
14vector<int> pr;
15bool check() {
16 vector<int> visit(n);
17 queue<int> q;
18 for (int i = 0; i < n; i++) q.push(i);
19 while (!q.empty()) {
20 int u = q.front(); q.pop();
21 if (visit[u] > 2 * n) return true;
22 for (int i = 0; i < n; i++) {
23 if (G[pr[u]][i])
24 q.push(i), visit[i] = visit[u] + 2;
25 }
26 }
27 return false;
28}
29void per(int cnt) {
30 if (cnt == n) {
31 if (check()) ans++;
32 return;
33 }
34 for (int i = 0; i < n; i++) {
35 if (pr[i] != -1) continue;
36 for (int j = i + 1; j < n; j++) {
37 if (pr[j] != -1) continue;
38 pr[i] = j, pr[j] = i;
39 per(cnt + 2);
40 pr[i] = pr[j] = -1;
41 }
42 break;
43 }
44}
45int main() {
46 freopen("wormhole.in", "r", stdin);
47 freopen("wormhole.out", "w", stdout);
48 cin >> n;
49 p.resize(n), pr.resize(n, -1);
50 G.resize(n, vector<bool>(n));
51 for (int i = 0; i < n; i++)
52 cin >> p[i].x >> p[i].y;
53 sort(p.begin(), p.end());
54 for (int i = 0; i < n; i++)
55 for (int j = i + 1; j < n; j++)
56 if (p[i].y == p[j].y) {
57 G[i][j] = true;
58 break;
59 }
60 per(0);
61 cout << ans << '\n';
62 return 0;
63}
1/*
2ID: whitech1
3TASK: skidesign
4LANG: C++14
5*/
6#include <bits/stdc++.h>
7using namespace std;
8inline int d(int x) {return x * x;}
9int main() {
10 freopen("skidesign.in", "r", stdin);
11 freopen("skidesign.out", "w", stdout);
12 int n; cin >> n;
13 vector<int> v(n);
14 for (int i = 0; i < n; i++) cin >> v[i];
15 sort(v.begin(), v.end());
16 int ans = n * d(100);
17 for (int m = 0; m <= 100; m++) {
18 int cnt = 0;
19 for (int a : v)
20 if (a < m) cnt += d(m - a);
21 else if (a > m + 17) cnt += d(a - m - 17);
22 ans = min(ans, cnt);
23 }
24 cout << ans << '\n';
25 return 0;
26}
- 題意：枚舉 p * p + q * q (0 ≤ p, q ≤ m ≤ 250)序列中的長度為 n ≤ 25 的序列。時間為 5 秒。
- 作法：把序列先用
bool seq[2 * m * m + 1] 紀錄。枚舉前兩個元素來檢查序列。
1/*
2ID: whitech1
3TASK: ariprog
4LANG: C++14
5*/
6#include <bits/stdc++.h>
7using namespace std;
8typedef pair<int, int> pii;
9set<int> s;
10int main() {
11 freopen("ariprog.in", "r", stdin);
12 freopen("ariprog.out", "w", stdout);
13 int n, m; cin >> n >> m;
14 vector<int> sq(m + 1);
15 for (int i = 1; i <= m; i++) sq[i] = i * i;
16 for (int i = 0; i <= m; i++)
17 for (int j = i; j <= m; j++)
18 s.insert(sq[i] + sq[j]);
19 set<pii> ans;
20 vector<int> v(s.begin(), s.end());
21 vector<bool> seq(2 * m * m + 1);
22 for (int i : v) seq[i] = true;
23 for (int i : v) {
24 for (int j : v) {
25 if (i >= j) continue;
26 int d = j - i;
27 bool success = true;
28 for (int k = i + (n - 1) * d; k > j; k -= d)
29 if (k >= seq.size() || !seq[k]) {
30 success = false;
31 break;
32 }
33 if (success) ans.insert(pii(d, i));
34 }
35 }
36 for (auto i : ans) cout << i.second << " " << i.first << "\n";
37 if (!ans.size()) cout << "NONE\n";
38 return 0;
39}
- 題意：給定 1 ≤ A, B, C ≤ 20，三個桶子，問 A 桶為空時，C 有哪些可能的容量。
1/*
2ID: whitech1
3TASK: milk3
4LANG: C++14
5*/
6#include <bits/stdc++.h>
7using namespace std;
8int a, b, c;
9bool ans[25][25][25];
10void solve(int x, int y, int z) {
11 if (ans[x][y][z]) return;
12 ans[x][y][z] = true;
13 int d;
14 // A -> B
15 d = min(x, b - y);
16 solve(x - d, y + d, z);
17 // A -> C
18 d = min(x, c - z);
19 solve(x - d, y, z + d);
20 // B -> A
21 d = min(a - x, y);
22 solve(x + d, y - d, z);
23 // B -> C
24 d = min(y, c - z);
25 solve(x, y - d, z + d);
26 // C -> A
27 d = min(a - x, z);
28 solve(x + d, y, z - d);
29 // C -> B
30 d = min(b - y, z);
31 solve(x, y + d, z - d);
32}
33int main() {
34 freopen("milk3.in", "r", stdin);
35 freopen("milk3.out", "w", stdout);
36 cin >> a >> b >> c;
37 solve(0, 0, c);
38 for (int i = 0; i < c; i++)
39 if (c - i <= b && ans[0][c - i][i])
40 cout << i << ' ';
41 cout << c << '\n';
42 return 0;
43}
| Value |
Binary Sample |
Meaning |
x |
00101100 |
the original x value |
x & -x |
00000100 |
extract lowest bit set |
| `x |
-x` |
11111100 |
x ^ -x |
11111000 |
create mask bits to left of lowest bit set |
x & (x - 1) |
00101000 |
strip off lowest bit set |
| `x |
(x - 1)` |
00101111 |
x ^ (x - 1) |
00000111 |
create mask for lowest-set-bit & bits to its right |
~x & (x - 1) |
00000011 |
create mask for bits to right of lowest bit set |
| `x |
(x + 1)` |
00101101 |
x / (x & -x) |
00001011 |
shift number right so lowest set bit is at bit 0 |
1/*
2ID: whitech1
3TASK: numtri
4LANG: C++14
5*/
6#include <bits/stdc++.h>
7using namespace std;
8int main() {
9 freopen("numtri.in", "r", stdin);
10 freopen("numtri.out", "w", stdout);
11 int r; cin >> r;
12 vector<vector<int> > a(r);
13 for (int i = 0; i < r; i++) {
14 a[i].resize(i + 1);
15 for (int j = 0; j <= i; j++)
16 cin >> a[i][j];
17 }
18 for (int i = 1; i < r; i++)
19 for (int j = 0; j <= i; j++)
20 a[i][j] += max(a[i - 1][max(0, j - 1)],
21 a[i - 1][min(i - 1, j)]);
22 int ans = 0;
23 for (int j = 0; j < r; j++)
24 ans = max(ans, a[r - 1][j]);
25 cout << ans << '\n';
26 return 0;
27}
- 題意：找 [a, b] 中同時為迴文和質數的數。
- 方法：枚舉迴文，再檢查使否為質數，相反會超時。可以發現除了 11 以外的偶位數迴文都會被 11 整除，即非質數。
1/*
2ID: whitech1
3TASK: pprime
4LANG: C++14
5*/
6#include <bits/stdc++.h>
7using namespace std;
8vector<int> prime;
9bool isprime[10000];
10void gen_prime() {
11 prime.push_back(2);
12 for (int i = 3; i < 10000; i += 2) {
13 if (isprime[i]) continue;
14 prime.push_back(i);
15 for (int j = i * i; j < 10000; j += 2 * i)
16 isprime[j] = true;
17 }
18}
19bool check_prime(int x) {
20 for (int p : prime) {
21 if (p * p > x) return true;
22 if (x % p == 0) return false;
23 }
24 return true;
25}
26int num(int x) {
27 int ret = x;
28 vector<int> v;
29 while (x) {
30 v.push_back(x % 10);
31 x /= 10;
32 }
33 for (int i = 1; i < v.size(); i++)
34 ret = ret * 10 + v[i];
35 return ret;
36}
37int main() {
38 freopen("pprime.in", "r", stdin);
39 freopen("pprime.out", "w", stdout);
40 int a, b; cin >> a >> b;
41 gen_prime();
42 vector<int> ans;
43 int c[] = {2, 3, 5, 7, 11};
44 for (int i : c)
45 if (a <= i && i <= b)
46 ans.push_back(i);
47 for (int i = 10; i < 10000; i++) {
48 int x = num(i);
49 if (a <= x && x <= b && check_prime(x))
50 ans.push_back(x);
51 }
52 for (int i : ans) cout << i << "\n";
53 return 0;
54}
1/*
2ID: whitech1
3TASK: sprime
4LANG: C++14
5*/
6#include <bits/stdc++.h>
7using namespace std;
8vector<int> prime;
9bool isprime[10000];
10void gen_prime() {
11 prime.push_back(2);
12 for (int i = 3; i < 10000; i += 2) {
13 if (isprime[i]) continue;
14 prime.push_back(i);
15 for (int j = i * i; j < 10000; j += 2 * i)
16 isprime[j] = true;
17 }
18}
19bool check_prime(int x) {
20 if (x < 2) return false;
21 for (int p : prime) {
22 if (p * p > x) return true;
23 if (x % p == 0) return false;
24 }
25 return true;
26}
27vector<int> ans;
28void solve(int cnt, int n, int num) {
29 if (cnt == n) {
30 ans.push_back(num);
31 return;
32 }
33 for (int i = 1; i <= 9; i++) {
34 int d = num * 10 + i;
35 if (check_prime(d)) solve(cnt + 1, n, d);
36 }
37}
38int main() {
39 freopen("sprime.in", "r", stdin);
40 freopen("sprime.out", "w", stdout);
41 int n; cin >> n;
42 gen_prime();
43 solve(0, n, 0);
44 for (int i : ans) cout << i << '\n';
45 return 0;
46}
Chapter 2
- “Farthest to the west” 是指「最西邊」。
- 題意：給定每個房間的四道牆，問拆一道牆能形成的最大房間大小。
- 解法：Flood Fill 算出每個房間的大小，再試著拆每道牆。
1/*
2ID: whitech1
3TASK: castle
4LANG: C++14
5*/
6#include <bits/stdc++.h>
7using namespace std;
8const char D[5] = "WNES";
9const int dx[4] = {0, -1, 0, 1};
10const int dy[4] = {-1, 0, 1, 0};
11int main() {
12 freopen("castle.in", "r", stdin);
13 freopen("castle.out", "w", stdout);
14 int n, m; cin >> m >> n;
15 vector<vector<int> > w(n, vector<int>(m));
16 for (int i = 0; i < n; i++)
17 for (int j = 0; j < m; j++)
18 cin >> w[i][j];
19 vector<vector<int> > G(n, vector<int>(m));
20 vector<int> sz(1);
21 int mx = 0;
22 for (int i = 0; i < n; i++) {
23 for (int j = 0; j < m; j++) {
24 if (G[i][j]) continue;
25 queue<int> qx, qy;
26 qx.push(i), qy.push(j);
27 G[i][j] = sz.size();
28 sz.push_back(1);
29 while (!qx.empty()) {
30 int x = qx.front(); qx.pop();
31 int y = qy.front(); qy.pop();
32 for (int d = 0; d < 4; d++) {
33 if ((1 << d) & w[x][y]) continue;
34 int xx = x + dx[d], yy = y + dy[d];
35 if (G[xx][yy]) continue;
36 G[xx][yy] = G[x][y];
37 qx.push(xx), qy.push(yy);
38 sz.back()++;
39 }
40 }
41 mx = max(mx, sz.back());
42 }
43 }
44 cout << sz.size() - 1 << "\n" << mx << "\n";
45 mx = 0;
46 int ax, ay; char dir;
47 for (int j = 0; j < m; j++) {
48 for (int i = n - 1; i >= 0; i--) {
49 for (int d = 1; d <= 2; d++) {
50 if ((1 << d) & w[i][j]) {
51 int ii = i + dx[d], jj = j + dy[d];
52 if (ii < 0 || jj >= m) continue;
53 if (G[ii][jj] == G[i][j]) continue;
54 if (sz[G[i][j]] + sz[G[ii][jj]] > mx) {
55 mx = sz[G[i][j]] + sz[G[ii][jj]];
56 ax = i, ay = j, dir = D[d];
57 }
58 }
59 }
60 }
61 }
62 cout << mx << "\n" << ax + 1 << " " << ay + 1 << " " << dir << "\n";
63 return 0;
64}
- 題意：枚舉出 0 ~ 1 之間，分母最大為 N ≤ 160 的分數，依照大小印出。
- 解法：只將分子與分母互質的最簡分數(reduced fraction)放入，再定義大小排序。
1/*
2ID: whitech1
3TASK: frac1
4LANG: C++14
5*/
6#include <bits/stdc++.h>
7using namespace std;
8typedef pair<int, int> frac;
9#define x first
10#define y second
11bool cmp (const frac &a, const frac &b) {
12 return a.x * b.y < a.y * b.x;
13}
14int main() {
15 freopen("frac1.in", "r", stdin);
16 freopen("frac1.out", "w", stdout);
17 int n; cin >> n;
18 vector<frac> v;
19 v.push_back(frac(0, 1));
20 for (int i = 1; i <= n; i++)
21 for (int j = 1; j <= i; j++)
22 if (__gcd(i, j) == 1)
23 v.push_back(frac(j, i));
24 sort(v.begin(), v.end(), cmp);
25 for (frac f : v) cout << f.x << '/' << f.y << '\n';
26 return 0;
27}
- 題意：給定一個長度為 n ≤ 1000 的序列，元素只有 1, 2, 3，操作為將任意兩個位置的元素交換，問最少要幾個操作才能將序列排序？
- 解法：Greedy，先將陣列排序，和原陣列比較。若兩兩交換能到對的位置則交換，各消耗 1 次操作。其餘會形成 cycle，cycle 需要 2 次操作。
1/*
2ID: whitech1
3TASK: sort3
4LANG: C++14
5*/
6#include <bits/stdc++.h>
7using namespace std;
8int main() {
9 freopen("sort3.in", "r", stdin);
10 freopen("sort3.out", "w", stdout);
11 int n; cin >> n;
12 vector<int> a(n);
13 for (int i = 0; i < n; i++) cin >> a[i];
14 vector<int> b(a.begin(), a.end());
15 sort(b.begin(), b.end());
16 int c[4][4] = {};
17 for (int i = 0; i < n; i++)
18 if (a[i] != b[i]) c[a[i]][b[i]]++;
19 int ans = 0;
20 for (int i = 1; i < 3; i++) {
21 for (int j = i + 1; j <= 3; j++) {
22 int d = min(c[i][j], c[j][i]);
23 ans += d, c[i][j] -= d, c[j][i] -= d;
24 }
25 }
26 int tmp = 0;
27 for (int i = 1; i <= 3; i++)
28 for (int j = 1; j <= 3; j++)
29 tmp += c[i][j];
30 cout << ans + tmp * 2 / 3 << '\n';
31 return 0;
32}
- 題意：牛需要 V 種維他命。有 G 種飼料可選擇，問最少要選擇幾種飼料，才能使維他命的和達到牛所需的量。
- 解法：枚舉所有組合檢查。
- 複雜度：$$O(VG2^G)$$
1/*
2ID: whitech1
3TASK: holstein
4LANG: C++14
5*/
6#include <bits/stdc++.h>
7using namespace std;
8int main() {
9 freopen("holstein.in", "r", stdin);
10 freopen("holstein.out", "w", stdout);
11 int v; cin >> v;
12 vector<int> need(v);
13 for (int i = 0; i < v; i++) cin >> need[i];
14 int n; cin >> n;
15 vector<vector<int> > vit(n, vector<int>(v));
16 for (int i = 0; i < n; i++)
17 for (int j = 0; j < v; j++)
18 cin >> vit[i][j];
19 int N = 1 << n;
20 vector<vector<int> > dp(N, vector<int>(v));
21 int ans = n, id = N - 1;
22 for (int i = 0; i < N; i++) {
23 int cnt = 0;
24 for (int j = 0; j < n; j++) {
25 if ((1 << j) & i) cnt++;
26 else for (int r = 0, k = i | (1 << j); !dp[k][r] && r < v; r++)
27 dp[k][r] = dp[i][r] + vit[j][r];
28 }
29 bool success = true;
30 for (int r = 0; r < v; r++)
31 if (dp[i][r] < need[r]) success = false;
32 if (success) {
33 if (cnt < ans) ans = cnt, id = i;
34 else if (cnt <= ans) id = min(i, id);
35 }
36 }
37 cout << ans;
38 for (int i = 0; i < n; i++)
39 if (id & (1 << i)) cout << ' ' << i + 1;
40 cout << '\n';
41 return 0;
42}
- 題意：輸出一個大小為 N ≤ 64 的集合，裡面的元素長度為 B ≤ 8 個 bits，兩兩 Hamming distance 不小於 D ≤ 7。
- 解法：測資弱，直接暴力枚舉。用
__builtin_popcount(x) 算幾個 1-bit。
1/*
2ID: whitech1
3TASK: hamming
4LANG: C++14
5*/
6#include <bits/stdc++.h>
7using namespace std;
8typedef unsigned int ui;
9vector<ui> ans;
10bool success = false;
11int N, M, D, B;
12void dfs() {
13 if (success) return;
14 if (ans.size() == N) {
15 success = true;
16 sort(ans.begin(), ans.end());
17 for (int i = 0; i < N; i++)
18 cout << ans[i] << " \n"[i % 10 == 9 || i == N - 1];
19 return;
20 }
21 for (ui i = 0; i < M && !success; i++) {
22 bool add = true;
23 for (ui x : ans) {
24 if (__builtin_popcount(i ^ x) < D) {
25 add = false; break;
26 }
27 }
28 if (add) {
29 ans.push_back(i);
30 dfs();
31 ans.pop_back();
32 }
33 }
34}
35int main() {
36 freopen("hamming.in", "r", stdin);
37 freopen("hamming.out", "w", stdout);
38 int B; cin >> N >> B >> D;
39 M = 1 << B;
40 dfs();
41 return 0;
42}
- 題意：給定 N ≤ 3500，計算 1 ~ N 的羅馬字母表示法共用了每種字母個幾個。
1/*
2ID: whitech1
3TASK: preface
4LANG: C++14
5*/
6#include <bits/stdc++.h>
7using namespace std;
8int d[13] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
9string s[13] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
10int cnt[13];
11void solve(int x) {
12 for (int i = 0; i < 13; i++) {
13 cnt[i] += x / d[i];
14 x %= d[i];
15 }
16}
17int main() {
18 freopen("preface.in", "r", stdin);
19 freopen("preface.out", "w", stdout);
20 int n; cin >> n;
21 for (int i = 1; i <= n; i++) solve(i);
22 int ans[7] = {};
23 char c[8] = "IVXLCDM";
24 for (int i = 0; i < 13; i++)
25 for (int j = 0; j < 7; j++)
26 for (char ch : s[i])
27 if (ch == c[j]) ans[j] += cnt[i];
28 for (int i = 0; i < 7; i++)
29 if (ans[i]) cout << c[i] << ' ' << ans[i] << '\n';
30 return 0;
31}
- 題意：給定 N ≤ 39，計算 1 ~ N 有幾種分法能使兩堆一樣多。
1/*
2ID: whitech1
3TASK: subset
4LANG: C++14
5*/
6#include <bits/stdc++.h>
7using namespace std;
8inline int sum(int x) {return x * (x + 1) >> 1;}
9int main() {
10 freopen("subset.in", "r", stdin);
11 freopen("subset.out", "w", stdout);
12 int n; cin >> n;
13 int m = sum(n);
14 if (m & 1) {
15 cout << "0\n";
16 return 0;
17 }
18 m >>= 1;
19 vector<long long> dp(m + 1);
20 dp[0] = 1;
21 for (int i = 1; i <= n; i++)
22 for (int j = min(sum(i), m); j >= i; j--)
23 dp[j] += dp[j - i];
24 cout << (dp[m] >> 1) << '\n';
25 return 0;
26}
- 題意：給定 M ≤ 2^32，找出一個大於 M 的循環數。循環數的定義為，沒用到 0，且每個位元不重複，從第一個位元 d 開始向右走 d 位，走到最右邊則從最左邊繼續，然後在從此位繼續，走完全部回到第一位且不重複。
- 解法：DFS 暴搜所有解，不斷更新最小值剪枝。
1/*
2ID: whitech1
3TASK: runround
4LANG: C++14
5*/
6#include <bits/stdc++.h>
7using namespace std;
8typedef long long ll;
9ll m;
10vector<int> v;
11bool used[10];
12bool check(ll num, int len) {
13 if (num <= m) return false;
14 vector<int> cnt(len);
15 for (int i = 0, r = 0; i < len; i++) {
16 r = (r + v[r]) % len;
17 cnt[r]++;
18 }
19 for (int i = 0; i < len; i++)
20 if (!cnt[i]) return false;
21 return true;
22}
23ll ans = 987654321LL;
24void solve(ll now, int len) {
25 if (check(now, len)) ans = min(ans, now);
26 if (now >= ans) return;
27 for (int i = 1; i <= 9; i++) {
28 if (used[i]) continue;
29 used[i] = true, v.push_back(i);
30 solve(now * 10 + i, len + 1);
31 used[i] = false, v.pop_back();
32 }
33}
34int main() {
35 freopen("runround.in", "r", stdin);
36 freopen("runround.out", "w", stdout);
37 cin >> m;
38 solve(0, 0);
39 cout << ans << "\n";
40 return 0;
41}
- 題意：給定 N ≤ 100 和 C ≤ 10000。一開始有 N 盞燈，及四種按鈕，分別為所有燈、奇數燈、偶數燈、3K + 1 狀態改變。以及給定某些燈的狀態。C 為按下按鈕的總次數，求輸出所有最後可能的狀態。
- 解法：只需要考慮四種按鈕分別按下的奇偶性，以及和 C 的大小及奇偶是否一致。然後枚舉 16 種狀態去花 O(N) 確認。
1/*
2ID: whitech1
3TASK: lamps
4LANG: C++14
5*/
6#include <bits/stdc++.h>
7using namespace std;
8void input(vector<int> &v) {
9 int x;
10 while (cin >> x && x != -1) v.push_back(x);
11}
12int main() {
13 freopen("lamps.in", "r", stdin);
14 freopen("lamps.out", "w", stdout);
15 int n, c; cin >> n >> c;
16 vector<int> on, off;
17 input(on); input(off);
18 int start[4] = {1, 1, 2, 1}, step[4] = {1, 2, 2, 3};
19 set<string> s;
20 for (int state = 0; state < 16; state++) {
21 int d = __builtin_popcount(state);
22 if (d > c || (d + c) & 1) continue;
23 vector<bool> lamp(1 + n);
24 for (int r = 0; r < 4; r++)
25 if ((1 << r) & state)
26 for (int i = start[r]; i <= n; i += step[r])
27 lamp[i] = !lamp[i];
28 bool success = true;
29 for (int i : on)
30 if (lamp[i]) success = false;
31 for (int i : off)
32 if (!lamp[i]) success = false;
33 if (!success) continue;
34 string str = "";
35 for (int i = 1; i <= n; i++) str += "10"[lamp[i]];
36 s.insert(str);
37 }
38 if (s.empty()) cout << "IMPOSSIBLE\n";
39 else for (string str : s) cout << str << "\n";
40 return 0;
41}
- 題意：給定一個字串集合，大小 n ≤ 200，元素長度小魚 L ≤ 10，以及一個字串 S。問能用集合中元素組成的最長 S 前綴有多長？
- 解法：DP，O(nL|S|)。
1/*
2ID: whitech1
3TASK: prefix
4LANG: C++14
5*/
6#include <bits/stdc++.h>
7using namespace std;
8int main() {
9 freopen("prefix.in", "r", stdin);
10 freopen("prefix.out", "w", stdout);
11 string tmp;
12 vector<string> pr;
13 while (cin >> tmp && tmp != ".") pr.push_back(tmp);
14 string s = " ";
15 while (cin >> tmp) s += tmp;
16 vector<bool> dp(s.length() + 1);
17 int ans = 0;
18 dp[0] = true;
19 for (int i = 1; s[i]; i++) {
20 for (string p : pr) {
21 int l = p.length();
22 if (i >= l && p == s.substr(i - l + 1, l))
23 dp[i] = dp[i] || dp[i - l];
24 if (dp[i]) {ans = i; break;}
25 }
26 }
27 cout << ans << "\n";
28 return 0;
29}
- 題意：給定 N < 200 和 K < 100，每個點只能有 0 / 2 個子節點，求大小為 N 且深度為 K 的樹有多少種，答案 mod 9901。
- 解法：DP。
- 狀態：
dp[n][k] 代表大小為 n 且深度不超過 k 的樹有幾種。
- 轉移：O(N) 枚舉左右子樹的大小。
1/*
2ID: whitech1
3TASK: nocows
4LANG: C++14
5*/
6#include <bits/stdc++.h>
7using namespace std;
8#define mod 9901
9inline void add(int &a, int b) { a = (a + b) % mod; }
10int main() {
11 freopen("nocows.in", "r", stdin);
12 freopen("nocows.out", "w", stdout);
13 int n, k; scanf("%d%d", &n, &k);
14 int dp[200][100] = {};
15 for (int i = 1; i <= k; i++) dp[1][i] = 1;
16 for (int i = 1; i <= n; ++i)
17 for (int j = 1; j <= k; ++j)
18 for (int l = 1, r = i - 2; r >= 1; ++l, --r)
19 add(dp[i][j], dp[l][j - 1] * dp[r][j - 1]);
20 printf("%d\n", (dp[n][k] - dp[n][k - 1] + mod) % mod);
21 return 0;
22}
- 題意：給定 N ≤ 9，在 1 ~ N 之間插入
+ - ，問有哪些算式能得到 0？
- Ex.
1-2 3-4 5+6 7 = 1 - 23 - 45 + 67 = 0
- 解法：枚舉所有可能，用 python 的
eval() 計算。
- 複雜度：$$O(N3^N)$$
1"""
2ID: whitech1
3LANG: PYTHON3
4TASK: zerosum
5"""
6ans = []
7def enum(i, s, n):
8 s += str(i)
9 if i == n:
10 if eval(s.replace(' ', '')) == 0:
11 ans.append(s + '\n')
12 else:
13 for op in " +-":
14 enum(i + 1, s + op, n)
15fin = open ('zerosum.in', 'r')
16fout = open ('zerosum.out', 'w')
17n = int(fin.readline())
18enum(1, '', n)
19fout.writelines(ans)
20fin.close()
21fout.close()
- 題意：給定 V ≤ 25 種貨幣，問有幾種方法能組出 N ≤ 10000？
- 解法：無限 DP。
1/*
2ID: whitech1
3TASK: money
4LANG: C++14
5*/
6#include <bits/stdc++.h>
7using namespace std;
8int main() {
9 freopen("money.in", "r", stdin);
10 freopen("money.out", "w", stdout);
11 int v, n; cin >> v >> n;
12 vector<long long> dp(n + 1);
13 dp[0] = 1;
14 while (v--) {
15 int x; cin >> x;
16 for (int i = x; i <= n; i++)
17 dp[i] += dp[i - x];
18 }
19 cout << dp[n] << '\n';
20 return 0;
21}
- 題意：給定至多 m = 100 家公司，及他們的持股資訊。A 控制 B，當達到三種條件的其中一種，問共有幾種控制的 pair。
- A = B
- A 持有 B 的股票超過 50%
- A 控制的公司們持有 B 的股票和超過 50%
- 解法：當 x 控制 y 時，則將 y 持有的股票加到 x，當超過 50，則繼續 DFS。因為最多 O(m^2) 次，每次 O(m)，總時間複雜度 O(m^3)。
1#include <bits/stdc++.h>
2using namespace std;
3typedef pair<int, int> pii;
4bool cont[101][101];
5int block[101][101];
6void dfs(int i, int j) {
7 if (cont[i][j]) return;
8 cont[i][j] = true;
9 for (int k = 1; k <= 100; k++) {
10 block[i][k] += block[j][k];
11 if (block[i][k] > 50) dfs(i, k);
12 }
13}
14int main() {
15 freopen("concom.in", "r", stdin);
16 freopen("concom.out", "w", stdout);
17 int n; cin >> n;
18 queue<int> q;
19 while (n--) {
20 int i, j, p; cin >> i >> j >> p;
21 block[i][j] = p;
22 }
23 for (int i = 1; i <= 100; i++)
24 for (int j = 1; j <= 100; j++)
25 if (block[i][j] > 50) dfs(i, j);
26 for (int i = 1; i <= 100; i++)
27 for (int j = 1; j <= 100; j++)
28 if (i != j && cont[i][j])
29 cout << i << " " << j << "\n";
30 return 0;
31}
- 題意：給定一個 10 x 10 的地圖，Farmer 和 Cow 以同樣的方式行走，他們一開始皆面向北，每分鐘可行走一步，當遇到障礙物時，則花一分鐘順時鐘轉 90 度，請問要多久兩者才會相遇在同一格？若不相遇則輸出 0。
- 解法：模擬。最多有 10 x 10 x 4 = 400 種狀態，兩者則有 400 x 400 = 160000 種狀態，若他們並未相遇，則不可能會相遇。
1#include <bits/stdc++.h>
2using namespace std;
3char board[12][12];
4const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
5struct state {
6 int x, y, d;
7 state() {d = 0;}
8 state(int _x, int _y, int _d) {
9 x = _x, y = _y, d = _d;
10 }
11};
12inline bool same(state A, state B) {
13 return A.x == B.x && A.y == B.y;
14}
15inline bool ob(int i, int j) {
16 return !board[i][j] || board[i][j] == '*';
17}
18state next_state(state S) {
19 int xx = S.x + dx[S.d], yy = S.y + dy[S.d];
20 if (ob(xx, yy)) return state(S.x, S.y, (S.d + 1) % 4);
21 return state(xx, yy, S.d);
22}
23int main() {
24 freopen("ttwo.in", "r", stdin);
25 freopen("ttwo.out", "w", stdout);
26 state F, C;
27 for (int i = 1; i <= 10; i++) {
28 scanf(" %s", board[i] + 1);
29 for (int j = 1; j <= 10; j++)
30 if (board[i][j] == 'F') F.x = i, F.y = j;
31 else if (board[i][j] == 'C') C.x = i, C.y = j;
32 }
33 for (int i = 0; i <= 160000; i++) {
34 if (same(F, C)) {
35 cout << i << "\n";
36 return 0;
37 }
38 F = next_state(F), C = next_state(C);
39 }
40 cout << "0\n";
41 return 0;
42}
- 題意：給定一個 W x H 的地圖，W ≤ 38，H ≤ 100，最外面有兩個柵欄是開的，每個格子都能走到外圍，問離外圍最遠的格子有多遠？
- 解法：從外圍的點開始 BFS，複雜度 O(WH)。小技巧是在最外圍加上一圈障礙物，就不會 BFS 超出陣列範圍。
1#include <bits/stdc++.h>
2using namespace std;
3const int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
4int main() {
5 freopen("maze1.in", "r", stdin);
6 freopen("maze1.out", "w", stdout);
7 int w, h; cin >> w >> h; cin.ignore();
8 char c[205][80];
9 memset(c, '.', sizeof(c)); // 加上障礙物
10 for (int i = 2; i <= 2 * h + 2; i++)
11 cin.getline(c[i] + 2, 2 * w + 2);
12 int vst[205][80];
13 memset(vst, -1, sizeof(vst)); // 設為沒走過
14 queue<int> qx, qy;
15 // 放入外圈的點
16 for (int i = 1; i <= 2 * w + 3; i++) {
17 c[1][i] = c[2 * h + 3][i] = ' ';
18 vst[1][i] = vst[2 * h + 3][i] = 0;
19 qx.push(1), qy.push(i);
20 qx.push(2 * h + 3), qy.push(i);
21 }
22 for (int i = 1; i <= 2 * h + 3; i++) {
23 c[i][1] = c[i][2 * w + 3] = ' ';
24 vst[i][1] = vst[i][2 * w + 3] = 0;
25 qx.push(i), qy.push(1);
26 qx.push(i), qy.push(2 * w + 3);
27 }
28 int mx = 0;
29 // BFS
30 while (!qx.empty()) {
31 int x = qx.front(); qx.pop();
32 int y = qy.front(); qy.pop();
33 mx = vst[x][y]; // 最後走到的點就是答案
34 for (int d = 0; d < 4; d++) {
35 int xx = dx[d] + x, yy = dy[d] + y;
36 // 遇到障礙物或走過的點就跳過
37 if (c[xx][yy] != ' ' || vst[xx][yy] != -1) continue;
38 vst[xx][yy] = vst[x][y] + 1;
39 qx.push(xx), qy.push(yy);
40 }
41 }
42 cout << mx / 2 << '\n';
43 return 0;
44}
- 題意：給定一個大小為 N ≤ 150 的圖，這個圖為加上一條邊可聯通的非聯通圖。問加上一條邊後的最小直徑（diameter）為多少。
- 解法：先做一次 Floyd-Warshall 算出枚舉加入 (i, j)，i、j 兩聯通塊和 i、j 最遠的點距和 i、j 的距離相加，再和未聯通前的最大直徑比較。
1#include <bits/stdc++.h>
2using namespace std;
3const double INF = 40000000;
4inline double dst(int x, int y, int xx, int yy) {
5 double dx = x - xx, dy = y - yy;
6 return sqrt(dx * dx + dy * dy);
7}
8int main() {
9 freopen("cowtour.in", "r", stdin);
10 freopen("cowtour.out", "w", stdout);
11 ios::sync_with_stdio(0), cin.tie(0);
12 int n; cin >> n;
13 vector<int> x(n), y(n);
14 for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
15 vector<string> m(n);
16 for (int i = 0; i < n; i++) cin >> m[i];
17 vector<vector<double> > dis(n, vector<double>(n, 0));
18 for (int i = 0; i < n; i++)
19 for (int j = i + 1; j < n; j++)
20 dis[i][j] = dis[j][i] = dst(x[i], y[i], x[j], y[j]);
21 vector<vector<double> > dp(n, vector<double>(n, INF));
22 for (int i = 0; i < n; i++) {
23 dp[i][i] = 0;
24 for (int j = i + 1; j < n; j++)
25 if (m[i][j] == '1') dp[i][j] = dp[j][i] = dis[i][j];
26 }
27 for (int i = 0; i < n; i++)
28 for (int j = 0; j < n; j++)
29 for (int k = 0; k < n; k++)
30 dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k]);
31 vector<double> far(n, 0);
32 for (int i = 0; i < n; i++)
33 for (int j = 0; j < n; j++)
34 if (dp[i][j] + 1 < INF)
35 far[i] = max(far[i], dp[i][j]);
36 double ans = INF;
37 for (int i = 0; i < n; i++)
38 for (int j = i + 1; j < n; j++)
39 if (dp[i][j] + 1 > INF)
40 ans = min(ans, far[i] + far[j] + dis[i][j]);
41 for (int i = 0; i < n; i++) ans = max(ans, far[i]);
42 cout << fixed << setprecision(6) << ans << "\n";
43 return 0;
44}
- 題意：共有 A ~ Y 和 a ~ z 這些牧場，每個大寫字母的牧場都有一隻牛，給定 P ≤ 10000 條道路，問距離 Z 最近的牧場為何？
- 解法：Dijkstra 找最短距離，O(P log P)。
1#include <bits/stdc++.h>
2using namespace std;
3typedef pair<int, int> pii;
4const int INF = 100000000;
5inline int id(char c) {
6 if (isupper(c)) return c - 'A';
7 return c - 'a' + 26;
8}
9int main() {
10 freopen("comehome.in", "r", stdin);
11 freopen("comehome.out", "w", stdout);
12 int m; cin >> m;
13 vector<vector<pii> > G(52);
14 while (m--) {
15 char a, b; int w; cin >> a >> b >> w;
16 G[id(a)].push_back(pii(w, id(b)));
17 G[id(b)].push_back(pii(w, id(a)));
18 }
19 vector<int> dis(52, INF);
20 dis[id('Z')] = 0;
21 priority_queue<pii, vector<pii>, greater<pii> > pq;
22 pq.push(pii(0, id('Z')));
23 while (!pq.empty()) {
24 int u = pq.top().second; pq.pop();
25 if (u < 25) {
26 cout << char(u + 'A') << ' ' << dis[u] << '\n';
27 return 0;
28 }
29 for (pii e : G[u]) {
30 int uu = e.second, w = e.first;
31 if (dis[uu] > dis[u] + w) {
32 dis[uu] = dis[u] + w;
33 pq.push(pii(dis[uu], uu));
34 }
35 }
36 }
37 return 0;
38}
- 題意：給定 N 和 D ≤ 100000，求 N / Q 的循環小數表示。
- 解法：當餘數重複出現，則表示出現循環，餘數至多 D 種，所以複雜度 O(D)。
1#include <bits/stdc++.h>
2using namespace std;
3inline char dec(int x) {return x + '0';}
4string str(int x) {
5 string s = "";
6 while (x) {
7 s += char(x % 10 + '0');
8 x /= 10;
9 }
10 reverse(s.begin(), s.end());
11 return s;
12}
13void print(string s) {
14 for (int i = 0; s[i]; i++) {
15 cout << s[i];
16 if (i % 76 == 75 || i == s.length() - 1)
17 cout << "\n";
18 }
19}
20int main() {
21 freopen("fracdec.in", "r", stdin);
22 freopen("fracdec.out", "w", stdout);
23 ios::sync_with_stdio(0), cin.tie(0);
24 int N, D; cin >> N >> D;
25 int Q = N / D;
26 if (!N) {
27 cout << Q << ".0\n";
28 return 0;
29 }
30 N %= D;
31 vector<int> q, r;
32 vector<int> vst(D + 1, -1);
33 r.push_back(N), vst[N] = 0;
34 while (N) {
35 q.push_back(N * 10 / D);
36 r.push_back(N * 10 % D);
37 N = r.back();
38 if (vst[N] != -1) break;
39 vst[N] = q.size();
40 }
41 string ans = Q ? str(Q) : "0";
42 ans += ".";
43 int rep = vst[r.back()];
44 for (int i = 0; i < rep; i++) ans += dec(q[i]);
45 if (rep != r.size() - 1) {
46 ans += "(";
47 for (int i = rep; i < q.size(); i++)
48 ans += dec(q[i]);
49 ans += ")";
50 }
51 print(ans);
52 return 0;
53}
Chapter 3
- 題意：給 N ≤ 100 的 Adjacency Matrix，求 MST。
- 解法：做 Prim，複雜度 O(N^2)。
1#include <bits/stdc++.h>
2using namespace std;
3#define MAXN 105
4#define INF 100000000
5int main() {
6 freopen("agrinet.in", "r", stdin);
7 freopen("agrinet.out", "w", stdout);
8 int n; cin >> n;
9 int G[MAXN][MAXN];
10 for (int i = 0; i < n; i++)
11 for (int j = 0; j < n; j++)
12 cin >> G[i][j];
13 int dis[MAXN] = {};
14 for (int i = 1; i < n; i++) dis[i] = INF;
15 bool visit[MAXN] = {};
16 int ans = 0;
17 for (int i = 0; i < n; i++) {
18 int u = 0, mx = INF;
19 for (int j = 1; j < n; j++)
20 if (!visit[j] && dis[j] < mx)
21 u = j, mx = dis[j];
22 visit[u] = true;
23 ans += dis[u];
24 for (int i = 0; i < 100; i++)
25 dis[i] = min(dis[i], G[u][i]);
26 }
27 cout << ans << "\n";
28 return 0;
29}
1#include <bits/stdc++.h>
2using namespace std;
3#define MAXM 10005
4int main() {
5 freopen("inflate.in", "r", stdin);
6 freopen("inflate.out", "w", stdout);
7 int M, N; cin >> M >> N;
8 int dp[MAXM] = {};
9 while (N--) {
10 int w, t; cin >> w >> t;
11 for (int i = t; i <= M; i++)
12 dp[i] = max(dp[i], dp[i - t] + w);
13 }
14 cout << dp[M] << "\n";
15 return 0;
16}
- 題意：給定一個大小為 K ≤ 100 的質數集合，問第 N ≤ 100000 個質因數只有集合裡元素的數為何（不含 1）？
- 解法：如果用 priority_queue 會 MLE，用 set 會 TLE。用了 DP，不斷計算每個因數目前被用到最大的數為何，複雜度 O(NK)。
1#include <bits/stdc++.h>
2using namespace std;
3int main() {
4 freopen("humble.in", "r", stdin);
5 freopen("humble.out", "w", stdout);
6 int K, N; cin >> K >> N;
7 vector<int> v(K);
8 for (int i = 0; i < K; i++) cin >> v[i];
9 vector<int> dp(N + 1);
10 dp[0] = 1;
11 vector<int> p(K);
12 for (int i = 1; i <= N; i++) {
13 dp[i] = dp[p[0]] * v[0];
14 for (int j = 1; j < K; j++)
15 dp[i] = min(dp[i], dp[p[j]] * v[j]);
16 for (int j = 0; j < K; j++)
17 if (dp[i] == dp[p[j]] * v[j]) p[j]++;
18 }
19 cout << dp[N] << "\n";
20 return 0;
21}
- 題意：給定 1 ≤ a ≤ b ≤ 12 和 1 ≤ N ≤ 50，以及一個長度最長 200000 的 0/1 字串 S，問長度介於 [a, b] 的 0/1 字串和 S 有多少 match 次數，列出前 N 大的頻率的所有字串。
- 解法：將所有長度為 [a, b] 的子字串前綴加上
1 後 hash 丟進 map 計算次數，O(b|S|)。
1#include <bits/stdc++.h>
2using namespace std;
3typedef pair<int, string> pis;
4typedef pair<int, pis> piis;
5int a, b;
6string p;
7vector<piis> ans;
8int mp[(1 << 13)];
9void substring(string s) {
10 for (int r = a; r <= b; r++) {
11 int mask = 1 << r, now = 0;
12 for (int i = 0; s[i]; i++) {
13 now = ((now << 1) | (s[i] - '0')) & (mask - 1);
14 if (i >= r - 1) mp[now | mask]++;
15 }
16 }
17}
18void solve(int len) {
19 int pat = 0;
20 for (int i = 0; p[i]; i++) pat = (pat << 1) | (p[i] - '0');
21 pat |= (1 << len);
22 if (a <= len && mp[pat])
23 ans.push_back(piis(-mp[pat], pis(len, p)));
24 if (len >= b) return;
25 p += '0'; solve(len + 1); p.pop_back();
26 p += '1'; solve(len + 1); p.pop_back();
27}
28int main() {
29 freopen("contact.in", "r", stdin);
30 freopen("contact.out", "w", stdout);
31 ios::sync_with_stdio(0), cin.tie(0);
32 int n; cin >> a >> b >> n;
33 string s, ss;
34 while (cin >> ss) s += ss;
35 substring(s);
36 solve(0);
37 sort(ans.begin(), ans.end());
38 int sz = ans.size();
39 for (int i = 0, j = 0; i < n && j < sz; i++) {
40 int f = ans[j].first;
41 cout << -f << "\n";
42 vector<string> tmp;
43 for (; ans[j].first == f && j < sz; j++)
44 tmp.push_back(ans[j].second.second);
45 for (int k = 0; k < tmp.size(); k++)
46 cout << tmp[k] << " \n"[k % 6 == 5 || k == tmp.size() - 1];
47 }
48 return 0;
49}
- 題意：給定 N ≤ 50 種價值的郵票，最大價值 M ≤ 10000，問最多只用 K ≤ 200 種郵票，能湊出的數為 1 ~ 多少？
- 解法：DP。狀態 DP[i] 設為湊出 i 需要的最少數量，O(N) 轉移，複雜度為 O(MNK)。
1#include <bits/stdc++.h>
2using namespace std;
3int main() {
4 freopen("stamps.in", "r", stdin);
5 freopen("stamps.out", "w", stdout);
6 int k, n; cin >> k >> n;
7 vector<int> v(n);
8 int mx = 0;
9 for (int i = 0; i < n; i++) {
10 cin >> v[i];
11 mx = max(mx, v[i]);
12 }
13 mx *= k;
14 vector<int> dp(mx + 2, k + 1);
15 dp[0] = 0;
16 for (int i = 0; i <= mx; i++)
17 for (int j = 0; j < n; j++)
18 if (i >= v[j])
19 dp[i] = min(dp[i], dp[i - v[j]] + 1);
20 int ans = 0;
21 for (; dp[ans] <= k; ans++);
22 cout << ans - 1 << "\n";
23 return 0;
24}
- 題意：給定 N ≤ 4220，問 N! 最右邊的非零數字是多少？ Ex. 7! = 5040 是 4。
- 解法：只有 2 和 5 會產生 0 結尾，把他們提出來另外處理，其他就不斷相乘模 10，最後將多出的 2 或 5 乘上去模 10，複雜度 O(N log N)。
1#include <bits/stdc++.h>
2using namespace std;
3int main() {
4 freopen("fact4.in", "r", stdin);
5 freopen("fact4.out", "w", stdout);
6 int n; cin >> n;
7 int ans = 1, two = 0, five = 0;
8 for (int i = 1; i <= n; i++) {
9 int x = i;
10 while (x % 2 == 0) x /= 2, two++;
11 while (x % 5 == 0) x /= 5, five++;
12 ans = ans * x % 10;
13 }
14 for (int i = two; i < five; i++) ans = ans * 5 % 10;
15 for (int i = five; i < two; i++) ans = ans * 2 % 10;
16 cout << ans << "\n";
17 return 0;
18}
- 題意：給定 N ≤ 31，集合 S 包含所有 1-bit ≤ L 個的 N-bit 數，問集合 S 中的第 I 個數？
- 解法：遞迴檢查前綴為 s 的數在集合中有幾個，這部分可用排列組合計算，這樣就可以決定每一位要放 0 或 1。
C(a, b) 的部分是用不斷消去分子和分母的最大公因數。複雜度為 O(N^4)。要小心 I 最大為 2^31，要用 unsigned int。官方解答用 DP 算出 C(a, b)，複雜度可降到 O(N^2)。
1#include <bits/stdc++.h>
2using namespace std;
3typedef unsigned int ui;
4string s;
5int C(int a, int b) {
6 if (a < b) return 0;
7 vector<int> up, down;
8 for (int i = a; i > b; i--) up.push_back(i);
9 for (int i = a - b; i > 1; i--) down.push_back(i);
10 for (int i = 0; i < down.size(); i++) {
11 for (int j = 0; j < up.size(); j++) {
12 int g = __gcd(down[i], up[j]);
13 down[i] /= g, up[j] /= g;
14 }
15 }
16 int ret = 1;
17 for (int x : up) ret *= x;
18 return ret;
19}
20void solve(int len, int cnt, ui id) {
21 if (!len) return;
22 ui f = 0;
23 for (int i = cnt; i >= 0; i--) f += C(len - 1, i);
24 if (f < id) {
25 s += '1';
26 solve(len - 1, cnt - 1, id - f);
27 } else {
28 s += '0';
29 solve(len - 1, cnt, id);
30 }
31}
32int main() {
33 freopen("kimbits.in", "r", stdin);
34 freopen("kimbits.out", "w", stdout);
35 int N, L; ui I; cin >> N >> L >> I;
36 solve(N, L, I);
37 cout << s << "\n";
38 return 0;
39}
1#include <bits/stdc++.h>
2using namespace std;
3typedef pair<int, int> pii;
4int main() {
5 freopen("spin.in", "r", stdin);
6 freopen("spin.out", "w", stdout);
7 int speed[5];
8 vector<pii> w[5];
9 for (int i = 0; i < 5; i++) {
10 int x; cin >> speed[i] >> x;
11 w[i].resize(x);
12 for (int j = 0; j < x; j++) {
13 cin >> w[i][j].first >> w[i][j].second;
14 w[i][j].second += w[i][j].first;
15 }
16 }
17 int ans = -1;
18 for (int t = 0; t < 360 && ans == -1; t++) {
19 int check[360] = {};
20 for (int i = 0; i < 5; i++)
21 for (pii p : w[i])
22 for (int j = p.first; j <= p.second; j++)
23 check[(j + t * speed[i]) % 360]++;
24 for (int i = 0; i < 360; i++)
25 if (check[i] == 5) {ans = t; break;}
26 }
27 if (ans == -1) cout << "none\n";
28 else cout << ans << "\n";
29 return 0;
30}
1#include <bits/stdc++.h>
2using namespace std;
3int main() {
4 freopen("ratios.in", "r", stdin);
5 freopen("ratios.out", "w", stdout);
6 int mi = 1000;
7 int a[4][3];
8 for (int i = 0; i < 4; i++)
9 for (int j = 0; j < 3; j++)
10 cin >> a[i][j];
11 int c[4], ans[4];
12 for (c[1] = 0; c[1] < 100; ++c[1]) {
13 for (c[2] = 0; c[2] < 100; ++c[2]) {
14 for (c[3] = 0; c[3] < 100; ++c[3]) {
15 int cnt[3] = {}, t[3];
16 bool f = true;
17 int mx = 0;
18 for (int i = 0; i < 3; i++) {
19 for (int j = 1; j <= 3; j++) cnt[i] += c[j] * a[j][i];
20 if (!a[0][i] && !cnt[i]) t[i] = 0;
21 else if ((!a[0][i] && cnt[i]) || cnt[i] % a[0][i]) f = false;
22 else if (a[0][i]) t[i] = cnt[i] / a[0][i];
23 else t[i] = 0;
24 mx = max(mx, t[i]);
25 }
26 for (int i = 0; i < 3; i++)
27 if (mx * a[0][i] != cnt[i])
28 f = false;
29 if (f && (c[0] + c[1] + c[2]))
30 if (mi > c[0] + c[1] + c[2])
31 mi = c[0] + c[1] + c[2],
32 ans[0] = mx, ans[1] = c[1],
33 ans[2] = c[2], ans[3] = c[3];
34
35 }
36 }
37 }
38 if (mi < 1000) {
39 for (int i = 1; i < 4; i++) cout << ans[i] << " ";
40 cout << ans[0] << "\n";
41 }
42 else cout << "NONE\n";
43 return 0;
44}
- 題意：給定一個由 1 ~ 8 組成的 4 x 2 矩陣，及三種循環操作，求產生目標矩陣的最小操作數方法為何？
- 解法：BFS，因為狀態最多 8! 種，將狀態用 8 位整數儲存到 map 裡。
1#include <bits/stdc++.h>
2using namespace std;
3int c[3][8] = {{4, 5, 6, 7, 0, 1, 2, 3},
4 {3, 0, 1, 2, 7, 4, 5, 6},
5 {0, 5, 1, 3, 4, 6, 2, 7}};
6char ch[4] = "ABC";
7int change(int x, int r) {
8 int a[8] = {};
9 for (int i = 0; i < 8; i++) {
10 a[7 - i] = x % 10;
11 x /= 10;
12 }
13 int ret = 0;
14 for (int i = 0; i < 8; i++) ret = ret * 10 + a[c[r][i]];
15 return ret;
16}
17int main() {
18 freopen("msquare.in", "r", stdin);
19 freopen("msquare.out", "w", stdout);
20 int goal = 0;
21 int a[8];
22 for (int i = 0; i < 8; i++) cin >> a[i];
23 for (int i = 0; i < 4; i++) goal = goal * 10 + a[i];
24 for (int i = 7; i >= 4; i--) goal = goal * 10 + a[i];
25 map<int, string> m;
26 queue<int> state;
27 state.push(12348765);
28 m[12348765] = "";
29 while (!state.empty()) {
30 int s = state.front(); state.pop();
31 if (s == goal) break;
32 for (int i = 0; i < 3; i++) {
33 int ss = change(s, i);
34 if (m.find(ss) != m.end()) continue;
35 m[ss] = m[s] + ch[i];
36 state.push(ss);
37 }
38 }
39 cout << m[goal].length() << "\n" << m[goal] << "\n";
40 return 0;
41}
- 題意：給定 N ≤ 500 頭牛，共有 P ≤ 800 個農場和 C ≤ 1450 條路，問要將集合點設在哪，才能使牛隻們走的總距離最小？
- 解法：以每個點當起點做一次最短路，這邊用 Dijkstra，總複雜度 O(PC log C)。
1#include <bits/stdc++.h>
2using namespace std;
3typedef pair<int, int> pii;
4const int INF = 2000000000;
5int main() {
6 freopen("butter.in", "r", stdin);
7 freopen("butter.out", "w", stdout);
8 int n, p, c; cin >> n >> p >> c;
9 vector<int> v(n);
10 vector<vector<pii> > G(p + 1);
11 for (int i = 0; i < n; i++) cin >> v[i];
12 while (c--) {
13 int a, b, w; cin >> a >> b >> w;
14 G[a].push_back(pii(w, b));
15 G[b].push_back(pii(w, a));
16 }
17 int ans = INF;
18 for (int i = 1; i <= p; i++) {
19 vector<int> dis(p + 1, INF);
20 priority_queue<pii, vector<pii>, greater<pii> > pq;
21 dis[i] = 0, pq.push(pii(0, i));
22 while (!pq.empty()) {
23 int u = pq.top().second; pq.pop();
24 for (pii e : G[u]) {
25 int uu = e.second, w = e.first;
26 if (dis[uu] > dis[u] + w) {
27 dis[uu] = dis[u] + w;
28 pq.push(pii(dis[uu], uu));
29 }
30 }
31 }
32 int cnt = 0;
33 for (int x : v) cnt += dis[x];
34 ans = min(ans, cnt);
35 }
36 cout << ans << "\n";
37 return 0;
38}
- 題意：給定一個 500 個點以內無向的聯通圖，求找出 Euler Path/Circuit。
- 解法：如果有奇點就從它開始 DFS，否則從編號最小的點開始。
1#include <bits/stdc++.h>
2using namespace std;
3#define MAXN 505
4int G[MAXN][MAXN], deg[MAXN];
5vector<int> ans;
6void solve(int i) {
7 for (int j = 0; j < MAXN && deg[i]; j++)
8 while (G[i][j]) {
9 deg[j]--, deg[i]--, G[i][j]--, G[j][i]--;
10 solve(j);
11 }
12 ans.push_back(i);
13}
14int main() {
15 freopen("fence.in", "r", stdin);
16 freopen("fence.out", "w", stdout);
17 int F; cin >> F;
18 for (int i = 0; i < F; i++) {
19 int a, b; cin >> a >> b;
20 deg[a]++, deg[b]++, G[a][b]++, G[b][a]++;
21 }
22 for (int i = 0; i < MAXN; i++)
23 if (deg[i] & 1) { solve(i); break;}
24 for (int i = 0; i < MAXN; i++)
25 if (deg[i]) { solve(i); break;}
26 for (int i = ans.size() - 1; i >= 0; i--)
27 cout << ans[i] << "\n";
28 return 0;
29}
- 題意：給定 b ≤ 5 種東西及各自的單價和需要的數量 ≤ 5，以及 s ≤ 99 種組合，每種組合包含數種物品、數量及組合價，問能買到剛好所需物品的最低價格為何？
- 解法：DP，i 為把 b 種物品的量 hash 起來，DP[i] 表示其最低所需價格。
- 寫得好醜 QAQ
1#include <bits/stdc++.h>
2using namespace std;
3typedef pair<int, int> pii;
4int num(int id, int state) {
5 for (int i = 0; i < id; i++) state /= 10;
6 return state %= 10;
7}
8int main() {
9 freopen("shopping.in", "r", stdin);
10 freopen("shopping.out", "w", stdout);
11 ios::sync_with_stdio(0), cin.tie(0);
12 int s; cin >> s;
13 vector<vector<pii> > v(s);
14 vector<int> p(s);
15 for (int i = 0; i < s; i++) {
16 int n; cin >> n;
17 v[i].resize(n);
18 for (int j = 0; j < n; j++)
19 cin >> v[i][j].first >> v[i][j].second;
20 cin >> p[i];
21 }
22 int b; cin >> b;
23 vector<pii> r(b);
24 vector<int> dp(55556);
25 for (int i = 0; i < b; i++) {
26 int pp; cin >> r[i].first >> r[i].second >> pp;
27 for (int j = dp.size() - 1; j; j--) {
28 int cnt = num(i, j);
29 if (cnt <= r[i].second) dp[j] += cnt * pp;
30 }
31 }
32 int goal = 0;
33 for (int i = b - 1; i >= 0; i--)
34 goal = goal * 10 + r[i].second;
35 for (int i = 0; i < goal; i++) {
36 vector<int> state(b);
37 for (int j = 0; j < b; j++) state[j] = num(j, i);
38 for (int vi = 0; vi < s; vi++) {
39 bool success = true;
40 vector<int> new_state(state.begin(), state.end());
41 for (pii p : v[vi]) {
42 int id = -1;
43 for (int ii = 0; ii < b; ii++)
44 if (p.first == r[ii].first) id = ii;
45 if (id == -1) success = false;
46 new_state[id] += p.second;
47 }
48 for (int i = 0; i < b; i++)
49 if (new_state[i] > r[i].second) success = false;
50 if (!success) continue;
51 int st = 0;
52 for (int j = b - 1; j >= 0; j--)
53 st = st * 10 + new_state[j];
54 dp[st] = min(dp[st], dp[i] + p[vi]);
55 }
56 }
57 cout << dp[goal] << "\n";
58 return 0;
59}
- 寫的有點醜醜的，但其實不難寫，想的難度比較高。因為想不太到夠快的方法，所以就 Google 了一下。
- 題意：給定一個 R x C ≤ 30 x 26 的棋盤，棋盤上有一個 King 和多個 Knights，棋子可停留在同一格，當 King 和 Knights 在一起時，King 可帶著一個 Knight 照著 Knight 的走法走，問使得所有棋子都在同一格的最少步數？
- 解法：如果沒有 King 的話，這題就是對每個點做一次 BFS，最小距離和就是答案。而多了 King 的做法，就是將每個棋做一次 SPFA，紀錄到每一格以遇到 King 或未遇到的最小步數。
- 複雜度：假設棋子數量為 K。$$O(KRC)$$
1#include <bits/stdc++.h>
2using namespace std;
3typedef pair<int, int> pii;
4#define x first
5#define y second
6#define INF 100000000
7inline int step(pii k, pii p) {
8 return max(abs(k.x - p.x), abs(k.y - p.y));
9}
10inline bool range(pii p, int R, int C) {
11 return 0 <= p.x && 0 <= p.y && p.x < R && p.y < C;
12}
13int dis[1000][30][35][2];
14int main() {
15 freopen("camelot.in", "r", stdin);
16 freopen("camelot.out", "w", stdout);
17 int R, C;
18 cin >> R >> C;
19 int tmp_int;
20 char tmp_ch;
21 cin >> tmp_ch >> tmp_int;
22 pii king = {tmp_int - 1, tmp_ch - 'A'};
23 vector<pii> knight;
24 while (cin >> tmp_ch >> tmp_int)
25 knight.push_back({tmp_int - 1, tmp_ch - 'A'});
26 if (!knight.size()) {
27 cout << "0\n";
28 return 0;
29 }
30 for (int i = 0; i < knight.size(); i++)
31 for (int j = 0; j < R; j++)
32 for (int k = 0; k < C; k++)
33 dis[i][j][k][0] = dis[i][j][k][1] = INF;
34 const int dx[8] = {2, 2, 1, 1, -1, -1, -2, -2};
35 const int dy[8] = {1, -1, 2, -2, 2, -2, 1, -1};
36 for (int i = 0; i < knight.size(); i++) {
37 dis[i][knight[i].x][knight[i].y][0] = 0;
38 dis[i][knight[i].x][knight[i].y][1] = step(king, knight[i]);
39 queue<pii> q;
40 q.push(knight[i]);
41 while (!q.empty()) {
42 int xx = q.front().x, yy = q.front().y;
43 q.pop();
44 for (int di = 0; di < 8; di++) {
45 int a = xx + dx[di], b = yy + dy[di];
46 if (!range({a, b}, R, C)) continue;
47 bool inque = false;
48 if (dis[i][a][b][0] > dis[i][xx][yy][0] + 1) {
49 dis[i][a][b][0] = dis[i][xx][yy][0] + 1;
50 inque = true;
51 }
52 int d = min(dis[i][xx][yy][0] + step(king, {a, b}),
53 dis[i][xx][yy][1]) + 1;
54 if (dis[i][a][b][1] > d) {
55 dis[i][a][b][1] = d;
56 inque = true;
57 }
58 if (inque) q.push({a, b});
59 }
60 }
61 }
62 int ans = INF;
63 for (int i = 0; i < R; i++) {
64 for (int j = 0; j < C; j++) {
65 int mi = INF, sum = 0;
66 for (int k = 0; k < knight.size(); k++) {
67 sum += dis[k][i][j][0];
68 mi = min(mi, dis[k][i][j][1] - dis[k][i][j][0]);
69 }
70 ans = min(ans, sum + mi);
71 }
72 }
73 cout << ans << "\n";
74 return 0;
75}
- 題意：給定一棵二元樹的中序和前序，求輸出後序。
- 解法：用前序標出中間節點後遞迴。應該可以做到 O(n)，但因為懶，所以用了 O(n^2)。
1#include <bits/stdc++.h>
2using namespace std;
3string pre, in;
4void solve(int il, int ir, int pl, int pr) {
5 if (il > ir) return;
6 if (il == ir) { cout << in[il]; return; }
7 int i;
8 for (i = il; in[i] != pre[pl]; i++) {}
9 solve(il, i - 1, pl + 1, pl - il + i);
10 solve(i + 1, ir, pr - ir + i + 1, pr);
11 cout << pre[pl];
12}
13int main() {
14 freopen("heritage.in", "r", stdin);
15 freopen("heritage.out", "w", stdout);
16 cin >> in >> pre;
17 solve(0, in.length() - 1, 0, in.length() - 1);
18 cout << "\n";
19 return 0;
20}
- 題意：給定一個三角形，頂點為 (0, 0), (n, m), (p, 0)，介於 [0, 32000]x[0, 32000] 之間，問有幾個座標點是在三角形裡？
- 解法：對每個 y 都算一次邊上的座標，複雜度 O(m)。
- 官方解法：Pick’s Theorem。
1#include <bits/stdc++.h>
2using namespace std;
3int main() {
4 freopen("fence9.in", "r", stdin);
5 freopen("fence9.out", "w", stdout);
6 int n, m, p;
7 cin >> n >> m >> p;
8 int ans = 0;
9 for (int i = 1; i < m; i++)
10 ans += max(0, ((n + p) * i - 1) / m - n * i / m);
11 cout << ans << "\n";
12 return 0;
13}
- 題意：給定 n ≤ 20 首個歌的長度，共有 m ≤ 20 個唱片可以存放歌曲，每張唱片最多存 T ≤ 20 的長度，且存放時要按照輸入的順序，問最多能存幾首歌。
- 解法：枚舉放了哪些歌，然後 Greedy，O(n 2^n)。或是用 DP 做，O(nmT)。
1#include <bits/stdc++.h>
2using namespace std;
3int main() {
4 freopen("rockers.in", "r", stdin);
5 freopen("rockers.out", "w", stdout);
6 int n, m, t;
7 cin >> n >> t >> m;
8 vector<int> v(n);
9 for (int i = 0; i < n; i++) cin >> v[i];
10 int N = 1 << n;
11 int ans = 0;
12 for (int i = 1; i < N; i++) {
13 int c = __builtin_popcount(i);
14 if (c <= ans) continue;
15 int r = 0, cnt = 0;
16 for (int j = 0; j < n; j++) {
17 if ((1 << j) & i) {
18 if (v[j] > t) r = m;
19 if (cnt + v[j] > t)
20 r++, cnt = v[j];
21 else cnt += v[j];
22 }
23 }
24 if (r < m) ans = max(c, ans);
25 }
26 cout << ans << "\n";
27 return 0;
28}
Chapter 4
- 有點吃數論的題目～
- 題意：給定 N ≤ 10 個正整數 ≤ 256，求最大的正整數不能用這些數字組出來，若無限大則輸出 0。
- 解法：若 gcd 不為 1 則輸出 0，否則答案會在 256 x 256 以內，DP 解即可。
- 對於互質的正整數 a, b，最大不能得到的數為 ab - a - b。
1#include <bits/stdc++.h>
2using namespace std;
3int main() {
4 freopen("nuggets.in", "r", stdin);
5 freopen("nuggets.out", "w", stdout);
6 int n; cin >> n;
7 vector<int> a(n);
8 for (int i = 0; i < n; i++) cin >> a[i];
9 int g = a[0];
10 for (int x : a) g = __gcd(x, g);
11 if (g != 1) {
12 cout << "0\n";
13 return 0;
14 }
15 const int M = 256 * 256;
16 bool check[M + 300] = {1};
17 int ans = 0;
18 for (int i = 0; i < M; i++)
19 if (check[i])
20 for (int x : a)
21 check[i + x] = true;
22 else ans = i;
23 cout << ans << "\n";
24 return 0;
25}