0%

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 第一名是附中欸好強喔)。