Fliptile
Solution sketch
這題有個非常重要的想法:
$$對於第一列的所有翻法進行窮舉,之後第二列開始就直接依照前一列的狀態直接進行 flip 操作即可!$$
如果,一路 flip 到最後一列,然而最後一列卻不是全 0 就代表著第一列翻法不成立。反之,該第一列的翻法是 ok 的。
輸出的部分,因為我們是按照字典順序枚舉翻法了,所以其實只要看 flip 局面的 1 的總數來更新答案即可。
Never give up!
這題有個非常重要的想法:
$$對於第一列的所有翻法進行窮舉,之後第二列開始就直接依照前一列的狀態直接進行 flip 操作即可!$$
如果,一路 flip 到最後一列,然而最後一列卻不是全 0 就代表著第一列翻法不成立。反之,該第一列的翻法是 ok 的。
輸出的部分,因為我們是按照字典順序枚舉翻法了,所以其實只要看 flip 局面的 1 的總數來更新答案即可。
對於所有的 $K$ 進行 枚舉 和 模擬反轉操作 的話,會是 $O(n^3)$ 所以會 TLE。
其實,一個點反轉兩次等於沒反轉。因此一個點有無被反轉,只需要看他前 $k - 1$ 的區間內反轉次數是奇數還數偶數就好。
因此,我們只要維護區間反轉次數,就可以壓到 $O(n^2)$ 了!
給定一個數列,求取最小的連續數字區間,其總和 $\geq s$。
利用二分搜的話,邊界要小心設定呀! WA 兩次 都只是因為邊界選錯而已…
爬行法的話,實作基本上大原則就是右跑左追。
A 不錯的數學題,但是不需要推公式就可做了… :)
B 不錯的思考題,但是實作QAQ
Random notes…
給定書名與作者 與 借還書歷史。在看到 SHELVE
時印出需要被上架的書籍的一些資訊。
就模擬吧! 很煩的那種…