Posted on | In ,

Fliptile

Solution sketch

這題有個非常重要的想法:

$$對於第一列的所有翻法進行窮舉，之後第二列開始就直接依照前一列的狀態直接進行 flip 操作即可！$$

如果，一路 flip 到最後一列，然而最後一列卻不是全 0 就代表著第一列翻法不成立。反之，該第一列的翻法是 ok 的。

輸出的部分，因為我們是按照字典順序枚舉翻法了，所以其實只要看 flip 局面的 1 的總數來更新答案即可。

Read more »

Posted on | In ,

Face The Right Way

Solution sketch

對於所有的 $K$ 進行 枚舉 和 模擬反轉操作 的話，會是 $O(n^3)$ 所以會 TLE。

其實，一個點反轉兩次等於沒反轉。因此一個點有無被反轉，只需要看他前 $k - 1$ 的區間內反轉次數是奇數還數偶數就好。

因此，我們只要維護區間反轉次數，就可以壓到 $O(n^2)$ 了！

Read more »

Posted on | In ,

Subsequence

Abridged problem statement

給定一個數列，求取最小的連續數字區間，其總和 $\geq s$。

Solution sketch

利用二分搜的話，邊界要小心設定呀！ WA 兩次 都只是因為邊界選錯而已…

爬行法的話，實作基本上大原則就是右跑左追。

Read more »