2025 TOI初選題解 pB (還沒打完)

因為 pA 跟 pC 都沒啥好講的後面的我也不會
就來打一下這個特別煩的 pB
題序如下：

有個人
他在煎鬆餅
他煎了 n 種大小的鬆餅
每種 m 個 但因為他要噁心人
所以他在桌上放了 n 堆 每堆 m 個
每種鬆餅按照大小被編號 1~n 每種各有 m 個
但完全沒有照順序排
現在桌上只剩下一個空位 也就是說你有 n+1 堆
而最後一堆是空的 其他都有 m 個隨機的東西
然後你現在可以進行不超過 9nm 次操作
每次你可以鏟起某一堆 k 個鬆餅 並把它放到另外一堆上
每次鏟起的鬆餅數量不得超過該堆目前有的鬆餅數量
你希望在進行若干次操作後能把所有編號為1的m個鬆餅放到第1堆上 編號為2放到第二堆 以此類推
注意操作過程中不得有任何一堆的鬆餅數量超過 m 
否則將僅得該組測試資料 30% 分數

constraints:
1 <= n, m <= 50

subtask 1: m=1
subtask 2: n=2
subtask 3: 無其他限制

噁心實作題要寫的乾淨是蠻重要的一個部分
題目中有提到對於每次操作要輸出三個整數 i, k, j 代表把第 i 行的 k 個煎餅放到第 j 行上
所以我們直接火爆寫一個lambda處理這個問題這樣之後所有的操作都可以當作黑盒子完成
coding complexity大減

vector<array<int, 3>> ans;
vector<vector<int>> pancakes(n, vector<int>(m));
vector<int> sz(n); //現在每堆有幾個
auto mv = [](int i, int k, int j){
   int si=sz[i], sj=sz[j];
    for(int l=1; l<=k; l++){
        pancakes[j][sj+l]=pancakes[i][si-k+l];
        pancakes[i][si-k+l]=0;
    }
    sz[i]-=k;
    sz[j]+=k;
    ans.push_back({i, k, j});
};

這題處理的方式有個比較重要的點既然是要照順序處理
那在處理完每次行動後都要把狀態恢復
這樣才能在之後的行動都套用同樣的方法而不用特判

partial AC 30 %

先講 30% 的部分分
反正一疊可以放無限多的東西
就把所有東西丟到最後面
然後一個一個放回去該放的地方就好了
總操作次數 nm+n

Subtask 1

然後是 m=1
既然每種東西只有一個
所以我們要做一個額外空間為一的sort
然後東西很小所以 n^2 就好
大致流程是
從頭開始處理如果現在上面的東西不該在這裡就把他搬到額外空間上
然後再遍歷一次把該放過來的東西放上去
最後把額外空間的東西放到那格上
就恢復初始狀態了

Subtask 2

接下來是n=2
這邊先講一個重要的點
我們可以很簡單的發現
可以在兩次行動中把一排中的其中一個搬到另外一個空行上
假設要把第 i 行的第 k 個(由上往下)搬到第 j 行的時候

mv(i, k, j);
mv(j, k-1, i);

這樣那個東西就會被留在那裏了
注意這個時候如果第j行有東西有可能會讓整個炸掉
所以我們要保證操作時第 i 行加第 j 行的東西不會超過 m 個
這時候我們可以想到一個方法就是把第二行中所有的1搬到第三行
然後把第一行的 2 放到第二行 1 放到第三行
這樣我們可以得到一整排的 2 跟一整排的 1
最後把第三行搬回來就好了

Subtask 3

最後是最麻煩的無其他限制
整個題目的核心在於均攤
怎麼在有限的次數內排好一排並恢復成 n 排 m 個並有一個空行呢
根據剛剛上面的想法與其花兩次把一個東西搬到新的一行
不如花三次把一個東西搬到這一行的最上面!

mv(i, k, j);
mv(j, k-1, i);
mv(j, 1, i);

這樣第 k 個東西就會在這一排的最上面了
注意此時第j行最好要是空的
反覆這樣做的話你可以把一個特定大小的鬆餅全部放在這排的頂端
那我們對所有行做這件事
假設我們現在處理的是1 那所有的1 都被放在頂端
那接下來就很簡單了
我們可以把它全部搬到一個空行
這樣就會有一整疊的1了

2025 TOI初選題解 pB (還沒打完)

author: cjtsai.toi

partial AC 30 %

Subtask 1

Subtask 2

Subtask 3