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; }