# 2022 建中校內賽複賽題解 --- ## pA 買項鍊 Setter: 8e7 ---- 定位：前面子題很好拿的梗題(?) 但是沒人想寫 qwq ---- 拆包裝：給一張 $n$ 點 $m$ 邊的無向圖，每條邊有權重 $w_i$，一個好的邊集可以被分成若干個歐拉環，權重是每條邊的 $w_i$ 乘起來，問所有好的邊集的權重總和。 以下都用 $n$ 點跟 $m$ 邊來說明本題 ($k$ 跟 $n$ 是為了讓他看起來比較不像圖論www) ---- ### Subtask 1: $m \leq 20$ 直接枚舉邊集，判斷是不是好的 ---- 如何判斷一個好的邊集？ * 一個歐拉環的每個點度數都是偶數 - 所有點度數都是偶數就能把邊拆成一些歐拉環 ---- ### Subtask 2: $n \leq 19$ ---- 每個點度數都是偶數的限制？ 對於一個邊集，我們需要的資訊是每個點度數的**奇偶性**。 ---- 位元 DP! $dp[c][S]$ 代表考慮了前 $c$ 條邊，每個點度數的奇偶性是 $S$ 的權重和。 轉移：把兩個點的位元flip。 初始狀態：$dp[0][0]$ = 1，最後答案會是 $dp[m][0] - 1$ 複雜度 $O(2^nm)$ ---- ### Subtask 3: $n \leq 23$ ---- 觀察前面的 DP ，可以發現到加邊的順序不會影響答案。而且每次轉移時只會改兩個位置。 那麼如果我已經加完了 $1$ 號點連接的所有邊，最後點度還是奇數的話，他就不可能對答案有貢獻！ ---- 先把點 $1$ 相鄰的邊加完，再加點 $2$, 點 $3$ ... 相鄰的邊。 每次把前面不重要的狀態忽略掉，狀態數會少一半！ 時間是 $2^nn + 2^{n-1}(n-1) + \cdots \leq 2^nn(1 + \frac{1}{2} + \frac{1}{4} + \cdots) = O(2^nn)$ ---- 毒瘤另解 (by wiwiho) 把點分成 19+4個，先把兩邊算完之後對中間的邊 DP。 不知道會不會過，預期解都要跑 1~1.5秒了 ---- AC code ```cpp= vector<pii> adj[maxn]; ll f[1<<maxn], g[1<<maxn]; int main() { io int n, m; cin >> n >> m; for (int i = 0;i < m;i++) { int u, v, w; cin >> u >> v >> w; u--, v--; if (v < u) swap(u, v); adj[u].push_back({v, w}); } f[0] = g[0] = 1; for (int a = 0;a < n;a++) { for (auto [b, w]:adj[a]){ int u = n - 1 - a, v = n - 1 - b; for (int i = 0;i < (1<<(n-a));i++) { g[i] = (g[i] + f[i ^ (1<<u) ^ (1<<v)] * w) % mod; } for (int i = 0;i < (1<<(n-a));i++) f[i] = g[i]; } } cout << (f[0] + mod - 1)%mod << "\n"; } ``` --- ## pB 調分 Setter: 8e7 ---- 定位：有包裝的簡單題？ ---- ### Subtask 1: $m = 1$ ---- 沒有包含所有人的話那就是無限大 有的話就是$w_i$ ---- ### Subtask 2: $m = n - 1, k_i = 2$ ---- 圖論觀點：把兩個人的分數限制看成圖上的邊 如果不連通就是 $-1$。連通的話那一定是一棵樹！ ---- 把 $1$ 號點當作是根，那跟我連到的人分數都能差到最大可能值（邊權），所以直接在樹上 dfs 找距離最大值。 ---- ### Subtask 3: $k_i = 2$ ---- 延續剛剛的想法，這會變成一張無向帶權圖。 如果我把每個人的分數叫做 $d_v$，那麼一條邊$(u, v, w)$的限制代表 $d_u \leq d_v + w, d_v \leq d_u + w$ 這不就是最短路嗎?!?! ---- 差分約束：可以用最短路問題對一些變數的大小關係求解。 答案會是從點 $1$ 開始跑 Dijkstra 之後距離最遠者。為什麼？ ---- ### Subtask 4: 無其他限制 ---- 現在問題變成：有一張無向圖，一開始是空的，接著有 $m$ 次加邊操作，每次選一個集合的點並讓他們兩兩之間連上權重為 $w_i$ 的邊，求單點源最短路。 ---- 解一：建圖 對一個集合的點 $v_1, v_2, \cdots, v_k$ 兩兩之間連邊等價於把 $v_1, v_2, \cdots, v_k$ 跟一個新的點 $x$ 連權重為 $\frac{w}{2}$的邊（或是連有向邊也可以）。總共的邊數是 $O(\sum k_i)$ ---- 解二：直接做? 對於每一點紀錄他在哪些群組裡，並且紀錄一個群組有沒有被「走過」，在Dijkstra 看一個新的點的時候，枚舉他在的群組，並且對沒有走過的群組鬆弛，並且將他們標記成有走過。 其實跟解一是一樣的意思，但常數比較小xd。 ---- AC code ```cpp= const ll inf = 1LL<<60; bool done[maxn]; vector<pii> adj[maxn]; vector<int> vert[maxn], col[maxn]; ll dis[maxn], wei[maxn]; int main() { io int n, m; cin >> n >> m; for (int i = 0;i < m;i++) { int ki, w; cin >> ki >> w; wei[i] = w; for (int j = 0;j < ki;j++) { int x; cin >> x; vert[i].push_back(x); col[x].push_back(i); } } for (int i = 1;i <= n;i++) dis[i] = inf; dis[1] = 0; priority_queue<pii, vector<pii>, greater<pii> > pq; pq.push({dis[1], 1}); while (pq.size()) { auto [d, cur] = pq.top(); pq.pop(); if (d != dis[cur]) continue; for (int i:col[cur]) { if (done[i]) continue; done[i] = 1; for (int v:vert[i]) { if (dis[v] > d + wei[i]) { dis[v] = d + wei[i]; pq.push({dis[v], v}); } } } } ll ans = 0; for (int i = 1;i <= n;i++) ans = max(ans, dis[i]); if (ans == inf) cout << -1 << "\n"; else cout << ans << "\n"; } ``` ---- 公審時間 ---- ```cpp= #include<bits/stdc++.h> #define int long long using namespace std; signed main(){ priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq; pq.push(make_pair(0,1)); pair<int,int> cur; vector<int> distance(n+1); vector<bool> visited(n+1,0); distance[1]=0; visited[1]=1; for(int i=2;i<=n;i++) distance[i]=1e18+1; while(!pq.empty()){ cur=pq.top(); pq.pop(); visited[cur.second]=1; for(auto x:vec[cur.second]){ if(visited[x.first]==1) continue; if(distance[x.first]<=distance[cur.second]+x.second){ continue; } else{ distance[x.first]=distance[cur.second]+x.second; pq.push(make_pair(distance[x.first],x.first)); } } } int maxi=-1; for(int i=1;i<=n;i++) maxi=max(distance[i],maxi); cout<<maxi; } ``` --- ## pC 方塊王與 Meme X Setter: alvingogo ---- 走路題，只是我沒想到他那麼慘 ---- subtask 1: 枚舉每條路徑，求出他的 mex，再把這個 mex 放進路徑上每個點的集合，最後再對集合取 mex 即可 O(n^2) 條路徑 $\cdot$ O(n) 求 mex = O(n^3) ---- subtask 2: 考慮定根為 i，我想求出 i -> 每個 j 的 memex 是多少，那就以 i 為根 dfs 一次，可以發現小孩的 memex 一定比祖先大，維護 cnt 陣列進去的時候 +1 出來的時候 -1 要算一條路徑的 mex 就從父親的 mex 開始枚舉，可以發現總共枚舉次數 <= n 於是整個演算法是 O(n^2) ---- subtask 3: 樹是一條鏈 a[0] = 0 的話答案就是 0 只要維護目前的左界和右界，可以發現右界以右的答案都會是右界自己，左界類似，而只要下一個點不是向外擴張剩下的點答案就是他 ---- subtask 4: 結合 subtask 2 跟 subtask 3，以 0 為根 假設 0 -> a -> ... -> 1 那麼對於 a 的子樹的所有不在 0 到 1 的路徑上的點，他的答案都是 2 1 的子樹的點答案是 1 ---- 接下來從 2 開始跑 可以發現只要有三條路徑就會燒雞 四種情況： 1. 當前的點 i 已經考慮過了，且不是 1 的子樹 -> 剩下的答案都是 i+1 2. 當前的點 i 已經考慮過了 且是某個以她小的點的子樹 -> 不變 3. 當前的點 i 尚未考慮過，且是根到某個已經考慮過的點的路徑上 -> 剩下的答案都是 i 4. 當前的點 i 尚未考慮過，且不滿足 3. -> 他的子樹都是 i，剩下所有不在路徑上的點的子樹都是 i+1 --- ## pD 花花世界 Setter: cheissmart ---- ~~定位: 你以為 DP 優化你都學過了嗎~~ ---- 問題等價於 $flower_i = max_{j \in [b_i-k+1, b_i]}(flower_j + (a_i - a_j + 1) * m_i)$ ---- Subtask1: 暴力轉移，~~為什麼會有人零分~~ 複雜度 $O(nk)$ ---- Subtask2: 因為 $a_i = 0$，所以$flower_i = max_{j \in [b_i-k+1, b_i]}(flower_j) + m_i$ 然後 $b_i = i - 1$，所以這是 sliding window 最大值問題，可以用單調對列做到 $O(n)$ 或是線段樹$O(nlogn)$都可以過 ---- Subtask3: 跟 subtask2 一樣但是少了 $b_i = i - 1$ 這個條件，可以用單調對列加一層離線做到 $O(n)$ 或是線段樹$O(nlogn)$都可以過 ---- Subtask4: $n \leq 10^5$ 分治/線段樹 + 李超/動態凸包 $O(nlog^2n)$ ---- # 滿分解 ---- [提示](https://www.youtube.com/watch?v=MDw82gjWJbg) ---- 如果你認真體會這首歌，不難想到做法 ---- Final remark: * 不要問我 1020050909 是啥 * > 曾經以為會寫 卻又發現假解 這是今天的第六題 比賽裡的題目 好像應該學過 我不會 快告訴 我作法 --- ## pE 數數大師 Setter: FHVirus, 8e7 ---- 定位：很好喇分的神題(?) ---- ### Subtask 1,2： $k=1, 2$ 亂做 ---- ### Subtask 3,4: $k = 3, \sum n \leq 500$, $k = 4, \sum n \leq 100$ 直接枚舉 ---- ### Subtask 6, 8: $k = 3, 4$ 且 $\sum n \leq 3000$ 少枚舉一點東西，枚舉兩項然後想辦法用公式算剩下的部份 ---- ### Subtask 4, 5, 6, 8, 9: $\sum n \leq 3000$ DP! ---- 令 $dp[i][j]$ 代表選了 $i$ 個東西，且總和模 $n$ 的餘數是 $j$ 的方法數。 複雜度是 $O(n^2k)$，看起來好像不太會過但是其實常數蠻小的 ---- ### Subtask 7: $k = 3$ ---- 打表觀察，哪次不打表的 (X) 可以發現答案似乎有個很好的規律： 如果 $n \% 3 \neq 0$，答案就是$\binom{n}{3}/n$，否則是 $\lfloor \binom{n}{3} /n \rfloor +1$ 這是真的 ---- ### Subtask 10: 無其他限制 ---- 如果你繼續打表通靈的話，可能會看出一個規律。 考慮固定 $n, k$，令陣列 $a_i$ 為總和模 $n$ 餘 $i$ 的方法數。則$a_i = a_{i + gcd(n, k)}$ 也太唬爛了吧 :angry: ---- 證明：對於一個集合 $\{v_1, v_2, \cdots, v_k \}$ ，我們可以把他對應到 $\{v_1 +1, v_2 + 1, \cdots, v_k + 1 \}$（在模 $n$ 底下），這樣的話總和也會增加 $k$。如果重複這個操作 $n$ 次的話就會得到原本的序列，根據貝祖定理，這些操作中的總和必須跟原本的和在模 $gcd(n, k)$ 底下同餘，因此方法數也會相同。 ---- 因此，我們可以令 $dp[i][j]$ 為有多少種方法選 $i$ 個東西使得總和模 $gcd(n, k)$ 是 $j$。在轉移的時候一次把所有 $a + b \times gcd(n, k)$ 的數字加進來考慮。因為 $gcd(n, k) \leq k$，複雜度會是 $O(k^4)$。 ---- AC code ```cpp= const int MOD = 1e9 + 7; inline int mad(int u, int v) { u += v - MOD; u += MOD & (u >> 31); return u; } inline int mul(int u, int v) { return (uint64_t) u * v % MOD; } inline int mow(int x, int e) { int r = 1; for (; e; x = mul(x, x), e >>= 1) if (e & 1) r = mul(r, x); return r; } int sol3(int N, int K) { int g = __gcd(N, K); int num = N / g; debug(N, K, g, num); vector<vector<int>> dp(K + 1, vector<int>(g, 0)); vector<int> numCk(K + 1, 1); for (int i = 1; i <= K; ++i) numCk[i] = mul(numCk[i-1], mul(num-i+1, mow(i, MOD-2))); dp[0][0] = 1; for (int v = 0; v < g; ++v) { for (int k = K - 1; k >= 0; --k) { for (int i = 0; i < g; ++i) { if (dp[k][i] == 0) continue; for (int dk = 1, x = i; dk + k <= K and dk <= num; ++dk) { x += v; if (x >= g) x -= g; int& to = dp[k + dk][x]; to = mad(to, mul(dp[k][i], numCk[dk])); } } } } return mul(dp[K][0], mow(N / g, MOD-2)); } int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); int T; cin >> T; while (T --> 0) { int N, K; cin >> N >> K; cout << sol3(N, K) << '\n'; } return 0; } ``` --- 北市賽加油！ 沒進的也不要太難過><