Re: leetcode Weekly Contest 421

作者: involution (內卷是好文明)   2024-10-27 12:14:50
https://i.imgur.com/Q6LZOOi.png
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

Links booklink

Contact Us: admin [ a t ] ucptt.com