第十屆高一生程式排名賽題解

# 第十屆高一生程式排名賽題解 ## Overview Problem writer: Colten、Fysty、LittleCube、PixelCat、victor.gao、yungyao Tester：Colten、PixelCat ::: spoiler AC 人數及比例（以有上傳 submission 的作為有參加） |組別|項目|A|B|C|D|E|F|G|H|I| |:-|:-|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| |高一組|滿分人數|26|10|15|12|5|4|1|1|0 ||平均分數|81.25|33.16|49.78|45.97|17.25|13.41|6.44|5.13|5.75 |線上組|滿分人數|11|6|7|6|5|3|1|1|1 ||平均分數|73.33|40|49.33|40|35.27|20.6|7.33|10.93|10.73 ::: ## A 雙倍作物 (crops) **Idea:** LittleCube **Task Prepration:** LittleCube **Statement Writer:** Colten :::spoiler **Tags:** `brute force, implementation` ::: 為什麼一堆人整天在這題判 case 啦= = **高一組首殺：** becaido **線上組首殺：** Red_rainOwO ### Problem 給你兩個跟座標軸平行的正方形求交集。 ### Subtask 1 其實我不知道如果你會基礎語法的話，排除你在做滿分推錯式子，要怎麼不過這個子題欸。 ### Subtask 2 #### Solution 1 求多邊形交集就是要用半平面交啊！可是我不會一般的半平面交欸，怎麼辦？因為直線都只有水平跟垂直，所以我們可以直接取交集然後乘起來輸出。時間複雜度 $\mathcal O(1)$。 ::: spoiler Code ```cpp #include <bits/stdc++.h> #define ll long long using namespace std; int main() { ll x1, y1, x2, y2, r1, r2, l, r, u, d; cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2; l = max(x1, x2); r = min(x1 + r1, x2 + r2); u = min(y1 + r1, y2 + r2); d = max(y1, y2); cout << max(0LL, (r - l)) * max(0LL, (u - d)) << '\n'; } ``` ::: #### Solution 2 不然我們有另一個做法：因為交集 $=$ 面積和 $-$ 聯集，我們可以用掃描線配上線段樹計算[矩形聯集面積](https://tioj.ck.tp.edu.tw/problems/1224)。時間複雜度 $\mathcal O(r + 4 \log r)$。 #### Solution 3 如果真的不行的話，有第三個做法：枚舉一個正方形，然後看裡面每一塊有沒有在另一個正方形裡。因為面積不大，所以可以直接暴力算。時間複雜度 $\mathcal O(r^2)$。注意到如果暴力開陣列交集的話會 MLE，但暴力 $4r^2$ 應該不太會 TLE。 ::: spoiler Code ```cpp #include <bits/stdc++.h> #define ll long long using namespace std; int main() { ll x1, y1, x2, y2, r1, r2, ans = 0; cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2; for (int i = 1; i <= 20000; i++) for (int j = 1; j <= 20000; j++) if (x1 < i && i <= x1 + r1 && y1 < j && j <= y1 + r1 && x2 < i && i <= x2 + r2 && y2 < j && j <= y2 + r2) ans++; cout << ans << '\n'; } ``` ::: --- ## B 機器 (machine) **Idea:** LittleCube **Task Prepration:** LittleCube **Statement Writer:** LittleCube :::spoiler **Tags:** `interactive` ::: 不要因為是互動題就怕啦 qwq **高一組首殺：** becaido **線上組首殺：** penguin71630 ### Problem 你可以查詢長度為 $n$ 的陣列的某些長度大於 $2$ 的區間和，請回溯原本的陣列。 ### $Q=n+2$ 觀察到如果我們查了某個區間跟區間 + 後面一個人，那我們就可以用減的得到後面那個人。這樣我們可以先查 $(1,\,2)$，然後求出第 $3,\,4,\,5,\,\cdots,\,n$，然後再查 $(1,\,n)$ 跟 $(2,\,n)$，求出第 $1$ 個人，再拿總和減它。 ### $Q=n+1$ 再更精確一點，先查 $(1,\,3)$ 跟 $(2,\,3)$ 可以得到 $1$，然後剩下的每一個人只要它鄰居有一個知道，就可以查它跟它鄰居拿到它。 ::: spoiler Code ```cpp #include "machine.h" using namespace std; int query(int l, int r); vector<int> revert(int n) { vector<int> ans; int b = query(0, 2); int c = query(1, 2); ans.emplace_back(b - c); for (int i = 1; i < n; i++) ans.emplace_back(query(i - 1, i) - ans.back()); return ans; } ``` ::: ### $Q=n$ 先查 $(1,\,3)$、$(1,\,2)$、$(2,\,3)$ 可以得到 $1$ 跟 $3$、然後就能知道 $2$，剩下的每一個人只要跟以前一樣處理就好。 ::: spoiler Code ```cpp #include "machine.h" #include <vector> using namespace std; vector<int> revert(int n) { vector<int> ans; int a = query(0, 1); int b = query(0, 2); int c = query(1, 2); ans.emplace_back(b - c); ans.emplace_back(a + c - b); ans.emplace_back(b - a); for (int i = 3; i < n; i++) ans.emplace_back(query(i - 1, i) - ans.back()); return ans; } ``` ::: 這題應該還有很多做法，這裡只是列出其中幾種而已。 --- ## C 電 (electricity) **Idea:** victor.gao **Task Prepration:** victor.gao **Statement Writer:** victor.gao :::spoiler **Tags:** `sorting` ::: **高一組首殺：** same0620 **線上組首殺：** huomark1001 ### Problem 在 $i$ 點時，在點 $j$ 的電神會給你 $\max(e−|i−j|,0)$，而需要承受的電力為全部電神給予的最大值，求出一個值代表站在整數點上所需要承受的電力最小值 ### Subtask 1 在 $n=L$ 時可以知道每個整數點上都站著一位電神這時候答案就會是 $e$ ### Subtask 2 在 $n=1$ 時可以直接暴力把每個點都算一次或可以發現最低的點會在 $1$ 或 $L$ 複雜度 $O(1)$ 或 $O(L)$ ### Subtask 3 可以對每位電神都去暴搜每個點所需要的承受的電力值，對全部取 $\max$ 最後再枚舉 $1 \sim L$ 哪個點答案最小複雜度 $O(nL)$ ### Subtask 4 可一個點的答案是被左邊第一位或右邊第一位電神決定所以只要對所有電神在的位置排序找出可能決定這個點的兩位電神去電答案就可或是可以把電神給的電力畫成線會是由一堆斜率為 $1,-1$ 組成的因為 $e$ 都是一樣的，所以最小值就會發生在兩相鄰電神的中點複雜度 $O(n\log n)$ 或 $O(n + L)$ --- ## D 登基大典 (worship) **Idea:** Fysty **Task Prepration:** LittleCube **Statement Writer:** PixelCat :::spoiler **Tags:** `sorting, greedy` ::: **高一組首殺：** becaido **線上組首殺：** penguin71630 ### Subtask 1 暴力枚舉或者遞迴，時間複雜度 $\mathcal O(2^nn)$ 或 $\mathcal O(2^nn^2)$。 ### Subtask 2 我們可以想到一件事情：如果我們從外圍填進來的話，裡面不管怎麼填，都可以確定裡面跟外面的相對順序。所以有一個單純的 DP 想法：絕對值是拿大減小，所以我們把他拆開，定義 $dp_{i,\,j,\,k}$ 表示前 $i$ 外面的人都決定好了，其中有 $j$ 個在負的部分、$k$ 個在正的部分。轉移就只需要從放正的跟負的處理就好，簡單來講就是藉由 $j$ 跟 $k$ 就能知道有多少是比自己大、有多少是比自己小，然後計算 DP 值。時間複雜度 $\mathcal O(n^3)$。 ::: spoiler Code ```cpp #include <bits/stdc++.h> #define ll long long using namespace std; ll n, a[505], dp[2][505][505], ans; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + 1 + n, greater<>()); for (int i = 1; i <= n; i++) for (int j = 0; j <= i; j++) { int k = i - j; if (k) dp[i % 2][j][k] = max(dp[i % 2][j][k], dp[(i - 1) % 2][j][k - 1] + (k - 1) * -a[i] + (n - k) * a[i]); if (j) dp[i % 2][j][k] = max(dp[i % 2][j][k], dp[(i - 1) % 2][j - 1][k] + (n - j) * a[i] + (j - 1) * -a[i]); } for (int i = 0; i <= n; i++) ans = max(dp[n % 2][i][n - i], ans); cout << ans << '\n'; } ``` ::: ### Subtask 3 觀察到 $i = j + k$，把剛剛的做法壓掉一個維度。時間複雜度 $\mathcal O(n^2)$。 ::: spoiler Code ```cpp #include <bits/stdc++.h> #define ll long long using namespace std; ll n, a[3005], dp[3005][3005], ans; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + 1 + n, greater<>()); for (int i = 1; i <= n; i++) for (int j = 0; j <= i; j++) { if (j < i) dp[i][j] = max(dp[i][j], dp[i - 1][j] + (i - 1 - j) * -a[i] + (n + j - i) * a[i]); if (j) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + (j - 1) * -a[i] + (n - j) * a[i]); } for (int i = 0; i <= n; i++) ans = max(dp[n][i], ans); cout << ans << '\n'; } ``` ::: ### Subtask 4 假設 $a_1\ge a_2\ge \cdots \ge a_{n-1}\ge a_n$，則最大值為 \\[\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}(n-2i+1)\cdot(a_{2i-1}+a_{2i})\\] 這可以在 $O(n\log n)$ 算出來。以下證明這確實就是最大值：假設 $p_1,p_2,...,p_n$ 已經由大到小排序好了，我們考慮每個 $p_i$ 對 $S=\sum_{i=1}^{n}\sum_{j=i}^{n}|p_i - p_j|$ 的貢獻。可以發現 \\[S=(n-1)\cdot p_1+(n-3)\cdot p_2+\cdots+(-n+3)\cdot p_{n-1}+(-n+1)\cdot p_n\quad (\star)\\] 整理一下得到 \\[S=\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor} (n-2i+1)\cdot(p_i+(-p_{n-i+1}))\\] 現在我們暫時忽略 $p_i$ 應該要是好好排好的限制，由排序不等式我們知道當 $p_1,-p_n,p_2,-p_{n-1},\cdots$ 的取值固定時，$p_1\ge -p_n\ge p_2\ge -p_{n-1}\ge\cdots$ 會使利用 $(\star)$ 算出來的 $S$ 達到最大。注意到 $(\star)$ 要達到最大，$p_1,-p_n,p_2,-p_{n-1},\cdots$ 一定都得是正的，否則把負的變成正的會更大，而全部都是正只有 $p_1=a_1,-p_n=a_2,p_2=a_3,-p_{n-1}=a_4,\cdots$ 這種可能，而且可以發現這樣會滿足剛剛忽略掉的 $p_i$ 大小順序，所以它確實是 $S$ 的最大值，證畢。  --- ## E 包裝 (packing) **Idea:** LittleCube **Task Prepration:** LittleCube **Statement Writer:** LittleCube :::spoiler **Tags:** `STL, greedy` ::: **高一組首殺：** Darren0724 **線上組首殺：** Red_rainOwO ### Observation 定義總數是 $S$，如果有一種顏色的鉛筆數量 $> \lceil\frac S k\rceil$，那顯然我們至少要那麼多包才能包完。否則，一定只需要 $\lceil\frac S k\rceil$ 包就能包完。證明：我們使用數學歸納法，並且只看 $S$ 整除 $k$ 的狀況，因為要是不符合的話，我們可以塞一堆空氣，那答案一定還是一樣。我們把數量前 $k$ 多的都拿一隻包裝，剩下一定不會有人超過 $\frac S k - 1$ 隻。假設剩下的最大的顏色剛好有 $\frac S k$ 隻，那前面那 $k$ 個人原本一定都有 $\frac S k$ 隻，這樣總數會大於 $S$，矛盾。當沒有筆的時候滿足條件，所以根據數學歸納法，任意一種筆的數量 $\leq \lceil\frac S k\rceil$ 的時候，只需要 $\lceil\frac S k\rceil$ 隻筆。 ### Subtask 1 暴力模擬把數量前 $k$ 多的都拿一隻包裝，時間複雜度 $\mathcal O(n^2C)$ 或 $\mathcal O(n^2C \log nC)$ ，其中 $|b_i| \leq 500 = C$。 ### Subtask 2 根據這個 Observation，我們只需要紀錄最大值跟總數就好，所以開一個陣列紀錄最大值，因為數量只會增加，所以直接更新就好，時間複雜度 $\mathcal O(n)$。 ### Subtask 4 利用這個 Observation，用 STL（`set` 或 `priority_queue`）維護最大值，時間複雜度 $\mathcal O(n\log n)$。 ::: spoiler Code ```cpp #include <bits/stdc++.h> #define ll long long using namespace std; ll n, k, c[200005], sum; multiset<ll, greater<ll>> st; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for (int i = 1; i <= n; i++) st.insert(0); for (int i = 1; i <= n; i++) { int a, b; cin >> a >> b; sum += b; st.erase(st.find(c[a])); c[a] += b; st.insert(c[a]); cout << (*st.begin() * k >= sum ? *st.begin() : (sum + k - 1) / k) << '\n'; } } ``` ::: ### Subtask 3 設計給知道 $k=2$ 是經典問題的人，希望有引導到想出結論 >< --- ## F 薪水 (salary) **Idea:** Fysty **Task Prepration:** Fysty **Statement Writer:** Fysty :::spoiler **Tags:** `math, bitmask` ::: **高一組首殺：** becaido **線上組首殺：** Penguin07 ### Subtask 1 只要預處理 $f(1),\cdots,f(200000)$，複雜度 $O(\max n_i\log\max n_i+t)$。 ### Subtask 2 令 $g(n)=f(1)+f(2)+\cdots+f(n),a_n=g(2^n-1)$。觀察到 $1,2,3,\cdots,2^{n-1}-1$ 的貢獻為 $a_{n-1}$。 $2^{n-1},2^{n-1}+1,\cdots,2^n-1$ 的 highest bit 都是 $2^{n-1}$，這個 bit 的貢獻為 $2^{n-1}$。考慮把 $2^{n-1},2^{n-1}+1,\cdots.,2^n-1$ 的 highest bit 扣掉變成 $0,1,2,\cdots,2^{n-1}-1$，剩下的數字只有 $2^{n-2},2^{n-2}+1,\cdots,2^{n-1}-1$ 還能對答案有貢獻(因為 highest bit 是 $2^{n-2}$)，這部分貢獻為 $a_{n-1}-a_{n-2}$。因此有 $a_n=2a_{n-1}-a_{n-2}+2^{n-1}$。令 $d_i=a_n-a_{n-1},d_1=1$，則有 $d_i=d_{i-1}+2^{n-1},a_n=d_1+d_2+\cdots+d_n$。可得 $a_n=\sum_{i=0}^{n-1} 2^i(n-i)=2^{n+1}-(n+2)$。只需要預處理 $2^1-1,2^2-1,\cdots,2^{200000}-1$，就可以 $O(1)$ 詢問，整體複雜度 $O(\sum len_i+t)$。 ### Subtask 3, 4 假設 $2^k\le n<2^{k+1}$。 $1,2,\cdots,2^k-1$ 的貢獻已知是 $2^{k+1}-(k+2)$。我們觀察 $2^k,2^k+1,\cdots,n$ 的 highest bit。對於所有 $k \ge i\ge 0$，$2^k,2^k+1,\cdots,n$ 之中不小於 $2^k+2^{k-1}+\cdots+2^i$ 的正整數個數為 $b_i=\max(0,n-(2^k+2^{k-1}+\cdots+2^i)+1)$。仔細觀察會發現 $2^k,2^k+1,\cdots,n$ 中，第 $i$ 個 bit 對答案的貢獻恰為 $b_i$。因此 $g(n)=a_k+b_0+b_1+\cdots+b_k$。 $b_i$ 如果不預處理會噴到 $O(len_i^2)$，預處理可以 $O(len_i)$。如果不提前算出 $a_k$ 的話，可以用同樣的方法分析 $g(2^k-1)$，注意到這樣反覆執行會讓複雜度達到 $O(len_i^2)$。複雜度 $O(\sum len_i^2)$ 或 $O(\sum len_i)$。 :::spoiler Code ```cpp= #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; #define MottoHayaku ios::sync_with_stdio(false);cin.tie(0); #define rep(i,n) for(int i=0;i<n;i++) #define rep1(i,n) for(int i=1;i<=n;i++) #define pb push_back #define F first #define S second const int MOD=1e9+7; ll p2[200005]; signed main() { MottoHayaku p2[0]=1; rep1(i,200000) p2[i]=p2[i-1]*2%MOD; ll t; cin>>t; while(t--) { string s; cin>>s; ll sz=s.size(); vector<ll> sum(sz+1,0); rep(i,sz) sum[i+1]=(sum[i]+p2[i]*(s[sz-1-i]-'0')%MOD)%MOD; ll ans=(p2[sz]-1-sz+MOD)%MOD; rep(i,sz) { if(s[i]=='0') continue; if(i==sz-1) ans=(ans+1)%MOD; else { ans=(ans+sum[sz-1-i]+1)%MOD; if(s[i+1]=='0') break; } } cout<<ans<<"\n"; } } ``` ::: --- ## G 愛人 (lover) **Idea:** victor.gao **Task Prepration:** victor.gao **Statement Writer:** yungyao :::spoiler **Tags:** `tree, DP` ::: **高一組首殺：** becaido **線上組首殺：** abc864197532 ### Problem 給一棵樹，每一條邊 $u_i,v_i$ 都可以走 $c_i$ 次輸出 $n$ 個數，分別代表從第 $i$ 個點開始最多能走過幾次邊 ### Observation 如果現在邊可以走 $1$ 次，那就只能走過去如果可以走 $2$ 次，那可以走過去再走回來如果可以走 $3$ 次，那可以先來回走一趟再走過去如果可以走 $c$ 次，那可以先來回走很多趟直到剩 $1 \sim 2$ 次 ### Subtask 1 樹為一條鏈，可以當作序列處理定義 $dp$ 狀態 $dpl[i][0]$ 為只往左走且不需回到 $i$ 的最大數量 $dpl[i][1]$ 為只往左走且要回到 $i$ 的最大數量 $dpr[i][0]$ 為只往右走且不需回到 $i$ 的最大數量 $dpr[i][1]$ 為只往右走且要回到 $i$ 的最大數量第 $i$ 個點的答案會是 $\max(\max(dpl[i][0],dpl[i][1])+dpr[i][1],\max(dpr[i][0],dpr[i][1])+dpl[i][1])$ 轉移 : 假設邊 $i-1,i$ 可以走 $c$ 次 - $c=1$ $dpl[i][1]=0$ $dpl[i][0]=\max(dpl[i-1][0],dp[i-1][1])+1$ - $c>1$ $dpl[i][1]=dp[i-1][1]+c/2 \times 2$ $dpl[i][0]=\max(dpl[i-1][0],dp[i-1][1])+c-((c-1)\%2)$ $dpr$ 也是一樣的轉移式複雜度 $O(N)$ ### Subtask 2 所有 $c$ 都是 $1$ 代表走過就不能再走等價樹直徑問題可以兩次 DFS 或樹 DP 複雜度 $O(N)$ ### Subtask 3 從 Subtask 1 的狀態稍微改變定義 $dp[i][0]$ 代表往 $i$ 的子樹走且不需回到 $i$ 的最大數量 $dp[i][1]$ 代表往 $i$ 的子樹走且需要回到 $i$ 的最大數量轉移 : 假設可以 $i$ 的孩子有 $v_1,v_2,\cdots,v_n$，可以走的次數分別為 $c_1,c_2,\cdots,c_n$ $dp[i][1]=\sum_{i = 1}^{n} dp[v_i][1]+c_i/2*2$ $dp[i][0]=dp[i][1]+\max(dp[v_1][0]-dp[v_1][1]+(c_1\%2\ ?\ 1 :-1),\cdots,dp[v_n][0]-dp[v_n][1]+(c_n\%2\ ?\ 1 :-1))$ 同樣要處理特別 $c_j=1$ 然後以每個點做為根各自 DP 複雜度 $O(N^2)$ ### Subtask 4 跟 Subtask 5 差別是不用 long long 注意 long long ### Subtask 5 按照 Subtask 3 可以發現它可以換根在換根的同時維護好現在子樹的 $\max(dp[v_1][0]-dp[v_1][1]+(c_1\%2\ ?\ 1 :-1),\cdots,dp[v_n][0]-dp[v_n][1]+(c_n\%2\ ?\ 1 :-1))$ 紀錄最大和次大與來源就可以做了或是直接用 multiset 全部一起放進去複雜度 $O(N),O(N\log N)$ ### Note :::spoiler 題目想法來源 [CF 201C](https://codeforces.com/problemset/problem/201/C) 把這題變成樹上版本 ::: ::: spoiler yungyao 的原汁原味的超怪題敘 ```md # 小方塊與他的愛人 (lover) 傳說中，遙遠的南方有個未知的國度，又被稱為 CP(Competitive Programming) 國 CP 國中有個地方：暴風之城-新竹在那座城市裡，住了一位清純可愛的 JK，她的名字叫做像素貓像素貓是位秀色可餐的女孩子，她身上總流著滴滴清純的蒸餾水那麼可愛的 JK，想必有著眾多的追求者然而作為 CP 國少數的女孩子，像素貓無情地拒絕了所有追求者在更加遙遠的地方，有座流著糖與蜜的城市：台南小方塊這位電神在座城市誕生了儘管他出生就是為了征服整個 CP 國，他卻不經意地聽說了像素貓的傳說他想著：像我一樣又帥又電的人，怎麼可能會被拒絕呢？於是他就這樣出發了。然而從台南到新竹的路上充滿了各種阻撓，不過小方塊都用他的過人才智一一解決了當小方塊終於抵達新竹時，卻遭遇了嚴重的難題首先是新竹似乎只有麥當勞可以吃再來是新竹是一座由 $n$ 家麥當勞所組成的城市由於新竹的貢丸交通系統非常花錢(具體來說，每個新竹人都會被配給一顆貢丸，而新竹人平常會在貢丸滑行道中通勤) 因此新竹市政府在像素貓的智慧下把整座城市用洽 $n-1$ 條雙向滑行道連接在一起而且每間麥當勞間都存在路徑通往彼此不幸的是小方塊受不了新竹的食物，無法騎乘貢丸可怕的是每座滑行道裡都有 yungyao 的皮卡丘分靈體在玩 speedrun 小方塊的遊戲 (具體來說，yungyao 們會挑戰可以多快速地惹怒小方塊，例如 yungyao 本人正在用無限拖稿 speedrun) 因此小方塊對於連接點對 $(u_i, v_i)$ 的滑行道最多只能走 $c_i$ 次，不然會生氣小方塊為了要讓像素貓對他印象深刻，決定展現自己卓越的運動才能，走越多條滑行道越好(同一條滑行道重複走可以重複計算) 不過小方塊並不知道自己現在在哪，因此想請你算出以任意一個點為出發點，最遠能走多遠呢？ ``` ::: --- ## H 工廠 (factory) **Idea:** LittleCube **Task Prepration:** LittleCube **Statement Writer:** LittleCube :::spoiler **Tags:** `graph, BFS, shortest path` ::: **高一組首殺：** alvingogo **線上組首殺：** abc864197532 ### Problem 給你一個 DAG，在無自環且兩點間只有一個方向的條件下讓它變不是 DAG。 ### Subtask 1 暴力找所有的環然後檢查可不可行。時間複雜度可以 $\mathcal O(n!+\sum k)$ 遞迴。 ### Subtask 2 對走過的點 DP，類似旅行推銷員問題。時間複雜度 $\mathcal O(2^nn^2+\sum k)$。 ### Subtask 3 直接對每個點都 BFS，記錄不能找長度 $\leq 2$ 的環（也就是每個點可能會被 visit 兩次：距離為 1 跟大於 1）。時間複雜度 $\mathcal O(n^3)$。 ### Observation 1 答案一定是 $1,\,2,\,3,\,-1$。證明：先亂找一個解，假設他是簡單環（因為不是簡單環的可以切開），對任意環上不相鄰的兩點，一定存在其中一個方向，所以可以把環剖成兩半，每次大小都會減少，最後一定會剩下大小是 $3$ 的環，所以答案要不是找不到任何環，就是答案是 $1,\,2,\,3$。 ### Observation 2 更進一步，假設一開始找的環有一條給定的邊，那答案一定 $\leq 2$。證明：對任意環上不相鄰的兩點，一定存在其中一個方向，所以可以把環剖成兩半，假設那個方向是給定的邊，那切出來的環顯然有一條給定的邊。不然，假設那個邊不是給定的，一定兩個方向都可以，所以我們可以選至少有一條的那一邊。做到最後的 3 條邊一定有一條是給定的，所以答案最多是 $2$。 ### Observation 3 定義一個把點分成兩邊的方法稱為**分割**如果其中一邊的點都有連到另一邊的所有點。顯然圖如果有分割，我們可以把它切開來看。另外，一個**分割**的兩群點一定一半在拓撲排序的前面、另一半在後面。對一個沒有分割的圖，答案為 $3$ 若且唯若沒有邊且點數 $\geq 3$。點數 $\geq 3$ 顯然，我們想要證明有邊的情況答案為 $1,\,2$。證明：首先，因為圖沒有分割，所以在拓撲排序的任意一個點 $u$ 如果順序在 $v$ 的後面，一定存在一條路徑從 $u$ 到 $v$，不然 $u,\,v$ 之間至少有一個**分割**。所以假設有任何一條邊，我們就走那條邊，這樣一定可以走回來（因為沒有分割），這個環上至少有一條邊是給定的，所以答案就不會是 $3$（根據 Observation 2）。 ### Subtask 4 利用 Observation 1，我們可以先拓撲排序，然後先做 $\mathcal O(n\sum k)$ DP 算可以達到的點，再枚舉 $\mathcal O(n^2)$ 條不存在的邊，看答案可不可能是 $1$，接下來枚舉每條邊，看可不可以形成答案是 $2$ 的環，也就是判兩邊可以達到的點有沒有存在都沒連過的，複雜度 $\mathcal O(n\sum k)$，最後利用 Observation 3，在 $\mathcal O(n^2)$ 找出所有分割之後，在切出來的子圖裡看有沒有邊且大小 $\geq3$，如果有那就會有 $3$ 的答案。總時間複雜度 $\mathcal O(n(n+\sum k))$，因為所有瓶頸只涉及 `bool` 的操作所以很快，如果被卡常（應該是不會，除非你不是用這個方法）的可以用 `bitset` 加速。理論上在 Subtask 3 的 BFS 每次只嘗試沒有走過的點的話，一次 BFS 只會失敗 $\mathcal O(\sum k)$ 次，有適當處理的話可以在 $\mathcal O(n(n+\sum k))$ 做完，應該能過 Subtask 4 但我們沒有特別去試這個解。 ::: spoiler Code ```cpp= #include <bits/stdc++.h> #define pii pair<int, int> using namespace std; int n, m, out[5005], scnt, topo[5005]; bool sep[5005], adj[5005][5005], reach[5005][5005], vis[5005][5005], connect[5005][5005]; vector<pii> v; queue<int> q; signed main() { cin >> n; for (int i = 1; i <= n; i++) { reach[i][i] = 1; connect[i][i] = 1; int j, k; cin >> j; m += j; while (j--) { cin >> k; adj[k][i] = connect[i][k] = connect[k][i] = 1; out[k]++; } } for (int i = 1; i <= n; i++) if (out[i] == 0) q.push(i); for (int i = 1; i <= n; i++) { int u = q.front(); topo[n - i + 1] = u; q.pop(); for (int i = 1; i <= n; i++) if (adj[i][u]) { out[i]--; for (int j = 1; j <= n; j++) reach[i][j] |= reach[u][j]; if (out[i] == 0) q.push(i); } } long long cnt = 0; for (long long i = 1; i < n; i++) { for (int j = 1; j < i; j++) if (adj[topo[j]][topo[i]]) cnt--; for (int j = i + 1; j <= n; j++) if (adj[topo[i]][topo[j]]) cnt++; if (cnt == i * (n - i)) sep[i] = 1; } for (int i = 1; i <= n; i++) if (v.empty()) { int j = 1; for (; j <= n; j++) if ((reach[i][j] & (!connect[i][j]))) break; if (j <= n) v.emplace_back(pii(j, i)); } for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) if (adj[i][j] && v.empty()) { int k = 1; for (; k <= n; k++) if ((!connect[i][k]) & (!connect[j][k])) break; if (k <= n) { v.emplace_back(pii(j, k)); v.emplace_back(pii(k, i)); } } for (int i = 1; i <= n; i++) if (v.empty()) { int j = i; while (j < n && !sep[j]) j++; if (j - i + 1 >= 3) { v.emplace_back(pii(topo[i], topo[i + 1])); v.emplace_back(pii(topo[i + 1], topo[i + 2])); v.emplace_back(pii(topo[i + 2], topo[i])); } i = j; } if (v.empty()) cout << -1 << '\n'; else { cout << v.size() << '\n'; for (auto [a, b] : v) cout << a << " " << b << '\n'; } } ``` ::: ### About Scoring 其實這題部分分不好拿到，除了亂做以外，如果你掉答案為 $1$ 的 Case 的話會拿到一半。 ### About `bitset` 關於 Subtask 4 答案為 $3$ 的部分，其實可以透過 `bitset` 暴力壓 $\mathcal O(n^3)$ 過。我自己也猶豫很久要不要卡掉這個解，不過有很多考量的點是： 1. 或許我分析不夠緊，其實不會跑滿到 $n^3$ 1. 很難卡，Fysty 給出了一個跑超快的解（在 C++20 (64)）。 2. 如果卡下去不僅要觀察一堆還要 `bitset`，`bitset` 實在很多餘。 3. 這題如果這樣設計我就怕有點卡常了（用 C++14 可能會慢一點點），`bitset` 卡下去我怕會卡到一堆人。 4. 卡下去如果 BFS 原本會過的話，就很有可能不會過了。綜上所述，這題就沒有特別卡 `bitset` 了，也希望不要太多人用 `bitset` $\mathcal O(n^3)$ 過 >< ### About Test Data 這題的結果很酷，但實際上測資不好生，而且我還假解好多次。我一共用了 6 個 generator： - `random` 隨機圖 - `complete` 都是完全子圖，逼迫答案要是 $2$ 以上 - `complete-cluster` 都是完全子圖接在一起，卡掉特判完全圖的 - `empty` 空圖，生 corner case - `nearly-empty` 生可以拔掉拓樸起點跟終點獨自在**分割**的一邊的，一開始我以為只有這個**分割**的 case，所以才有這個 - `seperator` 生有一堆**分割**的圖最後還要寫 `checker`，全部裡面我花最多時間的大概就是這題（也因為我一直亂假解，另一題是 B 因為互動題很麻煩）。這題測資其實有小問題，在比賽中才發現漏一個小 case 但已經有人拿到部分分了，所以就只有最後一個子題有，抱歉 qwq ## I 選舉 (election) **Idea:** LittleCube **Task Prepration:** LittleCube **Statement Writer:** LittleCube :::spoiler **Tags:** `prefix sum, data structure` ::: **線上組首殺：** abc864197532 ### Problem 定義一個顏色 $c$ 是一個連續區間的**嚴格眾數**僅當它的出現頻率大於區間長度的一半。對每個顏色 $c$ 算**嚴格眾數**的連續區間數量。 ### Subtask 1, 2 暴力跟一起暴力，這邊就不再贅述。 ### Subtask 3 觀察到如果 $c$ 是一個區間的**嚴格眾數**，那那個區間的長度為奇數、奇數號位都是 $c$，所以直接對每個顏色的每個連續間隔出現算就好。 ### Subtask 4 在算顏色 $c$ 的時候，定義 $a_i = 1$ 如果 $c_i = c$；$a_i = 0$ 如果 $c_i \neq c$，一個區間 $[l,\,r]$ 的嚴格眾數是 $c$ 的條件就可以轉化成 \\[a_l + a_{l+1} + \cdots + a_r > \frac 1 2(r - l + 1)\\] 利用前綴和的技巧，假設 $S$ 是 $a$ 的前綴和，條件就可以寫成 \\[S_r - S_{l-1} > \frac 1 2(r - (l - 1))\\] 也就是說我們要統計有多少對 $(l,\,r)\quad(0 \leq l \leq r \leq n)$ 滿足 \\[S_r - S_l > \frac 1 2(r - l)\\] 也就可以寫成 \\[2S_r - 2S_l > r - l\\] \\[2S_r - r > 2S_l - l\\] 我們可以透過一棵線段樹或 BIT，對 $2S_i - i$ 的值域開並記錄數量，在 $\mathcal O(mn\log n)$ 的時間內解決問題。 ::: spoiler Code ```cpp= #include <bits/stdc++.h> #define ll long long #define fast ios::sync_with_stdio(0), cin.tie(0) using namespace std; const int off = 300'001; int n, m; ll bit[600006], ans[300006], a[300006]; void init() { for (int i = 1; i <= off + n; i++) bit[i] = 0; } void modify(int pos) { for (int i = pos + off; i <= off + n; i += (i & -i)) bit[i]++; } ll query(int pos) { ll ans = 0; for (int i = pos + off; i > 0; i -= (i & -i)) ans += bit[i]; return ans; } signed main() { fast; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= m; i++) { init(); int pre = 0; modify(0); for (int j = 1; j <= n; j++) { pre += -1 + 2 * (a[j] == i); modify(pre); ans[i] += query(pre - 1); } } for (int i = 1; i <= m; i++) cout << ans[i] << " \n"[i == m]; } ``` ::: ### Subtask 5 我們進一步觀察，假設一個區間 $[L,\,R]$ 都沒有出現顏色 $c$，那它的 $2S_i - i$ 剛好會依序遞減 $1$。同時，在這段區間內都不會出現任何區間眾數，也就是說我們可以先對他們都查詢 $2S_i - i$ 對應到的答案再更新資料結構。這時候我們要一次處理連續的詢問，我們的線段樹上的節點 $k$ 就要改成記錄 $2S_i - i < k$ 的數量共有多少個，才能在 $\mathcal O(\log n)$ 一次處理掉區間詢問都沒有出現顏色 $c$ 部分的答案。在這個查詢結束後，我們要更新這個資料結構，剛好就會對應到一部份的區間加等差數列以及一部份的區間加值，同樣可以利用線段樹維護。實作上注意換下一個線段樹時要清空，除了回復操作、吃毒砸動態開點以外還可以用區間改值，會快很多。總時間複雜度 $\mathcal O(n\log n)$。 ::: spoiler Code ```cpp= #include <bits/stdc++.h> #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define F first #define S second #define fast ios::sync_with_stdio(0), cin.tie(0) using namespace std; const int off = 300'001; int n, m; ll seg[1200006]; pll lazy[1200006]; bool zero[1200006]; ll ans[300006]; vector<int> v[300006]; ll getval(int i, ll L, ll R) { ll sum = (L + R) * (R - L + 1) / 2; return seg[i] + lazy[i].F * sum + lazy[i].S * (R - L + 1); } pll operator+(pll p1, pll p2) { return pll(p1.F + p2.F, p1.S + p2.S); } void modify(int mL, int mR, pll f, int i = 1, int L = 0, int R = 2 * off) { if (mL <= L && R <= mR) lazy[i] = lazy[i] + f; else if (mR < L || R < mL) return; else { int mid = (L + R) / 2, l = i + 1, r = i + ((mid - L + 1) << 1); if (zero[i]) { zero[l] = zero[r] = 1; lazy[l] = lazy[r] = pii(0, 0); seg[l] = seg[r] = 0; zero[i] = 0; } lazy[l] = lazy[l] + lazy[i]; lazy[r] = lazy[r] + lazy[i]; lazy[i] = pii(0, 0); modify(mL, mR, f, l, L, mid); modify(mL, mR, f, r, mid + 1, R); seg[i] = getval(l, L, mid) + getval(r, mid + 1, R); } } ll query(int qL, int qR, int i = 1, int L = 0, int R = 2 * off) { if (qL <= L && R <= qR) return getval(i, L, R); else if (qR < L || R < qL) return 0; else { int mid = (L + R) / 2, l = i + 1, r = i + ((mid - L + 1) << 1); if (zero[i]) { zero[l] = zero[r] = 1; lazy[l] = lazy[r] = pii(0, 0); seg[l] = seg[r] = 0; zero[i] = 0; } seg[i] = getval(i, L, R); lazy[l] = lazy[l] + lazy[i]; lazy[r] = lazy[r] + lazy[i]; lazy[i] = pii(0, 0); return query(qL, qR, l, L, mid) + query(qL, qR, r, mid + 1, R); } } void reset() { zero[1] = 1; seg[1] = 0; lazy[1] = pii(0, 0); } signed main() { fast; cin >> n >> m; for (int i = 1; i <= n; i++) { int c; cin >> c; v[c].emplace_back(i); } for (int i = 1; i <= m; i++) if (!v[i].empty()) { int last = 0, cur = off; v[i].emplace_back(n + 1); for (int j = 0; j < (int)v[i].size(); j++) { int pre = v[i][j] - 1; ans[i] += query(cur + last - pre - 1, cur - 1); modify(cur + last - pre, cur, pii(1, 1 - (cur + last - pre))); modify(cur + 1, 2 * off, pii(0, v[i][j] - last)); cur = cur + last - v[i][j] + 2; last = v[i][j]; } reset(); } for (int i = 1; i <= m; i++) cout << ans[i] << " \n"[i == m]; } ``` :::

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.