Re: [閒聊] LeetCode Weekly Contest 413
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
推
09/01 12:03,
1年前
, 1F
09/01 12:03, 1F
推
09/01 12:04,
1年前
, 2F
09/01 12:04, 2F
推
09/01 12:06,
1年前
, 3F
09/01 12:06, 3F
推
09/01 12:08,
1年前
, 4F
09/01 12:08, 4F
推
09/01 14:34,
1年前
, 5F
09/01 14:34, 5F
討論串 (同標題文章)
完整討論串 (本文為第 1 之 7 篇)：
