壁纸链接
题目链接：https://atcoder.jp/contests/abc468/tasks

A - Maximal Value#

直接遍历序列中除首尾外的每个位置 $i$ ，判断是否同时满足 $A_i>A_{i-1}$ 和 $A_i>A_{i+1}$ 。满足条件就将答案加一。

1
int a[110];
2

3
void solved() {
4
    int n; cin >> n;
5
    int cnt = 0;
6
    for(int i = 1; i <= n;i++) cin >> a[i];
7
    for(int i = 2; i < n;i++){
8
        if(a[i] > a[i - 1] && a[i] > a[i + 1])
9
            cnt++;
10
    }
11
    cout << cnt << endl;
12
}

B - Corridor Watch#

我们先记录字符串中所有初始为 $G$ 的位置。对于每个位置 $i$ ，将区间 $[\max(0,i-D),\min(M-1,i+D)]$ 内的字符全部标记为 $G$ ，最后统计仍为 $.$ 的位置数量即可。
这里需要先保存所有初始的 $G$ ，再进行区间标记，避免把标记过程中产生的新 $G$ 错误地当成警卫位置继续扩展。

1
void solved() {
2
    int D, M; cin >> M >> D;
3
    string s; cin >> s;
4
    vector<int> pos;
5
    for(int i = 0; i < (int)s.size();i++){
6
        if(s[i] == 'G')
7
            pos.push_back(i);
8
    }
9
    int ans = 0;
10
    for(auto it1 : pos){
11
        for(int i = max(0, it1 - D); i <= min((int)s.size() - 1, it1 + D);i++)
12
            s[i] = 'G';
13
    }
14
    for(auto it : s)
15
        if(it == '.') ans++;
16
    cout << ans << endl;
17
}

C - Between P and Q#

由于 $N\leq 10$ ，可以直接枚举全排列。 $next\_permutation$ 会将当前排列修改为字典序严格大于它的下一个排列，所以从 $P$ 开始不断调用该函数，直到得到 $Q$ ，期间经过的排列数量就是严格位于 $P,Q$ 之间的排列数量。
如果一开始就有 $P\geq Q$ ，不存在同时满足大于 $P$ 且小于 $Q$ 的排列，答案为 $0$ 。否则每生成一个不等于 $Q$ 的新排列就将答案加一。

1
void solved() {
2
    int N; cin >> N;
3
    vector<int> P(N), Q(N);
4

5
    for(auto &it : P) cin >> it;
6
    for(auto &it : Q) cin >> it;
7
    if(P >= Q) {cout << 0 << endl; return;}
8

9
    int ans = 0;
10
    vector<int> cur = P;
11
    while(next_permutation(cur.begin(), cur.end())){
12
        if(cur == Q) break;
13
        ans++;
14
    }
15
    cout << ans << endl;
16
}

D - Pre-Palindrome#

一个字符串能够通过至多修改一个字符变成回文，当且仅当对称位置字符不同的组数不超过 $1$ 。因此我们只需要统计每个子串中有多少组不匹配的对称字符。
定义 $dp[l]$ 表示上一种长度下，以 $l$ 为左端点的子串中不匹配的对称字符组数。给子串的左右两端各扩展一个字符后，新的不匹配组数为 $ndp[l]=dp[l+1]+[S_l\neq S_r]$ 。因为只关心这个值是否不超过 $1$ ，所以代码中将大于等于 $2$ 的状态统一截断为 $2$ 。
奇数长度与偶数长度的中心不同，因此分别从长度 $3$ 和长度 $2$ 开始，每次将长度增加 $2$ 。长度为 $1$ 的子串一定满足条件，先将答案初始化为 $N$ ；其余子串在转移后状态不超过 $1$ 时计入答案。
整个转移只依赖前一种长度，所以可以使用滚动数组将空间复杂度降为 $O(N)$ ，时间复杂度为 $O(N^2)$ 。

1
void solved() {
2
    string s; cin >> s;
3
    int n = s.size();
4

5
    ll ans = n;
6
    for(int len : {2, 3}){
7
        vector<int> dp(n + 1, 0), ndp(n + 1, 0);
8

9
        for(int i = len; i <= n;i += 2){
10
            int substr_cnt = n - i + 1;
11

12
            for(int j = 0; j < substr_cnt;j++){
13
                int r = j + i - 1;
14
                ndp[j] = min(dp[j + 1] + (s[j] != s[r]), 2);
15
                if(ndp[j] <= 1) ans++;
16
            }
17
            dp.swap(ndp);
18
        }
19
    }
20
    cout << ans << endl;
21
}

E - Sum of Average#

直接枚举所有区间并计算平均值的复杂度至少为 $O(N^2)$ ，所以这里考虑分别计算每个 $A_i$ 对答案的贡献。对于一个包含位置 $i$ 的区间 $[l,r]$ ， $A_i$ 产生的系数为 $\frac{1}{r-l+1}$ 。因此答案可以写成 $\sum_{i=1}^{N}A_iC_i$ ，其中 $C_i=\sum_{l\leq i\leq r}\frac{1}{r-l+1}$ 。
记调和数 $H_k=\sum_{j=1}^{k}\frac{1}{j}$ 。当 $i=1$ 时，包含 $A_1$ 的区间只有 $[1,r]$ ，所以 $C_1=H_N$ 。从 $C_i$ 移动到 $C_{i+1}$ 时，新增加的是左端点为 $i+1$ 的区间，其系数和为 $H_{N-i}$ ；被删除的是右端点为 $i$ 的区间，其系数和为 $H_i$ 。因此有 $C_{i+1}=C_i+H_{N-i}-H_i$ 。
我们预处理 $1$ 到 $N$ 在模 $998244353$ 意义下的逆元，再求出所有调和数，就可以在线性时间内递推每个位置的系数并累加贡献。时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

1
vector<ll> get_inverse(ll n, ll MOD){
2
    vector<ll> inverse(n + 1);
3
    inverse[1] = 1;
4
    for(ll i = 2; i <= n;i++){
5
        inverse[i] = MOD - (MOD / i) * (inverse[MOD % i]) % MOD;
6
    }
7
    return inverse;
8
}
9

10
void solved() {
11
    int N; cin >> N;
12
    vector<ll> inverse = get_inverse(N, mod);
13

14
    vector<ll> harmonic(N + 1, 0);
15
    for(int i = 1; i <= N;i++){
16
        harmonic[i] = (harmonic[i - 1] + inverse[i]) % mod;
17
    }
18

19
    ll ans = 0, coeffic = harmonic[N];
20
    for(int i = 1; i <= N;i++){
21
        ll val; cin >> val;
22
        ans = (ans + val * coeffic) % mod;
23

24
        if(i < N){
25
            coeffic += harmonic[N - i] - harmonic[i];
26
            coeffic %= mod;
27
            if(coeffic < 0) coeffic += mod;
28
        }
29
    }
30
    cout << ans << endl;
31
}

F - Chmax#

每个元素都会被分配给 $x,y$ 中的一个变量，只有当它大于对应变量此前的最大值时才会产生一次贡献。等价地说，我们需要将原排列划分为两个子序列，最大化两个子序列中前缀最大值的数量之和。
先考虑原排列中的全局前缀最大值，即 $P_i>\max(P_1,\ldots,P_{i-1})$ 的位置。它出现时一定大于 $x,y$ 当前的值，所以无论分配给哪一个变量都会产生贡献。代码用 $premax$ 维护当前全局最大值，并用 $cnt$ 统计这部分必然能够取得的贡献。
对于不是全局前缀最大值的元素， $x,y$ 中至少有一个已经保存了比它更大的全局最大值。若想让该元素产生贡献，只能把它放入另一个较小的变量中，而且后续在这个变量中产生贡献的非前缀最大值必须严格递增。因此这部分最多能选出非前缀最大值序列的一条最长上升子序列。反过来，将所有全局前缀最大值放入一个变量，将这条最长上升子序列放入另一个变量，就能取得这个上界。
所以最终答案等于全局前缀最大值的数量加上其余元素的 $LIS$ 长度。代码使用 $tails$ 数组和二分查找维护 $LIS$ ，总时间复杂度为 $O(NlogN)$ ，空间复杂度为 $O(N)$ 。

1
void solved() {
2
    int N; cin >> N;
3
    int premax = 0, cnt = 0;
4

5
    vector<int> tails;
6
    for(int i = 1; i <= N;i++){
7
        int val; cin >> val;
8
        if(premax < val){
9
            premax = val;
10
            cnt++;
11
        }
12
        else{
13
            auto it = lower_bound(tails.begin(), tails.end(), val);
14
            if(it == tails.end()){
15
                tails.push_back(val);
16
            }
17
            else *it = val;
18
        }
19
    }
20
    cout << cnt + (int)tails.size() << endl;
21
}

G - Restricted Permutation#

我们按照数值从小到大，将 $1,2,\ldots,N$ 依次放入最终排列的各个位置。已经放置 $1\sim k$ 后，它们在排列中的最左位置到最右位置构成一个最小覆盖区间。因为区间内共有 $span$ 个位置而已经放置了 $k$ 个数，所以是否连续只需要判断 $span=k$ 。
定义 $dp[span]$ 表示已经放置 $1\sim k$ ，对于任意一个固定的长度为 $span$ 的最小覆盖区间，合法放置方案的数量。接下来放置 $k+1$ ，设新的覆盖区间长度为 $new\_span$ ，转移分为两类：
第一类是把 $k+1$ 放在原覆盖区间内部的空位，此时覆盖区间长度不变，共有 $new\_span-k$ 个空位，贡献为 $(new\_span-k)\times dp[new\_span]$ 。
第二类是把 $k+1$ 放在新覆盖区间的左端点或右端点。删除这个新端点后，原来的最小覆盖区间长度可以是任意小于 $new\_span$ 的值，左右两种放法产生的贡献为 $2\sum_{span<new\_span}dp[span]$ 。这个前缀和可以在枚举 $new\_span$ 时同步维护，使每次转移降为 $O(1)$ 。
完成转移后， $1\sim k+1$ 连续当且仅当 $new\_span=k+1$ 。我们根据 $S_{k+1}$ 为 $o$ 或 $x$ ，只保留连续性与其相符的状态。特别地，集合 $\{1\}$ 以及完整集合 $\{1,2,\ldots,N\}$ 在任何排列中都必然连续，所以 $S_1$ 或 $S_N$ 为 $x$ 时答案直接为 $0$ 。
初始状态为 $dp[1]=1$ ，最终只有覆盖整个排列的状态 $dp[N]$ 需要计入答案。时间复杂度为 $O(N^2)$ ，空间复杂度为 $O(N)$ 。

1
void solved() {
2
    int N; cin >> N;
3
    string s; cin >> s;
4
    // {1} 和 {1,2,...,n} 在任何排列中都一定连续。
5
    if(s[0] == 'x' || s[N - 1] == 'x'){
6
        cout << 0 << endl;
7
        return;
8
    }
9
    /*
10
        dp[span]表示已经放置数字 1...placed，它们的最小覆盖区间长度为 span；
11
        对于任意一个固定的、长度为 span 的区间，满足此前条件的放置顺序数量。
12
    */
13
    vector<ll> dp(N + 1, 0), ndp(N + 1, 0);
14
    dp[1] = 1;
15
    for(int placed = 1; placed < N;placed++){
16
        fill(ndp.begin(), ndp.end(), 0);
17
        // prefix = dp[1] + dp[2] + ... + dp[new_span - 1];
18
        ll prefix = 0;
19
        for(int new_span = 1; new_span <= N;new_span++){
20
            if(new_span >= placed + 1){
21

22
                //在原覆盖区域内容有new_span - placed个空位
23
                ll ways = (ll)(new_span - placed) * dp[new_span] % mod;
24
                //新位置为新区间的左端点和右端点两种情况，所以乘2
25
                ways = (ways + 2 * prefix) % mod;
26

27
                //判断连续（不连续）是否满足'o'('x')，满足才更新
28
                bool is_contiguous = (new_span == placed + 1);
29
                bool required = (s[placed] == 'o');
30
                if(is_contiguous == required)
31
                    ndp[new_span] = ways;
32
            }
33
            prefix += dp[new_span];
34
            if(prefix >= mod) prefix -= mod;
35
        }
36
        dp.swap(ndp);
37
    }
38

39
    cout << dp[N] << endl;
40
}

模板：

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
using ull = unsigned long long;
6
#define endl '\n'
7
#define mod 998244353
8
typedef pair<ll, ll> pll;
9
typedef pair<int, int> pii;
10

11
ll fast_pow(ll a, ll b, ll MOD) {
12
    ll ans = 1;
13
    while (b) {
14
        if (b & 1) ans = (ans * a) % MOD;
15
        b >>= 1;
16
        a = (a * a) % MOD;
17
    }
18
    return ans;
19
}
20

21
vector<ll> get_inverse(ll n, ll MOD){
22
    vector<ll> inverse(n + 1);
23
    inverse[1] = 1;
24
    for(ll i = 2; i <= n;i++){
25
        inverse[i] = MOD - (MOD / i) * (inverse[MOD % i]) % MOD;
26
    }
27
    return inverse;
28
}
29

30
void solved() {
31
}
32

33
int main() {
34
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
35
    int _ = 1;
36
    //cin >> _;
37
    while (_--) {
38
        solved();
39
    }
40
    return 0;
41
}

Mkrari的个人博客