題目列表
3566. 等積子集的劃分方案
3567. 子矩陣的最小絕對差
3568. 清理教室的最少移動
3569. 分割數組后不同質數的最大數目
一、等積子集的劃分方案
由于本題的數據范圍不大，我們可以暴力枚舉所有可能的劃分方式，代碼如下
// C++
class Solution {
public:bool checkEqualPartitions(vector<int>& nums, long long target) {int n = nums.size();// 用二進制位的 0/1 對 nums 進行劃分for(int i = 1; i < (1 << n) - 1; i++){long long mul[2] = {1, 1};for(int j = 0; j < n; j++){mul[i >> j & 1] *= nums[j];if(mul[i >> j & 1] > target){ // 在計算的過程中進行數值判斷，防止數據超范圍break;}}if(mul[0] == target && mul[1] == target){return true;}}return false;}
};
# Python
class Solution:def checkEqualPartitions(self, nums: List[int], target: int) -> bool:n = len(nums)for i in range(1, 1 << n):mul = [1, 1]for j in range(n):mul[i >> j & 1] *= nums[j]if mul[i >> j & 1] > target:breakif mul[0] == target and mul[1] == target:return Truereturn False
二、子矩陣的最小絕對差
由于數據范圍不大，直接暴力模擬即可，代碼如下
// C++
class Solution {
public:vector<vector<int>> minAbsDiff(vector<vector<int>>& grid, int k) {int n = grid.size(), m = grid[0].size();auto oneMinAbsDiff = [&](int x, int y)->int{set<int> st;for(int i = 0; i < k; i++){for(int j = 0; j < k; j++){st.insert(grid[x + i][y + j]);}}if(st.size() == 1) return 0;int ret = INT_MAX;for(auto it = ++st.begin(); it != st.end(); ++it){ret = min(ret, *it - *prev(it));}return ret;};vector ans(n - k + 1, vector<int>(m - k + 1));for(int i = 0; i <= n - k; i++){for(int j = 0; j <= m - k; j++){ans[i][j] = oneMinAbsDiff(i, j);}}return ans;}
};
# Python
class Solution:def minAbsDiff(self, grid: List[List[int]], k: int) -> List[List[int]]:n, m = len(grid), len(grid[0])ans = [[0] * (m - k + 1) for _ in range(n - k + 1)]for i in range(n - k + 1):rows = grid[i:i+k]for j in range(m - k + 1):a = []for row in rows:a.extend(row[j:j + k])a.sort()mn = inffor x, y in pairwise(a):if y > x:mn = min(mn, y - x)if mn < inf:ans[i][j] = mnreturn ans
三、清理教室的最少移動
求最短路徑問題一般考慮 bfs、dfs 或者更高級的圖的相關算法，本題用 bfs 就可以，但是我們一般寫 bfs 只考慮走的步數，更復雜一些的會有障礙物，需要判斷哪些結點不能走，為了防止結點重復走，還需要有一個 vis數組 標記走過的結點
本題的難點在于學生移動需要有能量，而某些結點能恢復能量，同時，對垃圾的收集的順序不同，也會導致不同的步數，所以對于一個網格是否被標記為遍歷過，還需要有額外的參數進行判斷。
-
如何設計
vis數組的參數？- 基本參數，當前網格的位置信息
(x,y) - 走到當前網格所剩的能量
energy - 剩余還有哪些垃圾需要被處理，本參數記為
mask由二進制進行表示，需要先對垃圾進行編號0~n，然后將其映射到二進制的每一位 - 故有
vis[x][y][energy][mask] 表示到達網格 (x,y) 所剩余的能量為energy，剩余未被收集的垃圾為mask的結點狀態是否被遍歷過 - 時間復雜度為
vis的狀態個數O(n*m*energy*2^k)，其中k為垃圾的個數
- 基本參數，當前網格的位置信息
代碼如下
// C++
class Solution {static constexpr int dirs[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
public:int minMoves(vector<string>& classroom, int energy) {int n = classroom.size(), m = classroom[0].size();map<pair<int,int>, int> mp;int start_x = 0, start_y = 0;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(classroom[i][j] == 'S'){start_x = i, start_y = j;}else if(classroom[i][j] == 'L'){mp[{i, j}] = mp.size();}}}vector vis(n, vector(m, vector(energy + 1, vector<bool>(1 << mp.size()))));int step = 0;queue<tuple<int,int,int,int>> q;q.emplace(start_x, start_y, energy, (1 << mp.size()) - 1);vis[start_x][start_y][energy][(1 << mp.size()) - 1] = true;while(q.size()){int sz = q.size();while(sz--){auto [x, y, e, mask] = q.front(); q.pop();if(mask == 0){ // 垃圾全部收集完return step;}for(int i = 0; i < 4; i++){int nx = x + dirs[i][0], ny = y + dirs[i][1];if(nx < 0 || nx >= n || ny < 0 || ny >= m || classroom[nx][ny] == 'X' || e == 0) // 如果越界、是障礙物、沒有能量，則不能走continue;int new_e = classroom[nx][ny] == 'R' ? energy : e - 1;int new_mask = classroom[nx][ny] == 'L' ? (mask & ~(1 << mp[{nx, ny}])) : mask;if(!vis[nx][ny][new_e][new_mask]){q.emplace(nx, ny, new_e, new_mask);vis[nx][ny][new_e][new_mask] = true;}}}step++;}return -1;}
};
四、分割數組后不同質數的最大數目
將 nums 數組分為前綴 A 和 后綴 B，求 max(A中不同質數個數 + B中不同質數個數)，該問題可以轉換成 nums 中不同質數個數 + 哪些質數能被計算兩次。
-
nums中不同質數的個數，我們可以直接用哈希表計算處理- 前置問題：如何快速判斷一個數字是否是質數，我們可以用埃氏篩進行預處理，具體見代碼
-
哪些質數能被計算兩遍？對于一個質數
x，我們只需要知道它出現的最左下標l和最右下標r，只要k 在 (l,r] 中，那么x對答案的貢獻就能+1，而這就是區間 +1 操作，然后我們只要找出區間的+1次數最多的位置即可，即維護區間最大值-
區間+1和維護區間最大值，可以用線段樹來維護 -
同時，由于會不斷的跟新數組中的數組，質數的下標位置信息也會變化，故我們需要用
set維護質數的下標信息- 在通過質數下標數據對線段樹進行跟新時，為了簡化跟新判斷邏輯，我們可以先對原本的操作進行撤銷，然后再進行跟新操作即可
-
代碼如下
//C++
#include <ranges>
const int MX = 1e5 + 5;
vector<bool> is_prime(MX, true);
int init = []{ // 預處理出所有的質數is_prime[0] = is_prime[1] = false;for(int i = 2; i < MX; i++){if(is_prime[i]){for(int j = 2*i; j < MX; j += i){is_prime[j] = false;}}}return 0;
}();
// 要求 質數的數量之和最大
// 轉換成 總的不同質數個數 + 哪些質數能被計算兩遍
// 對于任意一個質數來說，只要劃分區間的點 k 在 (left, right] 之間，答案就能 +1
//=> 區間+1/-1問題 + 求區間最值問題，可以用 線段樹 來維護
class SegTree{
public:SegTree(int n):t(n<<2), todo(n<<2){}SegTree(const vector<int>& a){int n = a.size();t.resize(n << 2);todo.resize(n << 2);build(a, 1, 0, n - 1);}void maintain(int o){t[o] = max(t[o << 1], t[o << 1 | 1]);}void build(const vector<int>& a, int o, int l, int r){if(l == r){t[o] = a[l];return;}int m = l + (r - l)/2;build(a, o << 1, l, m);build(a, o << 1 | 1, m + 1, r);maintain(o);}void do_(int o, int l, int r, int add){todo[o] += add;t[o] += add;}void down(int o, int l, int r){if(todo[o]){ // 判斷是否有需要跟新的數據沒有下放給子節點int m = l + (r - l)/2;do_(o << 1, l, m, todo[o]);do_(o << 1|1, m + 1, r, todo[o]);todo[o] = 0;}}void update(int o, int l, int r, int L, int R, int add){if(L <= l && r <= R){ // 到達該結點時，子節點的數據可以暫且不用更新，數據保存在 todo 數組中即可（懶更新）do_(o, l, r, add);return;}down(o, l, r); // 將 懶處理的數據 下發到子節點int m = l + (r - l)/2;if(m >= L) update(o << 1, l, m, L, R, add);if(m < R) update(o << 1|1, m + 1, r, L, R, add);maintain(o);}int query(){ // 由于本題只要求整個區間的最大值，所以直接返回根節點即可return t[1];}private:vector<int> t, todo;
};class Solution {
public:vector<int> maximumCount(vector<int>& nums, vector<vector<int>>& qs) {unordered_map<int,set<int>> pos;int n = nums.size();for(auto&& [idx, val] : nums | ranges::views::enumerate){ // 同時遍歷下標和元素if(is_prime[val]){pos[val].insert(idx);}}SegTree t(n);for(auto [_, st] : pos){if(st.size() > 1){t.update(1, 0, n - 1, *st.begin() + 1, *st.rbegin(), 1);}}vector<int> ans(qs.size());for(auto&& [i, q] : qs | ranges::views::enumerate){ // 同時遍歷下標和元素int j = q[0], val = q[1];if(is_prime[nums[j]]){auto & st = pos[nums[j]];if(st.size() > 1){ // 撤銷原本的區間 +1 操作t.update(1, 0, n - 1, *st.begin() + 1, *st.rbegin(), -1);}st.erase(j);if(st.size() > 1){ // 跟新現在的區間 +1 操作t.update(1, 0, n - 1, *st.begin() + 1, *st.rbegin(), 1);}if(st.empty()){ // 維護 總的不同質數個數pos.erase(nums[j]);}}if(is_prime[val]){auto& st = pos[val];if(st.size() > 1){ // 撤銷原本的區間 +1 操作t.update(1, 0, n - 1, *st.begin() + 1, *st.rbegin(), -1);}st.insert(j);if(st.size() > 1){ // 跟新現在的區間 +1 操作t.update(1, 0, n - 1, *st.begin() + 1, *st.rbegin(), 1);}nums[j] = val; // 注意跟新數組數據}ans[i] = t.query() + pos.size(); // 答案為 能被計算兩次的質數 + 總的不同質數個數}return ans;}
};
——彈性伸縮)
