Re: leetcode Weekly Contest 421
Q1:
n<=100, 暴力硬做
Q2/Q4:
矩陣乘法練習
令 x 為 a-z 的個數(size: [26,1]) 可以先求出轉移矩陣 A (size: [26,26])
經過一次 transformation 後變為 Ax 為新的 a-z 的個數
則只要用快速冪求出 A^t x 就可以了
Q2可以用 DP 做 O(|s| + t) 的也會過
Q3:
nums[i] <= 200, 所以可以令 DP[x][y] 為 gcd 分別為 x, y 的數量
最後求 DP[1][1] + DP[2][2] + ... + DP[200][200]
吃了一次 TLE 因為覺得 gcd 至少 O(log n) 結果還蠻慢的
改成 preprocess 完所有 gcd(x, y) 就過了
Q3 一開始一直在想要怎麼利用 gcd 想不出來就先去做 Q4
回頭才發現單純用 DP 就行了
唯一用到 gcd 的性質是 gcd(x,y) <= min(x,y) for x,y != 0
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.16.58 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1730002495.A.3F7.html
推
10/27 12:15,
1年前
, 1F
10/27 12:15, 1F
推
10/27 12:35,
1年前
, 2F
10/27 12:35, 2F
推
10/27 12:50,
1年前
, 3F
10/27 12:50, 3F
推
10/27 12:58,
1年前
, 4F
10/27 12:58, 4F
推
10/27 13:00,
1年前
, 5F
10/27 13:00, 5F
推
10/27 13:12,
1年前
, 6F
10/27 13:12, 6F
推
10/27 13:30,
1年前
, 7F
10/27 13:30, 7F
討論串 (同標題文章)
