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")