A.
略
B.
模拟
C.
贪心,顺序枚举,若 \(s_i < t_i\),将 \(i\) 存到数组中,否则直接令 \(s_i = t_i\),输出 \(s\)。
然后从后往前的枚举数组,依次修改并输出即可。
D.
一开始看错数据范围,虚空想了好久。。
用 用 \(set\) 找每一列,每一行的第一个没被摧毁的墙壁即可。
E.
给一个数组 \(a\) 和整数 \(k\),把 \(a\) 分割成若干个子数组,使得没有一个子数组的和为 \(k\) 的方案数。
设 \(f_i\) 表示 \(i\) 个中,以 \(i\) 结尾,没有一个子数组的和为 \(k\) 的分割方案数。
对于每个数 \(a_i\),统计以 \(i\) 结尾的子数组的和为 \(k\) 的方案数之和,可以用 前缀和与 map 维护,然后把以 \(i\) 结尾的方案数加进 map 中。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 7;
const int mod = 998244353;
int a[N], f[N];
signed main() {
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i ++) cin >> a[i];
int now = 0;
map<int, int> mp;
mp[0] = 1, now = 1;
for(int i = 1; i <= n; i ++) a[i] += a[i - 1];
for(int i = 1; i <= n; i ++) {
f[i] = now % mod;
f[i] = (f[i] % mod - mp[a[i] - k] % mod + mod) % mod;
mp[a[i]] = (mp[a[i]] + f[i] % mod) % mod;
now = (now + f[i]) % mod;
}
cout << f[n] % mod << endl;
}