題目列表

3522. 執行指令后的得分
3523. 非遞減數組的最大長度
3524. 求出數組的 X 值 I
3525. 求出數組的 X 值 II

一、執行指令后的得分

照著題目要求進行模擬即可，代碼如下

// C++
class Solution {
public:long long calculateScore(vector<string>& instructions, vector<int>& values) {long long ans = 0;int n = values.size();vector<bool> vis(n);for(int i = 0; i >= 0 && i < n;){if(vis[i]) break;vis[i] = true;if(instructions[i][0] == 'a'){ans += values[i++];}else{i = i + values[i];}}return ans;}
};

# Python
class Solution:def calculateScore(self, instructions: List[str], values: List[int]) -> int:n = len(values)i = 0ans = 0vis = [False] * nwhile 0 <= i < n:if vis[i]:breakvis[i] = Trueif instructions[i][0] == 'a':ans += values[i]i += 1else:i += values[i]return ans

二、非遞減數組的最大長度

根據題目的操作方式，我們會得到以下性質：

• 最大的元素一定會被保留
• 最大的元素后面的元素一定會被刪除
• 去掉最大元素，我們考慮剩下元素，依舊有上訴的性質
• 如此循環，直到沒有元素可以選擇

在上述過程中找最大值的操作需要 O(n) 的時間，會超時，但其實，如果我們逆著看思考過程，就會發現找最大值的操作就是在找前綴最大值，判斷一個元素是否能保留，就是看他是否是前綴最大值，代碼如下

// C++
class Solution {
public:int maximumPossibleSize(vector<int>& nums) {int ans = 0, mx = 0;for(int x : nums){mx = max(mx, x);if(x == mx)ans++;}return ans;}
};

# Python
class Solution:def maximumPossibleSize(self, nums: List[int]) -> int:mx = 0ans = 0for x in nums:mx = max(mx, x)if x == mx:ans += 1return ans

三、求出數組的 X 值 I

對于這類子數組問題，我們可以用 53. 最大子數組和 的動態規劃想法來思考

• 設 $f[i][j]$ 表示以 $i$ 為右端點的乘積除以 $k$ 后余數為 $j$ 的子數組的個數
• 如果和以 $i?1$ 為右端點的子數組連起來，則 $f[i][(j?x)\%k]+$$=f[i?1][j]$，其中 $x=nums[i]、j\in [0,k)$
• 如果 $i$ 單獨作為一個子數組，則 $f[i][x\%k]+$$=1$

代碼如下

// C++
class Solution {
public:vector<long long> resultArray(vector<int>& nums, int k) {int n = nums.size();vector f(n + 1, vector<long long>(k));vector<long long> res(k);for(int i = 0; i < n; i++){int x = nums[i] % k;for(int j = 0; j < k; j++){f[i+1][j*x%k] += f[i][j];}f[i+1][x % k]++;for(int j = 0; j < k; j++){res[j] += f[i+1][j];}}return res;}
};// 空間優化
class Solution {
public:vector<long long> resultArray(vector<int>& nums, int k) {int n = nums.size();vector<long long> f(k);vector<long long> res(k);for(int i = 0; i < n; i++){int x = nums[i] % k;vector<long long> tmp(k);for(int j = 0; j < k; j++){tmp[j*x%k] += f[j];}tmp[x % k]++;f = tmp;for(int j = 0; j < k; j++){res[j] += f[j];}}return res;}
};

# Python
class Solution:def resultArray(self, nums: List[int], k: int) -> List[int]:res = [0] * kf = [0] * kfor num in nums:m = num % ktmp = [0] * ktmp[m] += 1for x in range(k): tmp[(x * m) % k] += f[x]f = tmpfor x in range(k):res[x] += f[x]return res

四、求出數組的 X 值 II

(注意：本題的題面和上一題不一樣，請仔細閱讀)

通過題目，我們不難看出查詢的幾個經典特征：單點修改+區間查詢，很容易想到用 線段樹 來維護，關鍵是如何進行維護，或者說線段樹的結點應該保留哪些值？

• mul表示整個區間的乘積 %k 后的值，為了方便后面計算

• array<int,5>res，res[i] 表示 [l,r]中以 l 為左端點的元素乘積 %k = i 的子數組個數，這里直接開 5 個 int 是因為 k 最大為 5

• 合并區間時

  • cur.mul = left.mul * right.mul % k
  • cur.res = left.res && cur.res[left.mul * i % k] += right.res[i]，因為都要以 l 為左端點

// C++
struct Node{long long mul;array<int, 5> res;
};
class SegTree{    
public:SegTree(int n, int K):t(n << 2), k(K){}void maintain(int o){t[o].mul = (t[o<<1].mul * t[o<<1|1].mul) % k;t[o].res = t[o<<1].res;for(int i = 0; i < k; i++){t[o].res[t[o<<1].mul * i % k] += t[o<<1|1].res[i];}}void build(int o, int l, int r, const vector<int> & a){if(l == r){t[o].mul = a[l] % k;t[o].res[a[l] % k] = 1;return;}int mid = l + (r - l) / 2;build(o << 1, l, mid, a);build(o << 1 | 1, mid + 1, r, a);maintain(o);}void update(int o, int l, int r, int i, int val){if(l == r){t[o].mul = val % k;for(int i = 0; i < k; i++)t[o].res[i] = 0;t[o].res[val % k] = 1;return;}int mid = l + (r - l) / 2;if(i <= mid) update(o << 1, l, mid, i, val);else update(o << 1 | 1, mid + 1, r, i, val);maintain(o);}Node query(int o, int l, int r, int L, int R){if(L <= l && r <= R){return t[o];}int mid = l + (r - l) / 2;if(L <= mid){auto left = query(o << 1, l, mid, L, R);if(mid < R){auto right = query(o << 1 | 1, mid + 1, r, L, R);Node ret;ret.mul = left.mul * right.mul % k;ret.res = left.res;for(int i = 0; i < k; i++){ret.res[left.mul*i % k] += right.res[i];}return ret;}return left;}return query(o << 1 | 1, mid + 1, r, L, R);}
private:vector<Node> t;int k;
};
class Solution {
public:vector<int> resultArray(vector<int>& nums, int k, vector<vector<int>>& queries) {int n = nums.size();SegTree t(n, k);t.build(1, 0, n - 1, nums);vector<int> res;for(auto& q : queries){t.update(1, 0, n - 1, q[0], q[1]);res.push_back(t.query(1, 0, n - 1, q[2], n - 1).res[q[3]]);}return res;}
};