2021 附中暑期培訓模擬競賽 I | 競程

題目

Problem A - 直播循環

一個直播循環是由 $s$ 天的直播時段和 $r$ 天的休息時間構成。現有位直播主要進行 $n$ 個遊戲的直播，第 $i$ 個遊戲需在某個循環的第 $a_i$ 天遊玩。且每個遊戲直播之間須間隔至少 $r$ 天的休息日。求最少需幾個直播循環才能至少玩過所有遊戲一遍，並輸出每個遊戲須在第幾個循環進行直播（輸入任一種安排方式）。

$n \leq 2 \times 10^5$
$0 \leq r \leq s \leq 10^9$

子任務	分數	額外輸入限制
1	3	$r = 0$
2	13	$n = s$
3	9	$n \le 10$
4	18	$n \le 1000$
5	57	無額外限制

Problem B - 兔田彩券

給定 $m$ 個數對 $(a_i, b_i), a_i \neq b_i$ ，每個數對的數字皆 $\leq n$ 。接著有 $q$ 筆詢問，每筆詢問給定 $(l, r, s, t)$ ，求有多少數對 $(a_i, b_i)$ 滿足 $(l \leq a_i \leq r \land s \leq b_i \leq t)$ 或 $(l \leq b_i \leq r \land s \leq a_i \leq t)$ 。

$1 \leq n \leq 2000$
$1 \leq m, q \leq 2 \times 10^5$

子任務	分數	額外輸入限制
1	15	$n, m, q \leq 500$
2	21	$n \leq 100, q \leq 10000$
3	11	$l_i \leq r_i < s_i \leq t_i$
4	53	無額外限制

Problem C - 魔法師測驗

有一棵 $n$ 個節點的樹，每個節點有權重 $a_i$ ，求最長的路徑滿足路徑上的節點權重 $\gcd \neq 1$ ，輸出該路徑的節點數。

$1 \leq n, a_i \leq 2 \times 10^5$

子任務	分數	額外輸入限制
1	8	$m_1 = m_2 = \dots = m_N$
2	6	$n \leq 1000$ 且 $x_i = i, y_i = i + 1$
3	12	$x_i = i, y_i = i + 1$
4	19	$m_i$ 皆為質數
5	16	$m_i \leq 100$
6	14	$n \leq 1000$
7	25	無額外限制

Problem D - 刷怪塔

有 $T$ 筆測資，每筆測資有兩個數字 $a, b$ 。

令 $s$ 初始為 $1$ ，定義一次操作如下：

選擇 $a, b$ 數字較大者（若相同則選擇 $a$ ），並將該數字減去 $s$ 。
將 $s$ 的值增加 $1$ 。

重複操作直到 $a, b$ 皆 $\leq s$ 。

輸出總操作次數。

$1 \leq T \leq 10^5$
$0 \leq a, b \leq 10^{18}$

子任務	分數	額外輸入限制
1	8	$a = 0$
2	21	$a = b$
3	12	$a, b \leq 1000$
4	59	無額外限制

Problem E - 時空旅人之爭

有一棵 $n$ 個節點的樹，自第 $0$ 秒開始，複製人便佔領節點 $1$ ，並且每隔 $2$ 秒往相鄰節點擴散。

接著有 $q$ 筆詢問 $(s, t)$ ，代表從節點 $s$ 開始經過最短路徑到達 $t$ 。時間從 $0$ 秒開始計算，每前往下一個節點需要 $1$ 秒。求這段路程中有多少節點已經被複製人佔領。

$1 \leq n, q \leq 2 \times 10^5$

子任務	分數	額外輸入限制
1	14	$n, q \leq 1000$
2	9	$\forall 1 \leq i < n, v_i = u_{i+1}$
3	37	除了第 $1$ 個時空外，每個時空最多只有兩個透過裂縫相連的其他時空
4	40	無額外限制

比賽結果

2021 summer practice contest 1
------------------------------
Problem Difficulty:
pA < pB < pC < pE < pD
------------------------------
00:35 pA 100
01:04 pB 15
01:18 pD 0
01:21 pD 8
01:27 pD 20
02:01 pE 0
02:16 pE 0
02:27 pE 0
02:37 pE 0
02:59 pC 0
------------------------------
Score Gained:
pA 100
pB 15
pC 0
pD 20
pE 0

Total Score: 135
Final Rank:  3rd

比賽過程

開賽先下載所有題本，大概先花了 15 分鐘閱讀題本。

當時的難度排序：pA < pE < pC < pD < pB

pA 在紙上畫了一些圖後，馬上就想到 greedy+STL 就好了。

感覺這是最簡單的題目，沒什麼猶豫就寫下去了，刻模板 10 分鐘，但寫到後面才發現完了，我連 STL 的操作都不太熟悉，於是把 multiset 砍掉換成 map 才終於刻完。丟上去一發 AC。

00:35 pA 10 0分

接下來輪流想其他題目的作法。

pE 也是畫圖出來之後，很快想到 LCA+倍增二分搜，加上最近剛好有補到 LCA，所以我對實作滿有信心的，這題於是被我排在前面。

pC 感覺樹 DP，有觀察到每個數字的質因數不多，可是還是沒有複雜度好的想法，只有想到枚舉每個 $\leq 2\times 10^5$ 的質因數後套樹直徑。

pD 二分搜，但還要分一堆 case，非常麻煩，感覺寫下去了就會炸掉。

pB 有注意到 $n$ 特別小，除此之外沒任何想法，感覺是要寫線段樹或是莫隊，我對這種區間問題真的完全沒轍 QQ。但是有 15 分是很水的暴力分，寫完 5 分鐘就丟上去了。

01:04 pB 1 5分

pD 的 20 分也很好水，先拿了簡單二分搜的 8 分，再拿暴力 12 分。

這裡比較雷的點是，明明 8 分的二分搜很好寫（大概兩分鐘就可以寫完），但我心態上一直覺得二分搜才 8 分感覺沒什麼價值，莫名地一直猶豫到底要不要寫，或是去想正解，拖一拖結果拖了 15 分鐘才拿掉。我到底在想什麼啊 wwwwwwwwww

01:27 pD 2 0分

這時已經過半場，pC 樹 DP 依舊只有那個暴力的想法，這題子題切得很細但我完全沒有認真讀，很主觀地認為這個做法頂多 10~20 分，加上對於 pE 的滿分解太過自信，也沒想著要撈分就直接刻下去了。

LCA 的部分很順，5 分鐘就搞定，但最後的倍增二分搜沒有想清楚就直接寫，導致碰到一大堆 bug，碰一個 bug 就多加幾行特判處理，搞到最後 code 長得很肥。

好不容易範測過了，丟上去，結果

02:01 pE 0分

心中默念一聲幹之後回去好好看子題，結果我連一條鍊的測資都沒過。於是隨便生了一個鍊的測資，結果又找到更多問題，但我沒有打算重寫，反而是在那複雜的 code 上面又多加了更多的 if。看似解決了又丟上去。

02:16 pE 0分

糟糕，心態越來越不對，已經砸了 50 分鐘在這題了但我沒有收手，給自己停損點但都是給假的。一直很懊惱很不捨，寫了那麼長的 code 但一分也沒有，抱著「只要再修一下可能就可以 AC 了，現在放棄的話前面那一個小時就全都白費」這種斷不開的糟糕想法一直燒到比賽剩 20 分鐘。

02:27 pE 0分

02:37 pE 0分

這時候頭已經很脹痛，腦中思緒全部打結，心態上又一直很自責、懊悔，之後去上廁所，但心情還沒完全平復就又回到電腦桌前。

這時候才開始寫 pC 的暴力分，順便加個唬爛剪枝（按照質因數出現的次數排序做樹直徑）。質數篩 + 質因數分解 + 樹直徑 DP 刻完大概剩 5 分鐘，結果測了範測，完了，是爛的。最後就盯著 code 盯到結束前 30 秒，很情感地把 code 丟了上去，想當然的一分都沒有。

02:59 pC 0分

賽後檢討

先說說耍智障的地方，真的太多了。

pA 居然刻到後面才發現不能用 multiset 而要用 map。
pB 耍笨，套到二維平面上才發現只需要二維前綴和就行了，但我所有的思考過程全都在一維直線上，沒跳脫出來。
pC 有兩個智障 bug。
- 我所有的 code 都是 1-based 的，但輸入數字的時候卻從 index 0 開始輸入。
- 樹 DP 有一段 code
```
if (tag[u] == 0) {
    dp[u] = 0;
    return;
}
```
關鍵在於不能馬上 return 而是要繼續 dfs，真是智障。
pE 爛在倍增二分搜，結果只是我沒有注意到我的寫法會讓指針跳到 LCA 上面。

策略的檢討留到最後面一起統整，但這整場打得真的很不滿意。