1.?按策略買賣股票的最佳時機

給你兩個整數數組 prices 和 strategy，其中：

prices[i] 表示第 i 天某股票的價格。
strategy[i] 表示第 i 天的交易策略，其中：
-1 表示買入一單位股票。
0 表示持有股票。
1 表示賣出一單位股票。
同時給你一個 偶數 整數 k，你可以對 strategy 進行 最多一次 修改。一次修改包括：

選擇 strategy 中恰好 k 個 連續 元素。
將前 k / 2 個元素設為 0（持有）。
將后 k / 2 個元素設為 1（賣出）。
利潤 定義為所有天數中 strategy[i] * prices[i] 的 總和 。

返回你可以獲得的 最大 可能利潤。

注意： 沒有預算或股票持有數量的限制，因此所有買入和賣出操作均可行，無需考慮過去的操作。

解題思路：容易想到滑窗的思路, 通過計算增量, 結果就是原來的乘積+增量, 先計算第一個窗口, 對于數組strategy, 前k/2個數變成0, 增量為-strategy[I]*prices[i],? 后k/2變成1, 增量為prices[i]*1-strategy[I]*prices[i], 向右滑動的過程中, 下標為i-k/2的數會從1變成0, 若變化后增量全是負值, 此時保持原值更優, 也就是增量和0取最大值

using ll = long long;
class Solution {
public:long long maxProfit(vector<int>& prices, vector<int>& strategy, int k) {ll tot = 0, sum = 0;for (int i = 0; i < k / 2; i++) {int p = prices[i], s = strategy[i];tot += p * s;sum -= p * s;}for (int i = k / 2; i < k; i++) {int p = prices[i], s = strategy[i];tot += p * s;sum += p * (1 - s);}ll max_sum = max(sum, 0LL);for (int i = k; i < prices.size(); i++) {int p = prices[i], s = strategy[i];tot += p * s;sum += p * (1 - s) - prices[i - k / 2] +prices[i - k] * strategy[i - k];max_sum = max(max_sum, sum);}return max_sum + tot;}
};
// [i,i+k/2-1]/[i-k,i-k/2-1] - 前k/2
// [i-k/2,i-1]

?2.?區間乘法查詢后的異或 I

給你一個長度為 n 的整數數組 nums 和一個大小為 q 的二維整數數組 queries，其中 queries[i] = [li, ri, ki, vi]。

對于每個查詢，按以下步驟執行操作：

設定 idx = li。
當 idx <= ri 時：
更新：nums[idx] = (nums[idx] * vi) % (109 + 7)
將 idx += ki。
在處理完所有查詢后，返回數組 nums 中所有元素的 按位異或 結果。

解題思路：

0 <= li <= ri < n
1 <= q == queries.length <= 10^3

n*q的時間復雜度, 直接按題意模擬即可

const int MOD = 1e9 + 7;
using ll = long long;
class Solution {
public:int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {vector<ll> nums_;for (int i = 0; i < nums.size(); i++)nums_.push_back(nums[i]);for (int i = 0; i < queries.size(); i++) {int x = queries[i][0], y = queries[i][1], z = queries[i][2],e = queries[i][3];for (int j = x; j <= y; j += z) {nums_[j] = (nums_[j] * e) % MOD;}}ll ans = 0;for (int i = 0; i < nums_.size(); i++) {ans = ans ^ nums_[i];}return ans;}
};

3.?刪除可整除和后的最小數組和

給你一個整數數組 nums 和一個整數 k。

你可以 多次 選擇 連續 子數組 nums，其元素和可以被 k 整除，并將其刪除；每次刪除后，剩余元素會填補空缺。
返回在執行任意次數此類刪除操作后，nums 的最小可能 和。

解題思路：DP，每次刪除的元素和都是k的倍數, 對于數組的最后一個元素nums[n-1], 刪除的話, 尋找當前待刪子數組的左端點i, 下標i...n-1是k的倍數,?刪除子數組 [i,n?1] 后，問題變成前綴 [0,i?1] 的最小和, 可能有多個滿足條件的左端點i, 題中求刪除后nums的最小可能和, 因此刪除和最大的子數組和, 保留剩下最小的數組和。狀態轉移時, 不刪就是f+x, 刪的話, 變為剩余前綴的最小值

using ll = long long;
class Solution {
public:long long minArraySum(vector<int>& nums, int k) {vector<ll> a(k, LLONG_MAX);a[0] = 0;ll f = 0;int s = 0;for (int i = 0; i < nums.size(); i++) {s = (s + nums[i]) % k;f = min(f + nums[i], a[s]);a[s] = f;}return f;}
};

4.?區間乘法查詢后的異或 II

給你一個長度為 n 的整數數組 nums 和一個大小為 q 的二維整數數組 queries，其中 queries[i] = [li, ri, ki, vi]。
對于每個查詢，需要按以下步驟依次執行操作：

設定 idx = li。
當 idx <= ri 時：
更新：nums[idx] = (nums[idx] * vi) % (109 + 7)。
將 idx += ki。
在處理完所有查詢后，返回數組 nums 中所有元素的 按位異或 結果。

解題思路：大數據范圍 - 不會寫 - 轉載佬的

如果?ki?>n?，我們直接暴力計算，因為下標每次增加?n?，最多加?n??次就到?n?了。維護這種操作的復雜度是?O(qn?)。

如果?ki?≤n?，注意到本次操作被修改的下標?modki??都和?li?modki??相等，又因為只要求最后的答案，所以我們可以把這個信息先分類記下來：步長為?ki?，且下標?modki??為特定值，且位于區間?[li?,ri?]?里的所有下標都要乘以?vi?。步長只有?n??種，每種步長的?mod?也只有?n??種，因此我們只有?O(n)?類信息要記錄。

怎么把我們記錄的信息還原成答案呢？我們枚舉每類信息，這樣問題變為：每次給一個區間乘以?vi?，問每個數最后的值。這就是?leetcode 1109. 航班預定統計，對操作區間排序，使用差分 + 掃描線的思想即可離線處理。1109 題里，加法的逆運算是減法，本題里模意義下乘法的逆運算是求逆元。

還原答案的復雜度是多少呢？注意到相同步長不同余數的下標是不會重復的，因此每種步長會恰好把所有下標枚舉一遍，因此我們會枚舉?O(nn?)?次下標，再加上對操作的排序，因此復雜度為?O(qlogq+nn?)。

最后考慮求逆元的復雜度，整體復雜度為?O(q(logq+logM)+nn?)，其中?M=109+7?是模數。

class Solution {
public:int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {int n = nums.size(), B = sqrt(n);// 求乘法逆元const int MOD = 1e9 + 7;auto inv = [&](long long a) {long long b = MOD - 2, y = 1;for (; b; b >>= 1) {if (b & 1) y = (y * a) % MOD;a = a * a % MOD;}return y;};long long A[n];for (int i = 0; i < n; i++) A[i] = nums[i];typedef pair<int, long long> pil;vector<pil> vec[B + 1][B + 1];for (auto &qry : queries) {int l = qry[0], r = qry[1], K = qry[2], v = qry[3];if (K <= B) {// 步長不超過根號，先把操作記下來// 差分思想：記錄操作開始的位置以及原運算，再記錄操作結束的位置以及逆運算vec[K][l % K].push_back({l, v});vec[K][l % K].push_back({r + 1, inv(v)});} else {// 步長超過根號，暴力處理for (int i = l; i <= r; i += K) A[i] = A[i] * v % MOD;}}// 枚舉每一類操作for (int k = 1; k <= B; k++) for (int m = 0; m < k; m++) {// 把操作按下標從左到右排序sort(vec[k][m].begin(), vec[k][m].end());// 掃描線維護當前乘積long long now = 1;// 枚舉這一類里的所有下標for (int i = m, j = 0; i < n; i += k) {// 用掃描線進行需要的操作while (j < vec[k][m].size() && vec[k][m][j].first <= i) {now = now * vec[k][m][j].second % MOD;j++;}A[i] = A[i] * now % MOD;}}long long ans = 0;for (int i = 0; i < n; i++) ans ^= A[i];return ans;}
};

感謝大家的點贊和關注，你們的支持是我創作的動力！

?