题目链接
A
k 次操作，每次删除数组的第一个元素或者最后一个元素，求最后数组和的最大值
错误做法：每次操作比较第一个元素和最后一个元素，删除较小的一个。
这样不能只能保证一次操作是最优的；对于多次删除操作，不能保证
正确做法：维护一个 n - k 长度的滑动窗口，遍历整个数组求得滑动窗口和的最大值
代码
void slove()
{int n, k; cin >> n >> k;vector<int> a(n);for (int i = 0; i < n; i++) cin >> a[i];LL res = 0;for (int i = 0; i < n - k; i++){res += a[i];}LL t = res;for (int i = n - k; i < n; i++){t -= a[i - n + k];t += a[i];res = max(res, t);}cout << res << endl;
} B
和括号匹配是一样的，使用一个栈模拟。
代码
int main()
{int n; cin >> n;string s; cin >> s;string stk;for (int i = 0; i < s.size(); i++){stk.push_back(s[i]);if (stk.size() >= 2){string t;t += stk[stk.size() - 2];t += stk[stk.size() - 1];if (t == "fc" || t == "tb"){stk.pop_back();stk.pop_back();}}}cout << stk.size() << endl;
}C
先明白一个结论：当 n 为偶数，gcd(n, n - 2) = 2（n > 2)
从（1， 1）到（2， 2）需要 2 步（对于任意整数 n，gcd（n, n) = n)
所以当 n 为偶数，最少步数为 4
当 n 为奇数时，gcd(n - 1, n - 3) = 2 (n > 3)。n - 1 为偶数，从（1，1）到（n - 1， n - 1）最少步数为 4，（n - 1，n - 1）到（n，n）需要 2 步
所以当 n 为奇数，最少步数为 6
代码
void slove()
{int n; cin >> n;int res = 2 * (n - 1);if (n & 1)res = min(res, 6);elseres = min(res, 4);cout << res << endl;
}D
每次询问给定一个 x ，需要输出给出包含了 x 位置且区间和为完全平方数的连续子数组个数。
题意转换就是：包含 x 位置且区间和为完全平方数的区间有多少个
利用前缀和预处理好数组的每一个区间（数组长度：n <= 1000)；当一个区间和为完全平方数时，使用差分改变区间
代码
const int N = 1010;
int a[N], pre[N];
int n, q;
int d[N];
void slove()
{cin >> n >> q;for (int i = 1; i <= n; i++){cin >> a[i];pre[i] = pre[i - 1] + a[i];}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){int u = pre[j] - pre[i - 1];int x = sqrt(u);if (x * x != u) continue;d[i] ++;d[j + 1] --;}}for (int i = 1; i <= n; i++) d[i] = d[i - 1] + d[i];while (q--){int x; cin >> x;cout << d[x] << endl;}
} E
题意转换：对于数组中的任意一个元素 a，令 a 的约数个数为 x，数组为 a 的约数个数为 y，求有多少个元素，使得 x = y。就是说数组中一个元素的约数包含它本身的所有约数
先对数组排序，会有重复的元素，可以先去重，也可以一起处理。
遍历数组，使用数组 cnt，cnt[j] 表示 j 在数组中的约数个数
取元素的上界 N，在记录一遍约数个数
最后 cnt[i] = 0，表示 i 是一个满足要求的元素
const int N = 1e6 + 10;
int nums[N], cnt[N];
int n;int main()
{cin >> n;for (int i = 1; i <= n; i++) cin >> nums[i];sort(nums + 1, nums + 1 + n);for (int i = 1; i <= n; i++){if (nums[i] != nums[i - 1]){int j = nums[i];while (j < N){cnt[j]++;j += nums[i];}}}for (int i = 1; i < N; i++){int j = i;while (j < N){cnt[j]--;j += i;}}int res = 0;for (int i = 1; i < N; i++)if (cnt[i] == 0) res++;cout << res << endl；
}F
对数组 A 操作 n 次，每次在区间 [i, i + w] 中选择一个数和 A[i] 交换，最后变为数组 B。
遍历数组 B，当前元素为 B[i]，可以有两种情况：方案数 cnt
- B[i] 在 A 中：可以将 A 分为三个区间 [1, i)，[i, i + w]，(i + w, n] 。
假如在第一个区间：cnt *= 1，第二个区间：cnt *= 1， 第三个区间：cnt = 0 - B[i] 不在 A 中：在区间 [1, i + w] 中还有 x 个 -1 没有被使用：cnt *= x
当前遍历到 B[i]，那么意味着 B[i] 之前的元素已经被确定了，如果在区间 [1, i) 中有 B[i]，表示在 i 次操作之前将该元素换到后面了。
如果在(i + w, n] ，表示不可能通过交换到当前位置（操作是从左至右遍历的）
#include <iostream>
#include <cstring>
using namespace std;
using LL = long long;
const int N = 2e5 + 10, MOD = 998244353;
int n, w;
int a[N], b[N], pos[N];
LL pre[N];
void solve()
{cin >> n >> w;memset(pos, 0, sizeof pos); // pos 数组记录 a 中元素的下标memset(pre, 0, sizeof pre); // pre 数组记录当前位置之前有多少个 -1for (int i = 1; i <= n; i++){cin >> a[i];if (a[i] != -1)pos[a[i]] = i;if (a[i] == -1)pre[i] = 1;}for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + pre[i];for (int i = 1; i <= n; i++) cin >> b[i];int res = 1, cnt = 0; // cnt 表示当前已经有多少个 -1 被使用了for (int i = 1; i <= n; i++){if (pos[b[i]] != 0){if (pos[b[i]] > i + w)res = 0;}else{int x = pre[min(i + w, n)] - cnt;res = (LL) res * x % MOD;cnt++;}}cout << res << endl;
}int main()
{int t; cin >> t;while (t--) solve();return 0;
}
