1202 - Investigation
- 最短路徑水題
- Dijkstra
1#include<bits/stdc++.h>
2using namespace std;
3const int mod = 1000000007;
4typedef long long ll;
5typedef pair<ll, int> pii;
6#define pb push_back
7int main () {
8 ios_base::sync_with_stdio(0); cin.tie(0);
9 int n, m; cin >> n >> m;
10 vector<vector<pii>> G(n + 1);
11 for (int i = 0; i < m; i++) {
12 int a, b, c; cin >> a >> b >> c;
13 G[a].pb(pii(c, b));
14 }
15 vector<bool> visit(n + 1);
16 vector<ll> dis(n + 1, ll(m) * ll(1e9));
17 vector<ll> cnt(n + 1, 0), mn(n + 1), mx(n + 1);
18 dis[1] = 0, cnt[1] = 1;
19 priority_queue<pii, vector<pii>, greater<pii>> pq;
20 pq.push(pii(0, 1));
21 while (!pq.empty()) {
22 int u = pq.top().second; pq.pop();
23 if (visit[u]) continue;
24 visit[u] = true;
25 for (pii e : G[u]) {
26 int uu = e.second; ll w = e.first;
27 if (dis[uu] == dis[u] + w) {
28 cnt[uu] = (cnt[u] + cnt[uu]) % mod;
29 mn[uu] = min(mn[uu], mn[u] + 1);
30 mx[uu] = max(mx[uu], mx[u] + 1);
31 } else if (dis[uu] > dis[u] + w) {
32 dis[uu] = dis[u] + w;
33 cnt[uu] = cnt[u] % mod;
34 mn[uu] = mn[u] + 1;
35 mx[uu] = mx[u] + 1;
36 pq.push(pii(dis[uu], uu));
37 }
38 }
39 }
40 cout << dis[n] << " " << cnt[n] << " " << mn[n] << " " << mx[n] << "\n";
41 return 0;
42}1146 - Counting Bits
問 1 ~ n 的二進制表示法中，共有多少個 1-bit？
| 十進位 | $$2^2$$ | $$2^1$$ | $$2^0$$ |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 2 | 0 | 1 | 0 |
| 3 | 0 | 1 | 1 |
| 4 | 1 | 0 | 0 |
| 5 | 1 | 0 | 1 |
| 6 | 1 | 1 | 0 |
| 7 | 1 | 1 | 1 |
觀察 0/1 交替的方式，最末位是每隔 1 個，接下來是每隔 2 個，接下來是每隔 4 個…
1#include<bits/stdc++.h>
2using namespace std;
3typedef long long ll;
4int main() {
5 ll n, ans = 0;
6 cin >> n; n++;
7 for (ll i = 1; i <= n; i <<= 1) {
8 ll c = n / i;
9 if (c & 1) ans += c / 2 * i + n % i;
10 else ans += c / 2 * i;
11 }
12 cout << ans << "\n";
13 return 0;
14}11677 - Network Breakdown
題目是問給一張圖，每次刪除一條邊後，回答所剩的聯通塊數目。
用 Union Find Tree 維護聯通塊，離線倒著回答詢問，也就是一條一條加回去。
1#include<bits/stdc++.h>
2using namespace std;
3typedef pair<int, int> pii;
4#define x first
5#define y second
6vector<pii> remove(vector<pii> e, vector<pii> q) {
7 sort(q.begin(), q.end());
8 vector<pii> ret;
9 for (pii p : e) {
10 auto iter = lower_bound(q.begin(), q.end(), p);
11 if (iter == q.end() || *iter != p)
12 ret.push_back(p);
13 }
14 return ret;
15}
16struct UF {
17 int cnt;
18 vector<int> p, r;
19 UF(int n): cnt(n) {
20 p.resize(n + 1), r.resize(n + 1);
21 for (int i = 1; i <= n; i++) p[i] = i;
22 }
23 int par(int x) {
24 return p[x] = ((p[x] == x) ? x : par(p[x]));
25 }
26 void uni(int a, int b) {
27 a = par(a), b = par(b);
28 if (a == b) return;
29 if (r[a] < r[b]) {int t = a; a = b; b = t;}
30 p[b] = a, r[a] += (r[a] == r[b]), cnt--;
31 }
32};
33int main() {
34 ios::sync_with_stdio(0); cin.tie(0);
35 int n, m, k; cin >> n >> m >> k;
36 UF T(n);
37 vector<pii> e(m), q(k);
38 for (int i = 0; i < m; i++) {
39 int a, b; cin >> a >> b;
40 e[i] = pii(min(a, b), max(a, b));
41 }
42 for (int i = 0; i < k; i++) {
43 int a, b; cin >> a >> b;
44 q[i] = pii(min(a, b), max(a ,b));
45 }
46 e = remove(e, q);
47 for (pii p : e)
48 T.uni(p.x, p.y);
49 vector<int> ans;
50 reverse(q.begin(), q.end());
51 for (pii p : q) {
52 ans.push_back(T.cnt);
53 T.uni(p.x, p.y);
54 }
55 for(int i = k - 1; i >= 0 ; i--)
56 cout << ans[i] << " ";
57 return 0;
58}2189 - Point Location Test
基礎的幾何題。
1#include<bits/stdc++.h>
2using namespace std;
3typedef long long ll;
4typedef pair<ll, ll> point;
5#define x first
6#define y second
7ll check(point p[]) {
8 ll dx = p[1].x - p[0].x, dy = p[1].y - p[0].y;
9 return (p[2].y - p[1].y) * dx + (p[1].x - p[2].x) * dy;
10}
11int main () {
12 ios::sync_with_stdio(0), cin.tie(0);
13 int t; cin >> t;
14 while (t--) {
15 point p[3];
16 for (int i = 0; i < 3; i++)
17 cin >> p[i].x >> p[i].y;
18 ll c = check(p);
19 if (c > 0) cout << "LEFT\n";
20 else if (c < 0) cout << "RIGHT\n";
21 else cout << "TOUCH\n";
22 }
23 return 0;
24}2191 - Polygon Area
給一個簡單多邊形，輸出面積的兩倍。
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3using namespace std;
4typedef long long ll;
5typedef pair<ll, ll> pii;
6#define x first
7#define y second
8#define pb push_back
9ll det(vector<pii> &p, int n) {
10 ll cnt = 0;
11 for (int i = 0; i < n; i++)
12 cnt += p[i].x * p[i + 1].y - p[i + 1].x * p[i].y;
13 return (cnt > 0) ? cnt : -cnt;
14}
15int main() {
16 ios::sync_with_stdio(0), cin.tie(0);
17 int n; cin >> n;
18 vector<pii> p(n);
19 for (int i = 0; i < n; i++)
20 cin >> p[i].x >> p[i].y;
21 p.pb(p[0]);
22 cout << det(p, n) << "\n";
23 return 0;
24}2195 - Convex Hull
- 這題是要求在凸包上的所有點，所以
cross() < 0才需要拔掉。 cross的部分要記得開 long long，不然會溢位。
1// monotone chain
2#include<bits/stdc++.h>
3using namespace std;
4struct point {
5 long long x, y;
6 point() {}
7 point(long long _x, long long _y) { x = _x, y = _y;}
8 point operator-(const point p) {
9 return point(x - p.x, y - p.y);
10 }
11 long long cross(const point &p) {
12 return x * p.y - y * p.x;
13 }
14};
15static bool cmp(const point &a, const point &b) {
16 return (a.x < b.x) || (a.x == b.x && a.y < b.y);
17}
18void convex_hull(vector<point> p, vector<point> &h) {
19 sort(p.begin(), p.end(), cmp);
20 h.resize(p.size() + 1);
21 int m = 0;
22 for (int i = 0; i < p.size(); i++) {
23 while (m >= 2 &&
24 (h[m - 1] - h[m - 2]).cross(p[i] - h[m - 2]) < 0)
25 m--;
26 h[m++] = p[i];
27 }
28 for (int i = p.size() - 2, t = m + 1; i >= 0; i--) {
29 while (m >= t &&
30 (h[m - 1] - h[m - 2]).cross(p[i] - h[m - 2]) < 0)
31 m--;
32 h[m++] = p[i];
33 }
34 if (p.size() > 1) m--;
35 h.resize(m);
36}
37int main () {
38 ios::sync_with_stdio(0), cin.tie(0);
39 int n; cin >> n;
40 vector<point> P(n);
41 for (int i = 0; i < n; i++)
42 cin >> P[i].x >> P[i].y;
43 vector<point> H;
44 convex_hull(P, H);
45 cout << H.size() << "\n";
46 for (point p : H)
47 cout << p.x << " " << p.y << "\n";
48 return 0;
49}2205 - Gray Code
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3using namespace std;
4typedef long long ll;
5typedef pair<int, int> pii;
6int main() {
7 ios::sync_with_stdio(0), cin.tie(0);
8 int n; cin >> n;
9 for (int i = 0; i < (1 << n); i++) {
10 for (int j = n - 1; j >= 0; j--) {
11 int a = i >> j;
12 int b = a >> 1;
13 cout << ((a ^ b) & 1);
14 }
15 cout << '\n';
16 }
17 return 0;
18}1624 - Chessboard and Queens
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3using namespace std;
4bool a[8], b[20], c[20];
5char m[8][9];
6int ans = 0;
7void dfs (int i) {
8 if (i == 8) {
9 ans++;
10 return;
11 }
12 for (int j = 0; j < 8; j++) {
13 if (m[i][j] == '*') continue;
14 if (a[j] || b[i + j] || c[i - j + 8]) continue;
15 a[j] = b[i + j] = c[i - j + 8] = true;
16 dfs(i + 1);
17 a[j] = b[i + j] = c[i - j + 8] = false;
18 }
19}
20int main() {
21 ios::sync_with_stdio(0), cin.tie(0);
22 for (int i = 0; i < 8; i++) scanf(" %s", m[i]);
23 dfs(0);
24 printf("%d\n", ans);
25 return 0;
26}2183. Missing Coin Sum
1#include <bits/stdc++.h>
2using namespace std;
3int main() {
4 ios::sync_with_stdio(0), cin.tie(0);
5 int n;
6 cin >> n;
7 vector<int> v(n);
8 for (int i = 0; i < n; ++i)
9 cin >> v[i];
10 sort(v.begin(), v.end());
11 if (v[0] > 1) {
12 cout << "1\n";
13 return 0;
14 }
15 long long sum = v[0];
16 for (int i = 1; i < n; i++) {
17 if (sum < v[i] - 1) {
18 cout << sum + 1 << "\n";
19 return 0;
20 }
21 sum += v[i];
22 }
23 cout << sum + 1 << "\n";
24 return 0;
25}2216. Collecting Numbers
1#include <bits/stdc++.h>
2using namespace std;
3int main() {
4 ios::sync_with_stdio(0), cin.tie(0);
5 int n;
6 cin >> n;
7 vector<int> v(n);
8 for (int i = 0; i < n; i++)
9 cin >> v[i];
10 vector<int> pos(n + 1);
11 for (int i = 0; i < n; i++)
12 pos[v[i]] = i;
13 int ans = 1;
14 for (int i = 2; i <= n; i++)
15 if (pos[i - 1] > pos[i])
16 ans++;
17 cout << ans << "\n";
18 return 0;
19}2217. Collecting Numbers II
1#include <bits/stdc++.h>
2using namespace std;
3int main() {
4 ios::sync_with_stdio(0), cin.tie(0);
5 int n, q;
6 cin >> n >> q;
7 vector<int> v(n);
8 for (int i = 0; i < n; i++)
9 cin >> v[i];
10 vector<int> pos(n + 1);
11 for (int i = 0; i < n; i++)
12 pos[v[i]] = i;
13 int ans = 1;
14 for (int i = 2; i <= n; i++)
15 if (pos[i - 1] > pos[i])
16 ans++;
17 while (q--) {
18 int a, b;
19 cin >> a >> b;
20 a--, b--;
21 int va = v[a];
22 int vb = v[b];
23 swap(v[a], v[b]);
24 set<int> s {max(va, 2), min(va + 1, n), max(vb, 2), min(vb + 1, n)};
25 for (int i : s)
26 if (pos[i - 1] > pos[i])
27 ans--;
28 pos[va] = b, pos[vb] = a;
29 for (int i : s)
30 if (pos[i - 1] > pos[i])
31 ans++;
32 cout << ans << "\n";
33 }
34 return 0;
35}1753. String Matching
1#include <bits/stdc++.h>
2using namespace std;
3void z_build(string &s, vector<int> &z) {
4 int bst = z[0] = 0;
5 for (int i = 1; s[i]; ++i) {
6 if (z[bst] + bst < i) z[i] = 0;
7 else z[i] = min(z[bst] + bst - i, z[i - bst]);
8 while (s[z[i]] == s[i + z[i]]) ++z[i];
9 if (z[i] + i > z[bst] + bst) bst = i;
10 }
11}
12int z_match(string &s, string &t) {
13 int ans = 0;
14 int lens = s.length(), lent = t.length();
15 vector<int> z(lens + lent + 1);
16 string st = s + "$" + t;
17 z_build(st, z);
18 for (int i = lens + 1; st[i]; ++i)
19 if (z[i] == lens) ++ans;
20 return ans;
21}
22int main() {
23 ios::sync_with_stdio(0), cin.tie(0);
24 string s, p;
25 cin >> s >> p;
26 cout << z_match(p, s) << '\n';
27 return 0;
28}1680 - Longest Flight Route
- 找點 1 到點 n 的最長路徑。
- 拓樸排序＋DP。
1// DP on DAG
2// Topological Sort
3#pragma GCC optimization ("O3")
4#include<bits/stdc++.h>
5using namespace std;
6typedef long long ll;
7typedef pair<int, int> pii;
8#define pb push_back
9
10int main() {
11 ios::sync_with_stdio(0), cin.tie(0);
12 int n, m;
13 cin >> n >> m;
14 vector<vector<int>> G(n + 1);
15 vector<int> par(n + 1);
16 vector<int> deg(n + 1);
17 vector<int> dis(n + 1, -1e9);
18 dis[1] = 0;
19 for (int i = 0; i < m; i++) {
20 int a, b;
21 cin >> a >> b;
22 G[a].pb(b);
23 deg[b]++;
24 }
25 queue<int> q;
26 for (int i = 1; i <= n; i++) {
27 if (!deg[i]) {
28 q.push(i);
29 }
30 }
31 while (!q.empty()) {
32 int u = q.front();
33 q.pop();
34 for (int uu : G[u]) {
35 deg[uu]--;
36 if (!deg[uu]) {
37 q.push(uu);
38 }
39 if (dis[uu] < dis[u] + 1) {
40 dis[uu] = dis[u] + 1;
41 par[uu] = u;
42 }
43 }
44 }
45 if (dis[n] < 0) {
46 cout << "IMPOSSIBLE\n";
47 } else {
48 vector<int> ans;
49 int v = n;
50 while (v) {
51 ans.pb(v);
52 v = par[v];
53 }
54 cout << ans.size() << "\n";
55 for (int i = ans.size() - 1; i >= 0; i--) {
56 cout << ans[i] << " \n"[!i];
57 }
58 }
59 return 0;
60}1682 - Flight Routes Check
- 判斷圖是不是一個 SCC，若不是找一對 (a, b) 使得 a 走不到 b。
- Tarjan Algorithm。
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3using namespace std;
4typedef long long ll;
5typedef pair<int, int> pii;
6#define pb push_back
7
8vector<vector<int>> G;
9vector<int> visit;
10vector<int> low;
11vector<int> id;
12vector<bool> inStk;
13stack<int> st;
14int t;
15
16void dfs(int u) {
17 visit[u] = low[u] = ++t;
18 st.push(u);
19 inStk[u] = true;
20 for (int uu : G[u]) {
21 if (!visit[uu]) {
22 dfs(uu);
23 }
24 if (inStk[uu])
25 low[u] = min(low[u], low[uu]);
26 }
27 if (visit[u] == low[u]) {
28 while (1) {
29 int uu = st.top();
30 st.pop();
31 inStk[uu] = false;
32 id[uu] = u;
33 if (uu == u) {
34 break;
35 }
36 }
37 }
38}
39
40vector<int> SCC(int n) {
41 inStk.resize(n);
42 visit.resize(n);
43 low.resize(n);
44 id.resize(n, -1);
45 t = 0;
46 for (int i = 0; i < n; i++) {
47 if (!visit[i]) {
48 dfs(i);
49 }
50 }
51 vector<int> ret;
52 for (int i = 0; i < n; i++) {
53 if (id[i] == i) {
54 ret.pb(i);
55 }
56 }
57 return ret;
58}
59
60int main() {
61 ios::sync_with_stdio(0), cin.tie(0);
62 int n, m;
63 cin >> n >> m;
64 G.resize(n);
65 for (int i = 0; i < m; i++) {
66 int a, b;
67 cin >> a >> b;
68 a--, b--;
69 G[a].pb(b);
70 }
71 auto ans = SCC(n);
72 if (ans.size() == 1) {
73 cout << "YES\n";
74 } else {
75 cout << "NO\n";
76 for (int i = 0; i < n; i++) {
77 for (int j : G[i]) {
78 if (id[i] != id[j]) {
79 cout << j + 1 << " " << i + 1 << "\n";
80 return 0;
81 }
82 }
83 }
84 // all components are SCC
85 cout << ans[0] + 1 << " " << ans[1] + 1 << "\n";
86 }
87 return 0;
88}1087 - Shortest Subsequence
- 給一個字串 S，找一個最短字串 P 使得 P 不是 S 的子字串。
- Greedy。
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3using namespace std;
4typedef long long ll;
5typedef pair<int, int> pii;
6#define pb push_back
7
8int main() {
9 ios::sync_with_stdio(0), cin.tie(0);
10 string s;
11 cin >> s;
12 vector<int> a(s.length());
13 for (int i = 0; s[i]; i++) {
14 if (s[i] == 'A') a[i] = 1;
15 else if (s[i] == 'C') a[i] = 2;
16 else if (s[i] == 'G') a[i] = 4;
17 else a[i] = 8;
18 }
19 int st = 0; // Bit Set
20 vector<int> ans;
21 for (int i = 0; i < a.size(); i++) {
22 st = st | a[i];
23 if (st == 15) {
24 st = 0;
25 ans.pb(a[i]);
26 }
27 }
28 for (int i = 1; i <= 8; i <<= 1) {
29 if ((st & i) == 0) {
30 ans.pb(i);
31 break;
32 }
33 }
34 string out = "";
35 for (int i = 0; i < ans.size(); i++) {
36 if (ans[i] == 1) out += "A";
37 else if (ans[i] == 2) out += "C";
38 else if (ans[i] == 4) out += "G";
39 else out += "T";
40 }
41 cout << out << "\n";
42 return 0;
43}1756 - Acyclic Graph Edges
- 給一個無向圖，求輸出一個 Acyclic Orientation 的構造。
- Greedy 另小的點指向大的點，則必無環。
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, m;
7 cin >> n >> m;
8 for (int i = 0; i < m; i++) {
9 int a, b;
10 cin >> a >> b;
11 if (a > b) swap(a, b);
12 cout << a << " " << b << "\n";
13 }
14 return 0;
15}1688 - Company Queries II
- LCA 模板題。
1#include<bits/stdc++.h>
2using namespace std;
3#pragma GCC optimization ("O3")
4#include<bits/stdc++.h>
5using namespace std;
6typedef long long ll;
7typedef pair<int, int> pii;
8#define pb push_back
9
10class SparseTableTarjan {
11 private:
12 int maxlg;
13 vector<vector<int>> anc;
14 vector<int> dep;
15 void dfs(int u, vector<vector<int>>& edge, int d) {
16 dep[u] = d;
17 for (int i = 1; i < maxlg; i++)
18 if (anc[u][i - 1] == -1) break;
19 else anc[u][i] = anc[anc[u][i - 1]][i - 1];
20 for (int a : edge[u]) {
21 if (dep[a] != -1) continue;
22 anc[a][0] = u;
23 dfs(a, edge, d + 1);
24 }
25 }
26 public:
27 SparseTableTarjan(vector<vector<int>>& edge, int root) {
28 int n = edge.size();
29 maxlg = ceil(log2(n));
30 anc.assign(n, vector<int>(maxlg, -1));
31 dep.assign(n, -1);
32 dfs(root, edge, 0);
33 }
34 int lca(int a, int b) {
35 if (dep[a] > dep[b]) swap(a, b);
36 for (int k = 0; dep[b] - dep[a]; k++)
37 if (((dep[b] - dep[a]) >> k) & 1) b = anc[b][k];
38 if (a == b) return a;
39 for (int k = maxlg - 1; k >= 0; k--)
40 if (anc[a][k] != anc[b][k])
41 a = anc[a][k], b = anc[b][k];
42 return anc[a][0];
43 }
44 int dist(int a, int b) {
45 return dep[a] + dep[b] - 2 * dep[lca(a, b)];
46 }
47};
48
49int main() {
50 ios::sync_with_stdio(0), cin.tie(0);
51 int n, q;
52 cin >> n >> q;
53 vector<vector<int>> G(n);
54 for (int i = 1; i < n; i++) {
55 int p;
56 cin >> p;
57 p--;
58 G[i].pb(p);
59 G[p].pb(i);
60 }
61 SparseTableTarjan ST(G, 0);
62 while (q--) {
63 int a, b;
64 cin >> a >> b;
65 cout << ST.lca(a - 1, b - 1) + 1 << "\n";
66 }
67 return 0;
68}Josephus Problem I
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3using namespace std;
4typedef long long ll;
5typedef pair<int, int> pii;
6#define pb push_back
7
8int main() {
9 ios::sync_with_stdio(0), cin.tie(0);
10 int n;
11 cin >> n;
12 if (n == 1) {
13 cout << "1\n";
14 return 0;
15 }
16 vector<bool> die(n);
17 cout << 2;
18 for (int i = 1, p = 0; i < n; i++) {
19 die[p] = true;
20 while(die[p]) {
21 p = (p + 1) % n;
22 }
23 p = (p + 1) % n;
24 while(die[p]) {
25 p = (p + 1) % n;
26 }
27 cout << ' ' << (p + 1) % n + 1;
28 }
29 cout << '\n';
30 return 0;
31}