推 oin1104: 幹 我哭了 你怎麼這麼強 09/01 12:03
推 sustainer123: 大師 我第三題直接死去 我以為要dp 09/01 12:04
推 DJYOMIYAHINA: 第三題我知道要這樣 但我寫不出來 唉== 09/01 12:06
推 Furina: 大師 09/01 12:08
推 dont: 大師 09/01 14:34
還行
https://i.imgur.com/aPpvWJd.png
Q1:
等價於xy相加的奇偶是否一致
可以直接用字符的奇偶來做
Q2:
維護一個大小為 k 的 max heap
Q3:
第一感 從大的開始挑 如果全場只有某一行有最大的值 那顯然可以無腦挑
如果不能呢 那就遞迴下去每個有最大值的行都試一遍
決定能不能挑的狀態受: 1) 哪些行被挑過 2) 最後挑了誰 來決定
因為行數 <= 10 且值 <= 100, 狀態總共有 2^10 * 100 ~= 10^5
用 memorization 就可以了
我一開始 TLE 還在想是不是遞迴常數太大要優化一下
吃了兩次之後才發現是我 memorization 最後一步沒有存進去 = =
早知道用 python 無腦 lru_cache
Q4:
看到 n <= 2000, 代表 O(n^2) 應該扛的住
直接求出 n^2 個解再拿去 query 也可以
令 X[a][b] 是 a..b 的 XOR SCORE
根據定義 有 X[a][b] = X[a][b-1] ^ X[a+1][b]
所以可以 O(n^2) 求出 X[]
我們要求的是 subarray 裡 XOR SCORE 最大的
因此有 Ans[a][b] = max(Ans[a+1][b], X[a][a], X[a][a+1], ..., X[a][b])
我們可以花 O(n^2) 先求出所有 Y[a][b] := max(X[a][a], ..., X[a][b])
就能再花 O(n^2) 求出 Ans[]
感覺有點繞 不知道有沒有更好的做法
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.32.24 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1725163214.A.FB3.html