今年沒有現場賽 QQ，也不分初賽和決賽，就直接是線上賽了。

還沒有公開題本，就自己之後去官網找吧 (O)。還有我忘記備份程式碼了 QQ。

計分板·官解

以下分數格式是 verdict / time + penalty

題目

pA 殿壬的飲料王國

WA / -

有 $N \times M$ 個人，其中有 $M$ 個人有一個面額 1 元的硬幣、$M$ 個人有一個面額 2 元的硬幣、……、$M$ 個人有一個面額 $N$ 元的硬幣。他們要排隊買一塊錢的飲料，老闆一開始沒有錢，所以他只能用這些人付的錢來找錢。另外，這些人分成兩群，對於有面額 $i$ 元硬幣的人，第一群有 $a_i$ 人、第二群有 $b_i$ 人。求有多少種合法的排隊方式。有同樣硬幣的人視為互不相同。

首先發現到因為每一種面額的數量都是一樣的，所以 2 元一定只能用 1 元找、3 元一定只能用 2 元找、……，這樣就可以很好判斷一個排隊方式是不是對的：在第 $j$ 個面額 $i$ 的人之前，一定要有至少 $j$ 個面額 $i-1$ 的人。所以如果有 $a_{i-1} > a_i$ 就會無解。

有同樣硬幣的人視為不同的部份其實最後再乘一乘就好了，所以就先算 $1$ 到 $N$ 各有 $M$ 個有幾種合法排列。

本來我們想了各種組合的解法，像是把 2 插進一堆 1 裡面、3 再插進去……，或是分成好幾條 $1,2,3,\dots$，再拼起來，但這些作法都會多算或不好算。

後來我們想到可以把它放到二維表格上，第 $i$ 列第 $j$ 格的數字表示面額 $i$ 的第 $j$ 人排第幾個，然後 $(i,j)$ 的數字要比 $(i-1,j)$ 和 $(i,j-1)$ 大。然後兩群人會把這個表格切開，左上方的都要比右下方大，其中一邊看起來會是一個 young tableau，然後因為其中一邊的數字集合是確定的，所以兩邊可以分開算數量再乘起來，右下方的只要視為是倒過來的 young tableau 就好。

所以現在問題變成：有每一列長度是 $a_1,a_2,\dots,a_N$ 和 $b_N,b_{N-1},\dots,b_1$ 的 young tableau，有幾種方式在裡面填數字，使得每一個格子裡的數字都比它上面和右邊的大。

我寫了個暴搜找規律找了老半天，林柏瑄不知道怎麼通靈的看出他是前綴和（在只有兩列的時候），後來得出了 $dp[i_1][i_2]\dots[i_N]=dp[i_1-1][i_2]\dots[i_N] + dp[i_1][i_2-1]\dots[i_N] + dp[i_1][i_2]\dots[i_N-1]$ 這樣的式子（$i_k=$ 第 $k$ 列長度），其實這超顯然，根本不需要暴搜。

想成是在一個超立方體裡面的話，就會變成是從 $(1,1,\dots,1)$ 走到 $(a_1,a_2,\dots,a_N)$（或 $b$），路上前面維度的座標都比後面大的方法數，其實就有點類似卡塔蘭數，只是是高維版本，我們想了一陣子都想不到。

官解是用 Hook length formula 直接做掉。

pB 小 P 打仗

AC / 88 + 0

有 $N$ 個人要打疫苗，第 $i$ 個人打完後要休息 $r_i$ 天（含當天）、戰鬥力是 $s_i$，接下來 $N$ 天每一天都要有恰一人打疫苗。對每一個 $1 \leq k \leq N$，求在適當安排打疫苗順序的情況下，第 $k$ 天沒有在休息的人戰鬥力總和最大可以是多少。

重點就是要安排哪些人在第 $k$ 天以前打、在哪一天打，如果在 $k-i$ 天打的人是 $p$，那就要 $r_p \leq i$ 他才不會在第 $k$ 天休息。固定 $k$ 時顯然可以 Greedy，從 $i=0$ 開始看，找到還沒決定哪天的的人裡，$r_p \leq i$ 的 $s_p$ 最大的 $p$，讓他在第 $k-i$ 天打，如果沒有就是先不管這天要打誰。假設有 $cnt$ 個人確定要在哪天打，在剩下的人中，要選 $k - cnt$ 個人放在第 $k$ 天以前，然後他們在第 $k$ 天會休息，於是就是選 $s_p$ 盡量小的 $k-cnt$ 個，答案是總戰鬥力扣掉他們的戰鬥力。

接下來考慮 $k=t$ 和 $k=t+1$ 時的答案，因為 $i \in [0, t]$ 的部份其實是一樣的，只是多了要做 $i=t+1$，就維護有哪些人確定要在哪天打、再多選一個，然後維護好 $cnt$，再算剩下的最小 $k-cnt$ 個 $s_p$ 總和就好。我維護的方法是用兩個 set。

pC 箭頭謎題

AC / 32 + 20 * 1

有一個長度 $N$ 的 0/1 字串，你每次操作可以選一個位置，把它和它相鄰的字元反轉，也可以選邊邊的，求能不能把這個字串變成全部 0。

有一點 YTP 既視感 (?)，直覺告訴我它是梗題。

$N=1$ 的時候一定可以，$N=2$ 的時候要兩個字元長一樣才可以，接下來就是處理 $N \geq 3$ 的狀況。

我的想法是先找到最右邊的 1，動它左邊那個位置，這樣最右邊的 1 會一直往左移。到最後最左邊的字元可能是 0 或 1，剩下都會是 0，如果最左邊是 0 那就做完了，不然的話還得想辦法把它變 1。

假設現在我們的字串是 $100 \dots 000000$，把最右邊兩個翻轉會變成 $100 \dots 0000\color{blue}{11}$，再翻轉最右邊三個會變 $100 dots 000color{red}{1}color{blue}{00}$，再翻轉 1 和它左邊兩格會變 $100 dots 0color{blue}{11}color{red}{0}color{blue}{00}$，可以發現這個字串可以從右邊開始，分成長度是 2、1、2、……的段落，然後我們可以把某一段變成 1。

$$100 \dots \color{blue}{00}\color{red}{0}\color{blue}{00}\color{red}{0}\color{blue}{00}$$

如果最左邊是長成 $1{\color{blue}00}\dots$，那就把那兩個 0 變成 1，然後三個 1 反轉就結束了。如果是 $1{\color{red}0} \dots$，那就把那個 0 變成 1、最左邊兩個反轉。所有可以發現如果 $(n-1) \bmod 3 = 0$ 或 $2$ 就會有解，剩下 $(n-1) \bmod 3 = 1$ 的狀況經過暴搜可以發現它是無解的。

pD 紗霧與正宗

- / -

有一個長度 $N$ 的陣列，另外你有 $K$ 個數，你可以拿這 $K$ 個數把陣列裡一些元素替換掉（一個數只能換一個），求最大可能的最大連續和。

$N,K \leq 10^6$

前年全國模擬賽就有一題是可替換的最大連續和，有 $O(NK)$ 的 DP 解，但是在這題過不了。

DP 解是先注意到要換的話一定是先換成大的，然後 $dp[i][j]=$ 已經用了 $j$ 個數、第 $i$ 個結尾的最大連續和。我本來 claim $dp[i]$ 有差分單調性，但是馬上被林柏瑄反駁。

我本來以為這題應該是把這個 DP 優化，但官解不是。

pE 計算機結構

- / -

給你一張無向圖，你每次可以選一個簡單環，然後把這個簡單環上的邊都變成一個你想要的顏色，求能不能把這張圖變成指定的樣子。

有想到應該是要倒著做，先找最後的圖有沒有同色的環，然後塗成都可以的顏色，但不知道怎麼維護。

pF 隨機排序

AC / 105 + 0

給你一張有向圖，如果不是 DAG 的話輸出 $-1$，否則求它的拓樸排序數量的倒數，如果答案 $<0.01$ 則輸出 $0$。

答案 $<0.01$ 輸出 $0$ 就代表數量超過 $100$ 就可以停了，那就直接暴搜所有可能的拓樸排序。

我的寫法是用把度數 0 的點拆掉的那種方法找拓樸排序，然後每次都要把 queue 裡的每一個試過一遍，就寫一個遞迴，每次 call function 就拆一個點，先把 queue 裡最前面的那個出來拆，遞迴回來後，再把那個裝回去然後放到最後面。

pG 陣列刪除

AC / 12 + 0

給你一個長度 $N$ 的陣列，每次你可以選兩個相鄰的數刪除，成本是比較小的那個的值，求把整個陣列刪掉的最小成本。$N$ 是偶數。

很顯然只接算最小的 $\frac{N}{2}$ 個的總和就好。

pH 殿壬愛字串

- / -

給你兩個字串 $A$、$B$，你每次可以刪掉 $B$ 裡的一個字元，求把 $B$ 刪到變成 $A$ 的過程中，會出現的字串有幾種不同可能。（長得不一樣才算不同，位置不一樣但長得一樣的不算。）

$\lvert A \rvert \leq 100$、$\lvert B \rvert \leq 10000$

看完題目後我在紙上寫了「$B$ 的 subsequence 裡有 $A$ 是 subsequence」，然後一開始我們以為是位置不一樣就算，立刻想到 $dp[i][j]=$ $B_{1..i}$ 裡有 $A_{1..j}$ 是 subsequence 的 subsequence 數，$j$ 要盡量大，但看清楚後發現是要長得不一樣，我就認為「肯定是怪怪自動機」（其實滿智障的，subsequence 怎麼會是用自動機），然後丟到一邊去了。

賽中因為都沒有人要傳這題，所以我也一直認為一定是某個噁心東西題。

結果這題其實超簡單，如果把題目說成是「$A$ 是 $S$ 的 subsequence、$S$ 是 $B$ 的 subsequence」，那就會變得很顯然了。剛剛那個是對 $B$ DP，會沒辦法分是不是長得不一樣，那就對 $S$ DP 就好了。但因為剛剛那句話裡沒有 $S$，所以我沒有想到可以這樣做。

$dp[i][j]=$ $A_{1..i}$ 是 $S$ 的 subsequence、$S$ 是 $B_{1..j}$ 的 subsequence 的 $S$ 數量，然後 $i$ 要盡量大、$j$ 要盡量小。轉移就直接枚舉後面要接什麼字元，假設是 $c$，然後找 $B_{j+1..\lvert B \rvert}$ 裡最左邊的 $c$ 位置就是新的 $j$，再看 $A_{i+1}$ 是不是 $c$，是的話新的 $i$ 要多 1。

pI 幸福感

AC / 65 + 0，首殺

給你一個序列 $a_1,a_2,\dots,a_N$，令 $f(l,r)=$ 區間 $[l,r]$ 內有多少種不同數字，接下來有 $Q$ 筆詢問，每筆詢問給 $L,R$ 求 $\sum_{L \leq l \leq r \leq R} f(l,r)$。

這種題通常都是掃描線處理詢問右界，然後維護區間左界的貢獻。

我的作法是從最左邊開始枚舉 $R$，然後維護 $c_l= \sum_{l \leq r \leq R} f(l,r)$，也就是詢問右界在 $R$ 時，區間左界在 $l$ 的貢獻。

我讓同一種數字只有最左邊那個有貢獻，所以對於某個數 $a_p$，找它左邊第一個一樣的數，假設在 $lst$，那對於 $i \in (lst, p]$，$c_i$ 都會多上 $R-p+1$，也就是會包含到它的右界數量。$p$ 不會動而 $R$ 會動，那就維護 $-p+1$ 和要算幾個 $R$ 就好。

過程

開場分配是我先打 default code，洪銘德正著看題、林柏瑄倒著看題。本來林柏瑄跟我說他需要括號補全，所以我就先開好括號補全了，但是我打 default code 的時候發現我會一直多打一個括號，所以我還是把括號補全關掉了。

打完後看到有人過了 pG，林柏瑄：是不是取最小 $\frac{n}{2}$ 個就好，我在腦裡快速證明後就快快寫掉了。

接著看到有人過了 pC，我花了一點時間推那些東西，然後還寫個暴搜確定 $(n-1) \bmod 3 = 1$ 而且一開始弄的事情做完後沒變成 0 會無解，但傳的時候忘記檢查了，多吃一個 penalty 還花了一兩分鐘 debug。

到這個時候計分板上只有人過這兩題而已，林柏瑄就丟給我 pI，然後說應該是掃描線，我就想嗯對這種題通常都是掃描線，然後想到去年全國模擬賽社會組也有一題是這樣，對區間裡的區間詢問，我就把那題的作法拿來用，在紙上畫了一下後就幾乎秒解地做完了。

因為是前綴加值區間求和，我就寫線段樹了。因為我最近一直在嘗試比較大眾 (?) 的線段樹寫法，所以我用的不是我習慣的那種，結果一直出 bug，只好再重寫一次我習慣的寫法。有夠浪費時間，還不如 BIT 或直接好好寫。

然後看到有人過 pB，洪銘德：是不是 Greedy 就好，討論了一下細節之後我再把實作細節想清楚，然後就開寫，一發 AC。

另外還有人過的題目是 pF，前面我寫忘了哪題寫到一半的時候，林柏瑄問我怎麼數拓樸排序數量，因為我印象中它不是 P 問題，我就說「我記得這不是一個那麼簡單的問題」。但是看到超過 100 就直接無解，那就直接暴力啊，花了點時間想比較好寫的實作方法後，我就把它寫完了。

這個時候我們是 scoreboard 上唯一 5 題，然後還沒過半場。

接下來我們把剩下的四題都看了一遍，認為 pA 是某種組合數學題、pH 是噁心題、pD 應該是某種怪優化、pE 可能是論文題。然後觀察到一個很有趣的現象，就是計分板下面的隊伍一堆在傳 pD，上面的則是幾乎不傳，我就知道這題一定不簡單，所以放一邊去。

後來 amanorz 過 pA 了，我就很確定這是數學題。本來我們連怎麼檢查一個排列是不是好的都不知道，然後我忽然發現「$i$ 元一定要用 $i-1$ 元找」的性質，再來就是嘗試各種組合的方法，但都做不出來。林柏瑄提出可以放到 young tableau 上，然後我發現就是 young tableau 填數字，我知道有個公式可以算，但我不會，就只好開始暴搜找規律。

找規律完就找到那個很顯然的 DP，有一種剛剛都在浪費時間的感覺 QwQ，然後林柏瑄居然看得出來規律，強死。因為有點像是卡塔蘭數，我說我覺得那個式子會是一堆 $C^n_k$，但想了很久還是沒有想出來。

封板後，看到 amanorz 傳了 pE、ORZCK 傳了 pH，不知道有沒有過。我們把所有時間花在 pA 上，然後就結束了。

總結

5 題，總 penalty 322，rank 2

結果 pH 居然是簡單題，我還一直認為是水題，超氣ㄉ。如果後面花在 pA 的時間都改去投資 pH，我搞不好想得出來，而 pA 官解就是直接 Hook length formula，看起來不是找規律能發現的式子，真的是投資失敗。

我覺得跟去年比起來，我的持久力高了很多，去年我還真的在賽中睡覺，真的是糟糕人。雖然這次一堆人說我賽中在睡覺，但是我沒有在睡啦，我這次真的幾乎從頭到尾都有在做事，大概是今年常常在練 5 個小時 OI 制比賽，所以持久力好了很多，也不會有去年想到腦袋停機的問題。

這次的題目我覺得整體來講比前兩年的決賽都簡單，感覺難度大概是之前的 $\frac{2 \times \text{決賽} + \text{初賽}}{3}$，只是就是計分板詐欺術讓大家都認為 pH 是噁題，沒人要做。

就這樣，(Hardware|MusicGame|HuLan)Master 維持一慣的少 penalty 且虎頭蛇尾 (?) 的風格，在最後一年拿下了還不錯的名次。其實滿可惜的 QQ，如果沒有誤判難度，真的冠軍有望。不過其實也不錯了，至少是附中 2010 年以來最好的成績（2009 第一名是附中欸好強喔）。