oToToT的code收藏區

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_aa 題目大意: 給你一些想註冊的帳號的順序，如果帳號在之前沒有被註冊走，則算是一個成功的註冊，這時要輸出現在是第幾次的註冊。 直接照著題目說的，拿個 STL 的 set 之類紀錄一下帳號有沒有被註冊過就好了。 #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); unordered_set<string> st; int n; cin >> n; for (int i = 1; i <= n; ++i) { string s; cin >> s; if (st.find(s) == st.end()) cout << i << '\n'; st.insert(s); } return 0; }

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_z 題目大意: 給一棵$n$個點的樹，要你找出$\frac{n}{2}$個彼此不相鄰的點。 隨意找個點當根，接著每個點按深度奇偶性分組，分成兩組後根據鴿籠原理(?)，一定有一組大小至少$\frac{n}{2}$，那他就可以是答案了。 #include <bits/stdc++.h> using namespace std; const int N = 100000 + 5; vector<int> G[N]; int c[N]; void dfs(int u, int f) { for (int v: G[u]) { if (v == f) continue; c[v] = c[u] ^ 1; dfs(v, u); } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } dfs(1, 1); vector<int> s[2]; for (int i = 1; i <= n; ++i) s[c[i]].push_back(i); if (s[0].size() < s[1].size()) { swap(s[0], s[1]); } for (int i = 0; i < n / 2; ++i) cout << s[0][i] << " \n"[i == n / 2 - 1]; return 0; }

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_y 題目大意: 定義$f(x)$代表把$x$用十進位表示後每個位數的積。 接著給定$N$, $B$，問有多少個$1$到$N$的數$m$滿足$m-f(m)=B$。 因為其實總共只有12位數而已，所以就真的爆搜所有$f(m)$的值，接著移項就可以拿到$m=B+f(m)$，也就可以真的驗$f(m)$是不是對的，然後統計起來就好了。 #include <bits/stdc++.h> using namespace std; using lld = int64_t; void dfs(int x, int d, vector<lld> &r, lld o) { r.push_back(o); if (d == 11) return; for (int i = x; i <= 9; ++i) dfs(i, d + 1, r, o * i); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); vector<lld> f{0}; dfs(2, 0, f, 1); lld n, b; cin >> n >> b; unordered_set<lld> s; for (lld x: f) { lld o = x + b; if (o > n) continue; lld t = 1; for (; o; o /= 10) t *= o % 10; if (t == x) s.insert(x + b); } cout << s.size() << '\n'; return 0; }

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_x 題目大意: 給定兩個序列 $A$, $B$，每次操作可以把$A$中任意元素$A_i$變成$A_i-1$或$A_i+1$，問可不可以恰$K$次後把$A$變成$B$。 隨手用python寫了一個XD 總之想法就是如果$A_i$比$B_i$小，那我們一定至少要花$B_i-A_i$次把$A_i$變成$B_i$，比較大的 case 也差不多，於是我們就有了一個基礎的下界$\sum |A_i-B_i|$，如果$K$比這個下界少，那一定不可能可以讓$A$跟$B$一樣。而若超過這個下界的話，實際上我們也可以透過一連串的$+1$跟$-1$操作來刻意浪費那些多出來的步數，所以再多判一下奇偶性就可以知道是不是一定可以有解了。(奇偶性一樣就可以靠前面說的方式構造，不同的話則因為我們每一步對應的奇偶性都是固定的，所以不同則一定構不出來) n, k = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) s = 0 for i in range(n): s += abs(a[i] - b[i]) print("Yes" if s <= k and s % 2 == k % 2 else "No")

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_w 題目大意: 給定一個 $H \times W$ 的棋盤，其中被標記為 # 的格子代表不能擺棋子。問有多少種方式可以在棋盤上擺一堆西洋棋的國王而不會造成至少一組國王可以立即攻擊到對方。 看完馬上想到 大根蘿蔔 ，這種題明顯要狀態壓縮 DP，狀態大概可以是 $dp[x][y][\text{mask}]$ 代表在 $(x, y)$ 的時候 $\text{mask}$ 裡面那些位置是可以擺的，然後轉移就真的看這格要不要擺之類的。 但如果真的無腦這樣做的話，複雜度會是 $O(H \times W \times 2^W)$ ，明顯會跑太久，不過仔細想了想就可以感受到合法狀態數絕對沒有這麼多，因為放一個就會蓋掉周遭之類的。 所以對於這種情況一個好方法就是我們可以先花 $W \times 2^W$ 的時間預處理真正合法的狀態，接著就可以 $O(H \times W \times X)$ (其中 $X$ 是真正可能的合法的狀態數) DP 掉了。 不過因為我很爛，從以前就一直不知道該怎麼好好寫這種預處理 DP，只知道這樣是可行的，所以這題最後跑去看 官解程式碼 才終於學會寫程式。 官解 同時也有稍微說明我上面的那個 $X$ 其實就是費式數列的某項，因為把蓋掉之後能再放的拿出來估一估差不多就會跟費式數列遞迴式一樣。 #include <bits/stdc++.h> using namespace std; static constexpr int C = 167761; static constexpr int N = 24; static constexpr int N2 = 1 << N; static constexpr int MOD = 1'000'000'007; inline int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; } string a[N]; unordered_map<int, pair<int, int>> mp[N]; int cnt[N], stat

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_v 題目大意: 給定一個 $A \times B \times C$ 的蛋糕，問最少要幾刀才能把蛋糕切成一堆等大的正方體。切的方法只能平行面且不能亂移蛋糕。 照著算 (?) 反正盡量大塊就是好的，所以切出來的就是邊長的最大公因數。 #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); uint64_t a, b, c; cin >> a >> b >> c; uint64_t r = gcd(a, gcd(b, c)); cout << (a / r) + (b / r) + (c / r) - 3 << '\n'; return 0; }

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_u 題目大意: 給定一個 $N$ 個點 $M$ 條邊的有向圖，問有多少 $(x, y)$ 可以互相走到。 SCC 定義就是可以互相走到會在一起，所以建個 SCC 並數每個 CC 裡有多少點就好了。 #include <bits/stdc++.h> using namespace std; class SCC { private: int n, num_; vector< vector< int > > G, rG; vector< int > ord, num; vector< bool > vis; void dfs( int u ) { if ( vis[ u ] ) return; vis[ u ] = 1; for ( int v : G[ u ] ) dfs( v ); ord.push_back( u ); } void rdfs( int u ) { if ( vis[ u ] ) return; num[ u ] = num_; vis[ u ] = 1; for ( int v : rG[ u ] ) rdfs(v); } public: inline void init( int n_ ) { n = n_, num_ = 0; G.clear(); G.resize( n ); rG.clear(); rG.resize( n ); vis.clear(); vis.resize( n ); num.resize( n ); } inline void add_edge( int st, int ed ) { G[ st ].push_back( ed ); rG[ ed ].push_back( st ); } void solve() { fill( vis.begin(), vis.end(), 0 ); for ( int i = 0 ; i < n ;

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_t 題目大意: 問你 $\log_2 a < b \log_2 c$ 會不會成立。 看了官解才發現不會爆 uint64_t = = 總之就是要只用整數做就對ㄌ #include <bits/stdc++.h> using namespace std; using llu = uint64_t; llu add(llu a, llu b) { if (a > numeric_limits<llu>::max() - b) { return numeric_limits<llu>::max(); } return a + b; } llu mul(llu a, int b) { llu r = 0; for (int i = 0; i < b; ++i) { r = add(r, a); } return r; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); llu a; int b, c; cin >> a >> b >> c; llu r = 1; for (int i = 0; i < b; ++i) { r = mul(r, c); } cout << (a < r ? "Yes" : "No") << '\n'; return 0; }

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_s 題目大意: 給定 $2N$ 個整數 $A_i$ ，現在可以花費 $|A_i - A_{i+1}|$ 的價格把相鄰兩項 $A_i$, $A_{i+1}$ 都刪掉。問把整個序列刪光的最小代價。 $N$ 很小，所以直接暴力 $O(N^4)$ DP 就好。$\text{DP}_{i, j}$ 代表把 $[i, j]$ 都刪掉的最小代價，轉移的話就直接枚舉刪光這個區間的最後一步是刪掉哪兩個數字就好了。 #include <bits/stdc++.h> using namespace std; const int INF = 1 << 29; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; n <<= 1; vector<int> a(n); for (int &ai : a) cin >> ai; vector<vector<int>> dp(n, vector<int>(n)); for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { dp[i][j] = INF; } } for (int len = 1; len < n; len += 2) { for (int i = 0; i + len < n; ++i) { // remove seg [i, j] const int j = i + len; for (int x = i; x <= j; x += 2) { for (int y = x + 1; y <= j; y += 2) { // remove [x, y] // left: [i, x - 1] // mid: [x + 1, y - 1] // right: [y + 1, j

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_r 題目大意: 在 $x=0$ 的平面上有一個高度為 $L$ 的摩天輪，其轉一圈要花費 $T$ 時間，並且其轉速固定。在時間點 $0$ 的時候某車廂座標為 $(0, 0, 0)$、$\frac{T}{4}$ 時座標為 $(0, -\frac{L}{2}, \frac{L}{2})$、$\frac{T}{2}$ 時座標為 $(0, 0, L)$、$\frac{3T}{4}$ 時座標為 $(0, \frac{L}{2}, \frac{L}{2})$。 現在有一個「高橋直大像」位在$(X, Y, 0)$的地方。給定 $Q$ 筆詢問，請每次回答當坐了 $e_i$ 時間的摩天輪後與「高橋直大像」的仰角夾角為多少？ 高中基礎三角函數代一代移一移就好了，不知道題解怎麼寫XD #include <bits/stdc++.h> using namespace std; using llf = long double; static constexpr llf PI = acos(-1); int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.precision(15); int T, L, X, Y, Q; cin >> T >> L >> X >> Y >> Q; while (Q--) { int e; cin >> e; llf ang = static_cast<llf>(e) / T * 2 * PI + PI; llf y = L * sin(ang) / 2, z = L * (cos(ang) + 1) / 2 ; llf dx = X, dy = Y - y, dz = -z; llf dd = hypot(dx, dy, dz); llf theta = acos(dz / dd); cout << theta / PI * 180 - 90 << '\n'; }

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_q 題目大意: 給定一個圓，在圓周上有 $N$ 個點，每個點距離相同，接著我們畫 $M$ 條線段，分別從第 $L_i$ 個點連到第 $R_i$ 個點。問有多少組有交的線段 (這裡有交限定交在非端點上)。 想一下後可以發現兩個線段 $i$, $j$ 有交必定有一個 $j$ 的端點在 $L_i$ 與 $R_i$ 之間，另一個在外面。所以我們可以考慮對於每個線段，在 $L_j$ 的地方紀錄 $R_j$ ，並在 $R_j$ 的地方紀錄 $L_j$ ，這樣我們就可以透過查詢 $L_i$ 與 $R_i$ 之間有多少數字小於 $L_i$ 或大於 $R_i$ 就可以知道有多少線段跟第 $i$ 條線段交了。 #include <bits/stdc++.h> using namespace std; const int N = 300000 + 5; class SegTree { private: int n; vector<vector<int>> a; function<int(int, int)> policy; inline int lc(int x) { return 2 * x + 1; } inline int rc(int x) { return 2 * x + 2; } void build(int l, int r, int id, const vector<vector<int>> &v) { if (r - l == 1) { a[id] = v[l]; sort(a[id].begin(), a[id].end()); return; } int m = (l + r) >> 1; build(l, m, lc(id), v); build(m, r, rc(id), v); merge(a[lc(id)].begin(), a[lc(id)].end(), a[rc(id)].begin(), a[rc(id)].end(), back_inserter(a[id])); }

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_p 題目大意: 有三種幣值的硬幣 $A$, $B$, $C$ ，問要湊出 $N$ 元的話最少要多少硬幣，保證答案使用的總硬幣數不超過 $9999$ 因為不超過 $9999$ ，所以直接枚舉 $A$ 用多少跟 $B$ 用多少就自然知道 $C$ 要用多少了。 #include <bits/stdc++.h> using namespace std; using lld = int64_t; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); lld n, a, b, c; cin >> n >> a >> b >> c; lld ans = n; for (lld i = 0; i <= 9999; ++i) { for (lld j = 0; j <= 9999; ++j) { if (a * i + b * j > n) break; lld lef = n - a * i - b * j; if (lef % c != 0) continue; ans = min(ans, i + j + lef / c); } } cout << ans << '\n'; return 0; }

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_o 題目大意: 給定 $N$，對於每個 $k$ ($1 \leq k \leq N$)，回答從 $1$ 到 $N$ 中挑任意數量的數字 ($>0$)，使得挑出來的數字任意兩者絕對值差都至少 $k$ 的方法數有幾種。 我超爛不會做這個= = 腦袋中一直只有 $f_k(i) = f_k(i - 1) + f_k(i - k) + 1$ 的遞迴式，嘗試搞了搞也優化不下去。 解答的想法不太一樣，但也是高中基礎組合的範圍。 對於每個 $k$ ，我們每次都枚舉這次要拿多少個數字出來，因為假設 $k$ 很大的話，其實我們能拿的數字數量也有限 (實際上大概會是 $O(\frac{N}{k})$ 左右)，所以如果我們能 $O(1)$ 算給定 $k$ 且知道具體要拿幾個的時候的方法數的話，那我們就可以在 $\sum_k O(\frac{N}{k}) = O(N \log N)$ 做完這題。 給定 $k$ 且知道具體要拿幾個的時候要算方法數也很簡單，先保證每個挑出來的數字之間都至少有 $k$ 後，再把剩下的數字插回去就好，插回去的方法數其實也就是某種 H 之類的。 #include <bits/stdc++.h> using namespace std; constexpr int N = 100000 + 5; constexpr int MOD = 1000000007; constexpr int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; } constexpr int mul(int64_t a, int64_t b) { return static_cast<int>(a * b % MOD); } constexpr int qpow(int a, int k) { int r = 1; while (k) { if (k & 1) r = mul(r, a); a = mul(a, a); k >>= 1; } return r; } struct Fact { int t

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_n 題目大意: 有 $N$ 個國小生要去上小學，並且剛好也有 $N$ 個小學。一個住在 $A_i$ 的國小生要去 $B_j$ 的國小的不方便度為 $|A_i - B_j|$ ，現在你要安排每個國小生要去的學校，使得所有國小生的總不方便度最低。注意在這題每個國小生都要去不同的小學。 對兩個數列排序對項絕對值差和就是答案，不過其實我好像不會證 @_@ #include <bits/stdc++.h> using namespace std; using lld = int64_t; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<lld> a(n), b(n); for (lld &ai: a) cin >> ai; for (lld &bi: b) cin >> bi; sort(a.begin(), a.end()); sort(b.begin(), b.end()); lld ans = 0; for (int i = 0; i < n; ++i) ans += abs(a[i] - b[i]); cout << ans << '\n'; return 0; }

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_m 題目大意: 給一個 $N$ 個點 $M$ 條邊的圖，對於所有點 $u$ 求問強迫經過點 $u$ 時 $1$ 走到 $n$ 的最短路是多長。 從 $1$ 跟 $N$ 分別做一次 Dijkstra 就好了。 #include <bits/stdc++.h> using namespace std; using lld = int64_t; const lld INF = static_cast<lld>(1) << 60; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<pair<int, lld>>> g(n); for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; g[--u].emplace_back(--v, w); g[v].emplace_back(u, w); } auto shortest_path = [&g] (int s, vector<lld> &d) { vector<bool> vis(d.size()); fill(d.begin(), d.end(), INF); priority_queue<pair<lld,int>> pq; d[s] = 0; pq.emplace(-d[s], s); while (not pq.empty()) { int u = pq.top().second; pq.pop(); if (vis[u]) continue; vis[u] = true; for (auto [v, w]: g[u]) { if (d[u] + w < d[v]) {

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_l 題目大意: 給定一個 $N \times M$ 的網格上，現在有兩種可能的操作，其中一種 1 x y 代表把 ($x$, $y$) 塗成紅色的；另外一種 2 p q r s 代表詢問 ($p$, $q$) 可否只透過紅色的格子上下左右移動到 ($r$, $s$)。 詢問的時候等價問兩個點是不是在同個連通塊裡，所以弄個併查集每次塗色的時候都更新一下當前的連通資訊就好了。 #include <bits/stdc++.h> using namespace std; const int N = 2000 + 5; class DSU { private: vector<int> p; public: void init(int n) { p.resize(n); iota(p.begin(), p.end(), 0); } int query(int x) { if (p[x] != x) p[x] = query(p[x]); return p[x]; } void merge(int x, int y) { p[query(x)] = query(y); } } dsu; int dx[] = {0, 0, -1, 1}; int dy[] = {1, -1, 0, 0}; bool a[N][N]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; dsu.init(n * m); auto Idx = [&m](int i, int j){ return i * m + j; }; int q; cin >> q; while (q--) { int op; cin >> op; if (op == 1) { int x, y; cin >> x >> y; a[--x][--y] = true; for (int

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_k 題目大意: 現在有 $N$ 個工作可以做，第 $i$ 個工作要在 $D_i$ 前做完，並且要花費 $C_i$ 天，如果有做完的話可以獲得 $S_i$ 元的報酬。一天只能做一個工作，且一個工作做了就不能中途換其他工作。問最多可以得到多少報酬。 假設最佳解是做了 $p_1$, $p_2$, $\cdots$, $p_m$ 這些工作，那我們按照死線先後順序來做這些工作並不會讓我們少做甚麼工作。這代表我們可以按照死線先後順序來挑工作做。考慮直接暴力 DP 要挑哪些工作，這裡 $\text{dp}_{i,j}$ 代表只做前 $i$ 個工作 (排好序後的前 $i$ 個) 的話，那第 $j$ 天時可以獲得多少報酬，轉移的話就直接在每個時間點都安排看看工作就好了。 #include <bits/stdc++.h> using namespace std; using lld = int64_t; constexpr int N = 5000 + 5; struct Task { int d, c; lld s; }; lld dp[2][N]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<Task> a(n); for (auto &a_i : a) { cin >> a_i.d >> a_i.c >> a_i.s; } sort(a.begin(), a.end(), [](const auto &x, const auto &y){ return x.d < y.d; }); int me = 0, he = 1; for (int i = 0; i < n; ++i) { auto &task = a[i]; for (int j = 1; j < N; ++j) dp[me][j] = dp[he][j]; for (int j =

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_j 題目大意: ABC大學有 $N$ 個學生，學號 $i$ 的學生在 $C_i$ 班裡，已知第 $i$ 個學生期末考成績為 $P_i$ 。現在對於 $Q$ 筆詢問 $L_i$, $R_i$，請輸出學號在 $[L_i, R_i]$的學生的成績總和 (分班獨自統計) 算個前綴和就可以 $O(1)$ 回答了。 #include <bits/stdc++.h> using namespace std; using lld = int64_t; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<lld> a(n), b(n); for (int i = 0; i < n; ++i) { int op, scr; cin >> op >> scr; if (op == 1) { a[i] = scr; } else { b[i] = scr; } } partial_sum(a.begin(), a.end(), a.begin()); partial_sum(b.begin(), b.end(), b.begin()); int q; cin >> q; while (q--) { int l, r; cin >> l >> r; --l, --r; if (l) cout << a[r] - a[l - 1] << ' ' << b[r] - b[l - 1] << '\n'; else cout << a[r] << ' ' << b[r] << '\n'; } return 0; }

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_i 題目大意: 給定 $N$ 個二維點，請求出一組點 $i$, $j$, $k$ 使得其夾角越大越好，這裡夾角一定是 < 180 的那個角。 以每個點為中心做極角排序，然後雙指針找出在符合條件下的最大的夾角。 #include <bits/stdc++.h> using namespace std; using llf = long double; constexpr llf PI = acos(-1); int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<pair<int,int>> ps(n); for (auto &[x, y]: ps) cin >> x >> y; llf ans = 0; for (auto [x, y]: ps) { vector<llf> ang; for (auto [px, py]: ps) { if (px != x or py != y) { auto d = atan2(py - y, px - x); ang.push_back(d); ang.push_back(d + 2 * PI); } } sort(ang.begin(), ang.end()); size_t j = 1; for (size_t i = 0; i + 1 < ang.size();++i) { j = max(j, i + 1); while (j + 1 < ang.size()) { if (ang[j + 1] - ang[i] > PI) { break; } ++j; } if (ang[j] - ang[i] <= PI) { ans = max(ans, ang[j] - ang[i]); } } } c

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_h 題目大意: 給定一個字串 $S$ ，問其中有多少子字串 "atcoder"。 由左往右暴力掃一遍維護一下當下有多少 a, at, atc, atco, atcod, atcode, atcoder 就好ㄌ #include <bits/stdc++.h> using namespace std; const int MOD = 1'000'000'007; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; string s; cin >> s; int ca = 0, cat = 0, catc = 0, catco = 0, catcod = 0, catcode = 0, catcoder = 0; for (auto c: s) { switch (c) { case 'a': ca++; break; case 't': cat+=ca; cat%=MOD; break; case 'c': catc+=cat; catc%=MOD; break; case 'o': catco+=catc; catco%=MOD; break; case 'd': catcod+=catco; catcod%=MOD; break; case 'e': catcode+=catcod; catcode%=MOD; break; case 'r': catcoder+=catcode; catcoder%=MOD; break; } } cout << catcoder << '\n&#

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_g 題目大意: 給定$N$個數字 $A_i$ ，對於 $Q$ 比詢問的每個 $B_i$，請找到 $\min_j |A_j - B_i|$ 。 直接拿個平衡樹 (例如 C++ STL 內建的 std::set) 查一下就做完ㄌ。 #include <bits/stdc++.h> using namespace std; constexpr int INF = 1 << 30; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; set<int> s; for (int i = 0; i < n; ++i) { int x; cin >> x; s.insert(x); } int q; cin >> q; while (q--) { int x; cin >> x; auto it = s.lower_bound(x); int ans = INF; if (it != s.end()) ans = min(ans, *it - x); if (it != s.begin()) ans = min(ans, x - *prev(it)); cout << ans << '\n'; } return 0; }

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_f 題目大意: 給一個長度為 $N$ 的字串，請找出一個長度為 $K$ 的子序列 (不必連續)，使得其字典序最小。 因為字典序的性質，我們可以 greedy 的從頭往後把要挑的子序列找出來，每次就挑當前字典序最小且取它後其後面還有足夠數量的字元可取的字元出來就好。 #include <bits/stdc++.h> using namespace std; queue<int> qs[26]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; string s; cin >> s; for (int i = 0; i < n; ++i) { qs[s[i] - 'a'].push(i); } string ans; int pos = 0; for (int i = 0; i < k; ++i) { for (int c = 0; c < 26; ++c) { while (not qs[c].empty()) { if (qs[c].front() >= pos) { break; } qs[c].pop(); } if (qs[c].empty()) continue; if (n - qs[c].front() >= k - i) { ans += 'a' + c; pos = qs[c].front(); qs[c].pop(); break; } } } cout << ans << '\n'; return 0; }

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_e 題目大意: 給定 $c_i$ 代表可以用的數字種類，問在只用 $c_i$ 的情況下有多少 $N$ 位數是 $B$ 的倍數。 原本想暴力數位統計 DP 下去 ，但發現 $N$ 太大不能做，想了很久之後最後跑去看解答，我就爛= = 解答感覺也是一個很套路的東西，因為我們只要求 $N$ 位數而不是特定少於某個 $K$ 的數字，所以其實可以直接對 $N$ 倍增。初始狀態給的是 $1$ 位數的情況，那我們就可以倍增出 $2$ 位數的情況、$4$ 位數的情況、 $8$ 位數的情況...，對於 $N$ 位數，我們考慮它的二進位寫法，假設它是 $2^0 + 2^4 + 2^5$ 那我們就挑 $2^0$ 位數的情況、 $2^4$ 位數的情況、 $2^5$ 位數的情況來合併就好。 具體合併就是背包合併直接暴力枚舉高位跟低位分別模 $B$ 餘多少就好。 #include <bits/stdc++.h> using namespace std; using lld = int64_t; using llu = uint64_t; constexpr int M = 3000 + 5; constexpr int N = 64; constexpr int MOD = 1'000'000'007; static inline int add(int x, int y, int mod = MOD) { return x + y >= mod ? x + y - mod : x + y; } static inline void adde(int &x, int y, int mod = MOD) { x += y; if (x >= mod) x -= mod; } static inline int mul(int64_t x, int64_t y, int mod = MOD) { return static_cast<int>(x * y % mod); } int dp[N][M]; int ans[M], tmp[M]; int main() { ios_bas

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_d 題目大意: 給一個二維陣列 $A$ ，請建構另一個二維陣列 $B$ ，使得 $B_{ij}$ 為所有跟 $A_{ij}$ 同行或同列的和 ($A_{ij}$ 自己也算)。 直接照著定義做，然後記得一行的值或一列的值不用每次都重算就好。A #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<int>> a(n, vector<int>(m)); for (auto &a_i : a) { for (auto &a_ij : a_i) { cin >> a_ij; } } vector<vector<int>> b(n, vector<int>(m)); for (int i = 0; i < n; ++i) { int sm = accumulate(a[i].begin(), a[i].end(), 0); for (int j = 0; j < m; ++j) b[i][j] = sm - a[i][j]; } for (int j = 0; j < m; ++j) { int sm = 0; for (int i = 0; i < n; ++i) sm += a[i][j]; for (int i = 0; i < n; ++i) b[i][j] += sm; } for (auto &b_i : b) { for (int j = 0; j < m; ++j) { cout << b_i[j] << " \n"[j == m - 1]; } } return 0;

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_c 題目大意: 給你一棵樹，詢問在樹上加入一條邊後最長的環可以是多長。 樹直徑就會是這題答案了。 #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<vector<int>> g(n); for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; g[--u].emplace_back(--v); g[v].emplace_back(u); } int ans = 0; auto dfs = [&g, &ans] (auto rec, int u, int f) -> int { int mx1 = 0, mx2 = 0; for (int v: g[u]) { if (v == f) continue; int s = rec(rec, v, u); if (s >= mx1) { mx2 = mx1; mx1 = s; } else if (s >= mx2) { mx2 = s; } } ans = max(ans, mx1 + mx2); return mx1 + 1; }; dfs(dfs, 0, 0); cout << ans + 1 << '\n'; return 0; }

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_b 題目大意: 給你一個 $N$ ，請輸出所有長度為 $N$ 且合法括號序列。 這題其實跟 LeetCode 22 一模一樣，不過我真的做不太出來，上次面試被問還真的寫錯東西... 總之，這裡的做法是因為我們知道把「(」當作 $+1$、「)」當作 $-1$ 的話，一個括號序列合法，若且唯若前綴和恆非負且總和為 $0$。於是我們就可以暴力遞迴下去，每次都加加看右括號或左括號，並檢查當前的和是不是少於 $0$ 了，最後長度滿足後就把構造的序列加入 set 裡即可。 #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; if (n & 1) return 0; set<string> ans; auto generate = [&ans](auto rec, int lef, int rig, string s) -> void { if (rig < lef or lef < 0 or rig < 0) return; if (lef == 0 and rig == 0) { ans.insert(s); return; } rec(rec, lef - 1, rig, s + "("); rec(rec, lef, rig - 1, s + ")"); }; generate(generate, n/2, n/2, ""); for (auto s: ans) cout << s << '\n'; return 0; }

最近一直覺得自己該復健一下。剛好看到這系列，決定來寫一下回復一下手感，順便練練日文，不然真的太久太久沒自己好好做題了，什麼都忘光光了 😥 題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_a 題目大意: 有一個 $L$ 公分的羊羹，其中有 $N$ 個可以切的地方，從左數來第 $i$ 個可以切的位置在 $A_i$ 公分。你要選擇切 $K$ 刀使得產生 $K+1$ 塊的羊羹出來。定義切完後的羊羹的分數為： 切出來的 $K+1$ 塊中長度最小塊的長度。我們想要最大化切出來的分數。答案請輸出最大可能的分數。 挺經典的二分搜題，跟 骨牌遊戲 那種題目有點類似，可以直接對答案二分搜。假設我們知道分數是 $x$ ，那就代表只要當前位置與上一刀距離超過 $x$ 就可以砍一刀下去，而如果砍了 $K$ 刀的話就可以停下來，且代表這個分數是達的到的。根據這件事情我們就可以二分搜出最大的分數 $x$ 使得還可以砍得出 $K$ 刀。 惹..講得有點模糊，但 code 短短的可能可以看一下它 (?) #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, d, k; cin >> n >> d >> k; vector<int> a(n); for (int &a_i : a) cin >> a_i; auto valid = [&] (int m) { int piv = 0, tot = 0; for (int a_i: a) { if (a_i - piv >= m and d - a_i >= m) { tot++; piv = a_i; } } return tot >= k; }; int l = 0, r = 1'000'000'001; while (r - l > 1) { int m = (l + r