oToToT的code收藏區

題目連結: 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...

題目連結: 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 ); ...

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_t 題目大意: 問你 $\log_2 a 看了官解才發現不會爆 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 ...

題目連結: 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 ...

題目連結: 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...