題目列表

3536. 兩個數字的最大乘積
3537. 填充特殊網格
3538. 合并得到最小旅行時間
3539. 魔法序列的數組乘積之和

一、兩個數字的最大乘積

由于數據都是正數，所以乘積最大的兩個數，本質就是找數組中最大的兩個數即可，可以排序后直接找到，也可以通過遍歷找到，代碼如下

// C++
// 遍歷
class Solution {
public:int maxProduct(int n) {int mx1 = 0, mx2 = 0;while(n){int x = n % 10;if(x > mx1) mx2 = mx1, mx1 = x;else if(x > mx2) mx2 = x;n /= 10;}return mx1 * mx2;}
};

# Python
class Solution:def maxProduct(self, n: int) -> int:mx1 = 0mx2 = 0while n:x = n % 10if x > mx1:mx1, mx2 = x, mx1elif x > mx2:mx2 = xn //= 10return mx1 * mx2

二、填充特殊網格

這是個很經典的分治題，根據題目描述，對于一個網格圖，可以將它劃分成四個象限，即四個小網格圖，而對于每一個小網格圖，我們又能劃分成四個象限，很顯然，這是規模更小的子問題，可以用遞歸來解決，代碼如下

// C++
class Solution {
public:vector<vector<int>> specialGrid(int n) {int cnt = 0;vector grid(1 << n, vector<int>(1 << n));auto dfs = [&](this auto&& dfs, int x, int y, int d){ // 根據左上角坐標和邊長就能確定一個網格圖if(d == 1){grid[x][y] = cnt++;return;}int new_d = d / 2;// 按照這樣的順序，網格中的數字從小到大依次增長// 右上象限dfs(x, y + new_d, new_d);// 右下象限dfs(x + new_d, y + new_d, new_d);// 左下象限dfs(x + new_d, y, new_d);// 左上象限dfs(x, y, new_d);};dfs(0, 0, 1 << n);return grid;}
};

# Python
class Solution:def specialGrid(self, n: int) -> List[List[int]]:grid = [[0] * (1 << n) for _ in range(1 << n)]cnt = 0def dfs(x: int, y: int, d: int):if d == 1:nonlocal cntgrid[x][y] = cntcnt += 1returndfs(x, y + d // 2, d // 2)dfs(x + d // 2, y + d // 2, d // 2)dfs(x + d // 2, y, d // 2)dfs(x, y, d // 2)dfs(0, 0, 1 << n)return grid

三、合并得到最小旅行時間

本題可以用選或不選的思想，對于每一個索引 i，我們都可以考慮是否刪除它，如果刪除，則下一段路程的 next_time = time[i] + time[i+1]，同時，我們還需要記錄上一段路程的 pre_time 來計算出當前這段路程需要花費的時間
對于任意一段 position[i] ~ position[i+1] 路程來說，它所需要的時間只和當前索引 i 對應的 time 有關，一旦確定了是否刪除當前索引，就能計算出這段路程需要花費的時間

故我們有如下定義

• $dfs(i,j,pre\_time,cur\_time)$ 表示當前路程 time = cur_time，上一段路程 time = pre_time，剩余可刪除索引為 j 個時，position[i] ~ position[n-1] 時所需的最少時間
  • 如果選擇不刪除當前索引，則 $dfs(i,j,pre\_time,cur\_time)=dfs(i+1,j,cur\_time,time[i+1])+(position[i+1]?position[i])\times cur\_time$
  • 如果選擇刪除當前索引，則 $dfs(i,j,pre\_time,cur\_time)=dfs(i+1,j?1,pre\_time,cur\_time+time[i+1])+(position[i+1]?position[i])\times pre\_time$
  • 上訴兩種情況去 min 返回
• 當 i == n - 1 時，到達終點，返回 0
• 答案返回 $dfs(1,k,time[0],time[1])+(position[1]?position[0])\times time[0]$，因為 i = 0 的索引不能被刪除，可以單獨計算(或者也可以放入 dfs 中寫一個邏輯處理 i = 0 的情況，此時應該返回 $dfs(0,k,0,time[0])$ )

代碼如下

// C++
class Solution {
public:int minTravelTime(int l, int n, int k, vector<int>& position, vector<int>& time) {// 6 | 4 | 7 | 7// 這里用哈希進行記憶化，分別計算出 i、j、pre、cur 所需要的比特位，將他們拼接成 int 當作 key 來使用unordered_map<int,int> memo;auto dfs = [&](this auto&& dfs, int i, int j, int pre, int cur)->int{if(i == n - 1){return j == 0 ? 0 : INT_MAX / 2;}int mask = i << 18 | j << 14 | pre << 7 | cur;if(memo.count(mask)) return memo[mask];int res = dfs(i + 1, j, cur, time[i+1]) + cur * (position[i + 1] - position[i]);if(j){res = min(res, dfs(i + 1, j - 1, pre, cur + time[i+1]) + pre * (position[i + 1] - position[i]));}return memo[mask] = res;};// 將 i = 0 的邏輯放在外面return dfs(1, k, time[0], time[1]) + time[0] * (position[1] - position[0]);}
};class Solution {
public:int minTravelTime(int l, int n, int k, vector<int>& position, vector<int>& time) {// 6 | 4 | 7 | 7unordered_map<int,int> memo;auto dfs = [&](this auto&& dfs, int i, int j, int pre, int cur)->int{if(i == n - 1){return j == 0 ? 0 : INT_MAX / 2;}int mask = i << 18 | j << 14 | pre << 7 | cur;if(memo.count(mask)) return memo[mask];int res = dfs(i + 1, j, cur, time[i+1]) + cur * (position[i + 1] - position[i]);if(j && i){ // 將 i = 0 的邏輯放在里面res = min(res, dfs(i + 1, j - 1, pre, cur + time[i+1]) + pre * (position[i + 1] - position[i]));}return memo[mask] = res;};return dfs(0, k, 0, time[0]);}
};

# Python
class Solution:def minTravelTime(self, l: int, n: int, k: int, position: List[int], time: List[int]) -> int:@cachedef dfs(i: int, j: int, pre: int, cur: int)->int:if i == n - 1:return 0 if j == 0 else infres = dfs(i + 1, j, cur, time[i+1]) + (position[i+1] - position[i]) * curif i and j:res = min(res, dfs(i + 1, j - 1, pre, cur + time[i+1]) + (position[i+1] - position[i]) * pre)return resreturn dfs(0, k, 0, time[0])

四、魔法序列的數組乘積之和

思路：

• 給定一個 seq 序列，如何計算出它對答案的貢獻？

  • 假設給定 seq = [0,0,0,1,1,2,2,2]
  • 根據題目要求，它對答案的貢獻為 $nums[0{]}^3\times nums[1{]}^2\times nums[2{]}^3$
  • 同時，由于 seq 序列的數據順序不同，被認定為不同的序列，根據排列組合，則包含這些元素的 seq 序列對于答案的貢獻為 $\frac{8!}{3!\times 2!\times 3!}\times nums[0{]}^3\times nums[1{]}^2\times nums[2{]}^3=8!\times \frac{nums[0{]}^3}{3!}\times \frac{nums[1{]}^3}{2!}\times \frac{nums[2{]}^3}{3!}$
  • 也就是說，我們可以單獨計算每一個 $\frac{nums[i{]}^c}{c!}$，然后將它們相乘得到答案
  • 故對于 seq 來說，只要我們確定了它標定了幾個 $nums[i]$，就能計算出它的貢獻

• 考慮如何得到序列 seq，使得 popcount(sum(2^seq[i])) == K ?

  • 難點在于，相同二進制位置的 1 相加會產生進位，我們無法只通過一個參數來直接確定還需要多少二進制數位的 1
  • 如果我們直接暴力計算出 s = sum(2^seq[i])，然后在選完所有 seq 序列的數字后，求 popcount(s)，進行判斷，就會爆內存，因為 s 很大
  • 如何做？
    • 性質：只要我們從低到高枚舉二級制數位的 1 進行選擇，就會發現 +Nx2^i 不會影響低位的二進制數位的 1 的數量
    • 所以我們只要關心統計從二進制數位 i 開始往后的高位上的二級制數即可，這樣我們記錄的 s 的個數就會大大減小，具體見代碼

代碼如下

// C++
constexpr int MOD = 1e9 + 7;
constexpr int MX = 31;
long long POW(long long x, long long y){long long res = 1;while(y){if(y & 1) res = res * x % MOD;x = x * x % MOD;y >>= 1;}return res;
}
vector<long long> F(MX), INV_F(MX);
int init = []{F[0] = 1;for(int i = 1; i < MX; i++){F[i] = F[i - 1] * i % MOD;}// 計算逆元INV_F.back() = POW(F.back(), MOD - 2);for(int i = MX - 1; i > 0; i--){INV_F[i - 1] = INV_F[i] * i % MOD;}return 0;
}();
class Solution {
public:int magicalSum(int m, int K, vector<int>& nums) {int n = nums.size();vector pow_(n, vector<int>(m + 1));for(int i = 0; i < n; i++){pow_[i][0] = 1;for(int j = 1; j <= m; j++){pow_[i][j] = 1LL * pow_[i][j-1] * nums[i] % MOD;}}vector memo(n, vector(m+1, vector(K+1, vector<int>(m/2+1, -1))));// i : 從低到高枚舉二進制數位// j : 剩余要選的 seq 的元素個數// k : 剩余要得到的二進制 1 的個數// s : sum(2^seq[0...i])>>iauto dfs = [&](this auto&& dfs, int i, int j, int k, int s)->int{int c1 = popcount((unsigned) s);if(c1 + j < k){return 0;}if(i == n || j == 0 || k == 0){return j == 0 && c1 == k;}if(memo[i][j][k][s] != -1) return memo[i][j][k][s];int res = 0;for(int c = 0; c <= j; c++){res = (res + 1LL * dfs(i + 1, j - c, k - ((s + c) & 1), s + c >> 1) * pow_[i][c] % MOD * INV_F[c] % MOD) % MOD;}return memo[i][j][k][s] = res;};return F[m] * dfs(0, m, K, 0) % MOD;}
};