NPSC 2021

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

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

計分板·官解

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

題目

pA 殿壬的飲料王國

WA / -

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

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

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

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

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

所以現在問題變成：有每一列長度是 和 的 young tableau，有幾種方式在裡面填數字，使得每一個格子裡的數字都比它上面和右邊的大。

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

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

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

pB 小 P 打仗

AC / 88 + 0

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

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

接下來考慮 和 時的答案，因為 的部份其實是一樣的，只是多了要做 ，就維護有哪些人確定要在哪天打、再多選一個，然後維護好 ，再算剩下的最小 個 總和就好。我維護的方法是用兩個 set。

pC 箭頭謎題

AC / 32 + 20 * 1

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

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

的時候一定可以， 的時候要兩個字元長一樣才可以，接下來就是處理 的狀況。

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

假設現在我們的字串是 ，把最右邊兩個翻轉會變成 ，再翻轉最右邊三個會變 ，再翻轉 1 和它左邊兩格會變 ，可以發現這個字串可以從右邊開始，分成長度是 2、1、2、……的段落，然後我們可以把某一段變成 1。

如果最左邊是長成 ，那就把那兩個 0 變成 1，然後三個 1 反轉就結束了。如果是 ，那就把那個 0 變成 1、最左邊兩個反轉。所有可以發現如果 或 就會有解，剩下 的狀況經過暴搜可以發現它是無解的。

pD 紗霧與正宗

- / -

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

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

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

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

pE 計算機結構

- / -

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

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

pF 隨機排序

AC / 105 + 0

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

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

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

pG 陣列刪除

AC / 12 + 0

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

很顯然只接算最小的 個的總和就好。

pH 殿壬愛字串

- / -

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

、

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

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

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

是 的 subsequence、 是 的 subsequence 的 數量，然後 要盡量大、 要盡量小。轉移就直接枚舉後面要接什麼字元，假設是 ，然後找 裡最左邊的 位置就是新的 ，再看 是不是 ，是的話新的 要多 1。

pI 幸福感

AC / 65 + 0，首殺

給你一個序列 ，令 區間 內有多少種不同數字，接下來有 筆詢問，每筆詢問給 求 。

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

我的作法是從最左邊開始枚舉 ，然後維護 ，也就是詢問右界在 時，區間左界在 的貢獻。

我讓同一種數字只有最左邊那個有貢獻，所以對於某個數 ，找它左邊第一個一樣的數，假設在 ，那對於 ， 都會多上 ，也就是會包含到它的右界數量。 不會動而 會動，那就維護 和要算幾個 就好。

過程

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

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

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

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

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

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

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

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

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

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

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

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

總結

5 題，總 penalty 322，rank 2

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

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

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

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