2019-team321/C013

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[[Image(sub.png,500px)]]

== 回顾 ==

前期節奏很順，然後一直卡Ｅ和Ｍ題，三個人都不會做，中間消失了３個小時。

== YPL ==

今天的核心問題是比別人少做了兩個籤到題， 原因是自己太菜了。

Ｍ： 已知 n, m, p[0..2**m-1]， 條件是有數組 x[1..n] in [0..2**m-1]， 最大化 y xor a[i] 的下標 i 是 p[y]， 求有多少組 x。
[[BR]]
經驗告訴我， 如果想法卡住了， 多半是因爲第一步的思考方向就出現了偏差。 這時候應該及時地從自己錯誤的想法中提煉有用的東西， 並走出來， 問自己有沒有其他想法。 就像這道題我先思考了 p 的求法， 考慮逐個元素確定， 從高位到低位貪心， 然後去想對於 p[y] 相同的若幹個數， 滿足什麼要求， 發現它們一定在一個連續的區間， 又發現了一些沒有什麼用的小性質， 然後就不會做了。 事實上應該注意到我求了所有的 p， 那麼能不能整體地去考慮求出所有的 p， 然後想一想就做完了。

E： 20 × 20 的矩陣， 求有多少個子矩陣滿足每行單調、 每列單調。
[[BR]]
復雜度太高的東西不要馬上叉掉， 優化是一種可能性。 兩年沒有遇到這種情況， 又沒有這種意識了。 最初 n5 的 DP 可以減少枚舉量優化到 n4， 預處理優化到 n3， 觀察轉移條件發現每條邊只用一次優化到 n2。

回顾

前期節奏很順，然後一直卡Ｅ和Ｍ題，三個人都不會做，中間消失了３個小時。

YPL

今天的核心問題是比別人少做了兩個籤到題， 原因是自己太菜了。

Ｍ： 已知 n, m, p[0..2**m-1]， 條件是有數組 x[1..n] in [0..2**m-1]， 最大化 y xor a[i] 的下標 i 是 p[y]， 求有多少組 x。

經驗告訴我， 如果想法卡住了， 多半是因爲第一步的思考方向就出現了偏差。 這時候應該及時地從自己錯誤的想法中提煉有用的東西， 並走出來， 問自己有沒有其他想法。 就像這道題我先思考了 p 的求法， 考慮逐個元素確定， 從高位到低位貪心， 然後去想對於 p[y] 相同的若幹個數， 滿足什麼要求， 發現它們一定在一個連續的區間， 又發現了一些沒有什麼用的小性質， 然後就不會做了。 事實上應該注意到我求了所有的 p， 那麼能不能整體地去考慮求出所有的 p， 然後想一想就做完了。

E： 20 × 20 的矩陣， 求有多少個子矩陣滿足每行單調、 每列單調。

復雜度太高的東西不要馬上叉掉， 優化是一種可能性。 兩年沒有遇到這種情況， 又沒有這種意識了。 最初 n5 的 DP 可以減少枚舉量優化到 n4， 預處理優化到 n3， 觀察轉移條件發現每條邊只用一次優化到 n2。