joylintp / WiwiHo
直播循環 (Cycle)
來源: Codeforces 1041C
測資: joylintp
題敘: joylintp
\(r=0\)
→ 不用休息
→ 所有遊戲都可以在第一個循環直播
→ \(k=1,x_i=1\)
3 / 100
\(n \le 10\)
→ 枚舉直播遊戲的順序
→ 盡量讓遊戲可以在同一個循環內直播
→ \(O(n! \times n)\)
9 / 100
\(n = s\)
→ 每天都有一種遊戲要玩
→ 第一個循環玩第 \(1,1+r+1,1+2r+2,\dots\) 天的遊戲
→ 第二個循環玩第 \(2,2+r+1,2+2r+2,\dots\) 天的遊戲
→ \(O(n)\)
13 / 100
每次盡量選擇還沒玩過的遊戲中 \(a_i\) 最小的
→ \(O(n)\) 迴圈尋找可玩的遊戲
→ 總複雜度 \(O(n^2)\)
18 / 100
→ \(O(n)\) 迴圈尋找可玩的遊戲
→ set、priority_queue \(O(\log{n})\) 維護
→ 總複雜度 \(O(n\log{n})\)
100 / 100
#include<bits/stdc++.h> using namespace std; #define MP make_pair #define F first #define S second signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m, d; cin >> n >> m >> d; vector<pair<int, int>> a(n); for (int i = 0; i < n; i++) cin >> a[i].F, a[i].S = i; sort(a.begin(), a.end()); vector<int> ans(n); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; for (int i = 0; i < n; i++) if (pq.empty() || a[i].F - pq.top().F < d + 1) ans[a[i].S] = pq.size() + 1, pq.push(MP(a[i].F, pq.size() + 1)); else ans[a[i].S] = pq.top().S, pq.pop(), pq.push(MP(a[i].F, ans[a[i].S])); cout << pq.size() << '\n'; for (int i : ans) cout << i << ' '; return 0; }
兔田彩券 (Lottery)
靈感來源: JOI 2021 Final Round pC
測資: WiwiHo
題敘: joylintp
有 \(m\) 個 pair \((a_i,b_i)\)
對於每筆詢問 \((l_i,r_i,s_i,t_i)\)
求有幾個 \(j\) 滿足
\(l_i \leq a_j \leq r_i \land s_i \leq b_j \leq t_i\) 或
\(l_i \leq b_j \leq r_i \land s_i \leq a_j \leq t_i\)
\(n,m,q \leq 500\)
對於每一個詢問
把所有 pair 檢查一次是否符合條件就好了
\(O(mq)\)
\(n \leq 100\)，\(q \leq 10000\)
\(n\) 很小？
pair 只有 \(O(n^2)\) 種而已
數每一種 pair 出現了幾次
詢問的時候，找符合條件的 pair
\(O(m + n^2q)\)
\(l_i \leq r_i < s_i \leq t_i\)
如果把每一種 pair 出現的數量存在一個表格上
那詢問其實是在問一個矩形區域的和
假設 \((i,j)\) 出現 \(c[i][j]\) 次
二維前綴和：\(sum[i][j]= \sum_{i'=1}^i \sum_{j'=1}^j c[i'][j']\)
\(\sum_{i=l}^{r} \sum_{j=s}^t c[i][j] = sum[r][t] \\ - sum[l-1][t] - sum[r][s-1] + sum[l-1][s-1]\)
預處理 \(sum\)，詢問只要 \(O(1)\) 的時間
\(O(m + n^2 + q)\)
為什麼上一個 subtask 的 code 不能過這個？
因為會算到重複的
如果 \(l_i \leq a_j \leq r_i \land s_i \leq b_j \leq t_i\)
和 \(l_i \leq b_j \leq r_i \land s_i \leq a_j \leq t_i\)
同時滿足，\(j\) 就會被算到兩次
誰會被算到兩次？
\(\max(l_i,s_i) \leq a_j,b_j \leq \min(r_i,t_i)\)
\(j\) 就會被算到兩次
把這個區域扣掉就好
#include <bits/stdc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); using namespace std; int main(){ StarBurstStream int n, m; cin >> n >> m; vector<vector<int>> a(n + 1, vector<int>(n + 1)); for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; if(u > v) swap(u, v); a[u][v]++; a[v][u]++; } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++) a[i][j] += a[i][j - 1]; } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++) a[j][i] += a[j - 1][i]; } auto calc = [a](int x1, int y1, int x2, int y2){ return a[x2][y2] - a[x2][y1 - 1] - a[x1 - 1][y2] + a[x1 - 1][y1 - 1]; }; int q; cin >> q; while(q--){ int l, r, s, t; cin >> l >> r >> s >> t; int tl = max(l, s); int tr = min(r, t); int ans = calc(l, s, r, t); if(tl <= tr) ans -= calc(tl, tl, tr, tr) / 2; cout << ans << "\n"; } return 0; }
魔法師測驗 (Mage)
來源: CF 1101D
測資: joylintp
題敘: joylintp
\(m_1=m_2=\ldots=m_n\)
→ 若 \(m_1=1\) 則答案為 \(0\)（和諧度必為 \(1\)）
→ 若 \(m_1 \ne 1\) 則答案為樹直徑（和諧度必不為 \(1\)）
8 / 100
\(n \le 1000\)
→ 枚舉起點
→ \(O(n)\) DFS 看能走多遠
→ 總複雜度 \(O(n^2)\)
(6 + 14) / 100
和諧度不為 \(1\)
→ 最大公因數大於 \(1\)
→ 所有數字至少有一個共同質因數
\(m_i \le 100\)
→ 枚舉質數（至多 \(25\) 個）
→ 對每個質數建出子圖
→ 找所有子圖中最長的樹直徑
→ 總複雜度 \(O(n \times 25)\)
16 / 100
\(m_i \le 2 \times 10^5\)
→ 質數有 \(17984\) 個
→ 對每個質數建出子圖
→ TLE
\(m_i \le 2 \times 10^5\)
→ \(2 \times 3 \times 5 \times 7 \times 11 \times 17 > 2 \times 10^5\)
→ 每個節點的相異質因數不會超過 \(5\) 個
→ 樹 DP
記錄
轉移
總複雜度 \(O(n\log^2{m})\)
100 / 100
#include<bits/stdc++.h> using namespace std; #define F first #define S second int ans; vector<bool> pfac(200001, true), vis; vector<int> prime, a; vector<vector<int>> edge; map<int, int> dfs(int u) { vis[u] = true; map<int, int> sa; for (int i : prime) { if (i * i > a[u]) break; while (a[u] % i == 0) sa[i] = 1, a[u] /= i; } if (a[u] != 1) sa[a[u]] = 1; map<int, pair<int, int>> sb; for (int i : edge[u]) if (!vis[i]) { map<int, int> mp = dfs(i); for (auto p : mp) if (sa.count(p.F)) { sa[p.F] = max(sa[p.F], p.S + 1); if (p.S > sb[p.F].F) sb[p.F].S = sb[p.F].F, sb[p.F].F = p.S; else if (p.S > sb[p.F].S) sb[p.F].S = p.S; else; } } for (auto p : sa) ans = max(ans, p.S); for (auto p : sb) ans = max(ans, p.S.F + p.S.S + 1); return sa; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); for (int i = 2; i <= 200000; i++) { if (pfac[i]) prime.push_back(i); for (int j : prime) { if (i * j > 200000) break; pfac[i * j] = false; if (i % j == 0) break; } } int n; cin >> n, vis.resize(n + 1), a.resize(n + 1), edge.resize(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; int u, v; for (int i = 1; i < n; i++) cin >> u >> v, edge[u].push_back(v), edge[v].push_back(u); dfs(1); cout << ans << '\n'; return 0; }
刷怪塔 (Monster)
來源: Google Code Jam 2020 Round 2 pA
測資: joylintp
題敘: joylintp
\(a,b \le 1000\)
→ 選擇刷怪塔的次數至多 \(\sqrt{a+b}\) 次
→ 模擬每次選擇刷怪塔
→ 總時間複雜度 \(O(T\sqrt{a+b})\)
12 / 100
\(a=0\)
→ 只會打第二座刷怪塔的怪物
→ \(b \ge \frac{l(l+1)}{2}\)
→ 解不等式或二分搜最大值
→ 總時間複雜度 \(O(T)\) 或 \(O(T\log{b})\)
8 / 100
\(a=b\)
→ 觀察到在怪物數量足夠的情況下，
奇數一定選擇第一座刷怪塔，偶數一定選擇第二座
→ \(a \ge 1+3+\ldots+(2k+1) = (k+1)^2\)
\(b \ge 2+4+\dots+(2k) = (k+1)^2 + k + 1\)
→ 解不等式或二分搜最大值
→ 總時間複雜度 \(O(T)\) 或 \(O(T\log{b})\)
21 / 100
將較多的那座擊殺到怪物數量不超過另一座
接下來兩座刷怪塔必定會輪流使用
→ 作法類似 Subtask 2
→ 總時間複雜度 \(O(T)\) 或 \(O(T\log{b})\)
100 / 100
#include<bits/stdc++.h> using namespace std; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int T; cin >> T; for (int i = 1; i <= T; i++) { long long A, B; cin >> A >> B; bool swp = (A <= B); if (A < B) swap(A, B); long long l = 0, r = 2e9; while (l != r) { long long m = (l + r) / 2; if (m * (m + 1) / 2 > A - B) r = m; else l = m + 1; } A -= l * (l - 1) / 2; if (A > B || (A == B && !swp)) swap(A, B), swp = !swp; long long x = l - 1; if (B < x + 1) { if (swp) swap(A, B); cout << x << ' ' << A << ' ' << B << '\n'; } else if (A < x + 2) { B -= x + 1; if (swp) swap(A, B); cout << x + 1 << ' ' << A << ' ' << B << '\n'; } else { l = x + 2, r = 2e9; long long Aa = A, Ba = B; while (l != r) { long long m = (l + r) / 2; long long Al = m, Bl = m; if (Al % 2 == x % 2) Bl--; else Al--; long long At = (Al + x + 2) * (Al - x) / 4, Bt = (Bl + x + 1) * (Bl - x + 1) / 4; if (A < At || B < Bt) r = m; else l = m + 1, Aa = A - At, Ba = B - Bt; } if (swp) swap(Aa, Ba); cout << l - 1 << ' ' << Aa << ' ' << Ba << '\n'; } } return 0; }
時空旅人之爭 (Time)
來源: 原創
測資: WiwiHo
題敘: joylintp
給一棵樹，複製人大軍會從節點 1 開始擴散，每 2 秒擴散一個節點
有 \(Q\) 筆詢問，詢問求從入侵的時間點開始，從 \(s_i\) 走到 \(t_i\) 的路上
至少要經過幾個有複製人大軍的節點
顯然就是走得越快越好，所以直接走 \(s_i\) 到 \(t_i\) 的簡單路徑
Kronii 到達 \(v\) 的時間：\(dis(s_i, v)\)
複製人大軍到達 \(v\) 的時間： \(2 \times dis(1, v)\)
答案要求有幾個 \(v\) 滿足 \(dis(s_i,v) \geq 2 \times dis(i,v)\)
\(n,q \leq 1000\)
暴力檢查
\(O(nq)\)
\(\forall 1 \leq i < n, v_i = u_{i+1}\)
就是這個樹是一條鏈的意思
如果 \(s_i,t_i\) 都在 \(1\) 的同一側
那麼靠近 \(1\) 的那邊可能會有一段連續的符合條件的節點
也就是這條鏈上會有一邊符合條件、一邊不符合
二分搜找交界點
如果 \(s_i,t_i\) 在 \(1\) 的兩側
那麼符合條件的節點會是中間連續的一段
如果把 \(1\) 左右分開看
就和上一種狀況一樣了
\(O(n + q \log n)\)
除了節點 1 以外，每個節點度數最多 2
也就是說這個樹是從 1 往外伸的一堆鏈
只看 \(s_i\) 和 \(t_i\) 所在的鏈
就跟 Subtask 2 一樣了
Subtask 2,3 都是「把 \(s_i\) 到 \(t_i\) 的路徑，以最靠近 \(1\) 的節點為中心把這條路徑切成兩半」，而切出來的兩條路徑上，都是有一邊的點符合條件（靠近中心的那邊）、一邊不符合
\(s_i\) 到 \(t_i\) 的路徑上離 \(1\) 最近的點就是他們的 LCA
（以 \(1\) 為根）
然後就跟前面一樣了
可以用倍增法二分搜
#include <bits/stdc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define eb(a) emplace_back(a) using namespace std; vector<vector<int>> g; vector<int> in, out, dpt; int ts = 0; vector<vector<int>> anc; void dfs(int now, int p, int d){ in[now] = ts++; dpt[now] = d; anc[0][now] = p; for(int i : g[now]){ if(i == p) continue; dfs(i, now, d + 1); } out[now] = ts++; } bool isAnc(int a, int b){ return in[a] <= in[b] && out[a] >= out[b]; } int getLCA(int a, int b){ if(isAnc(a, b)) return a; if(isAnc(b, a)) return b; for(int i = 19; i >= 0; i--){ if(!isAnc(anc[i][a], b)) a = anc[i][a]; } return anc[0][a]; } int getDis(int a, int b){ int lca = getLCA(a, b); return dpt[a] + dpt[b] - 2 * dpt[lca]; } bool check(int s, int now){ return getDis(s, now) < dpt[now] * 2; } void solve(){ int s, t; cin >> s >> t; int lca = getLCA(s, t); if(check(s, lca)){ cout << "0\n"; return; } int ans = 0; int now = s; for(int i = 19; i >= 0; i--){ if(check(s, anc[i][now])) now = anc[i][now]; } ans += dpt[now] - dpt[lca] + !check(s, s); now = t; for(int i = 19; i >= 0; i--){ if(check(s, anc[i][now])) now = anc[i][now]; } ans += dpt[now] - dpt[lca] + !check(s, t); ans--; cout << ans << "\n"; } int main(){ StarBurstStream int n; cin >> n; g.resize(n + 1); in.resize(n + 1); out.resize(n + 1); dpt.resize(n + 1); anc.resize(20, vector<int>(n + 1)); for(int i = 0; i < n - 1; i++){ int u, v; cin >> u >> v; g[u].eb(v); g[v].eb(u); } int q; cin >> q; dfs(1, 1, 0); for(int i = 1; i < 20; i++){ for(int j = 1; j <= n; j++){ anc[i][j] = anc[i - 1][anc[i - 1][j]]; } } for(int i = 0; i < q; i++){ solve(); } return 0; }