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

A - Second Half Sum#

因为 $N$ 为偶数，序列后半部分的下标范围为 $\frac{N}{2}+1$ 到 $N$ 。读入序列时只累加满足 $i\geq \frac{N}{2}+1$ 的元素即可。时间复杂度为 $O(N)$ ，额外空间复杂度为 $O(1)$ 。

1
void solve(){
2
    int n; cin >> n;
3
    int sum = 0;
4
    for(int i = 1; i <= n;i++){
5
        int x; cin >> x;
6
        if(i >= n / 2 + 1) sum += x;
7
    }
8
    cout << sum << endl;
9
}

B - Old Maid#

对于值为 $x$ 的卡片，设其出现次数为 $cnt_x$ 。每次操作会删除两张相同的卡片，所以最终剩余数量只由 $cnt_x$ 的奇偶性决定：偶数张可以全部配对删除，奇数张会剩下一张。
因此先统计每个整数的出现次数，再将所有出现次数为奇数的整数值累加到答案中。使用 $map$ 统计时，时间复杂度为 $O(NlogN)$ ，空间复杂度为 $O(N)$ 。

1
void solve(){
2
    int n; cin >> n;
3
    map<int, int> mp;
4
    for(int i = 1; i <= n;i++){
5
        int x; cin >> x;
6
        mp[x]++;
7
    }
8
    int ans = 0;
9
    for(auto it : mp){
10
        if(it.second & 1) ans += it.first;
11
    }
12
    cout << ans << endl;
13
}

C - Change Schools#

先统计每个班级当前的人数 $cnt_i$ ，并求出全局最大人数 $ma=\max cnt_i$ 。如果选择第 $i$ 个班级，加入后该班人数会从 $cnt_i$ 变为 $cnt_i+1$ ，要使其不小于其他所有班级的人数，必须满足 $cnt_i+1\geq ma$ 。
因此合法班级恰好是当前人数等于 $ma$ 或 $ma-1$ 的班级。人数为 $ma$ 时加入后会成为新的最大值，人数为 $ma-1$ 时加入后会追平当前最大值；更少的班级加入一人后仍小于 $ma$ 。遍历所有班级统计这两类即可。时间复杂度为 $O(N+K)$ ，空间复杂度为 $O(N+K)$ 。

1
void solve(){
2
    int n, k;
3
    cin >> n >> k;
4
    vector<int> a(n + 1, 0);
5
    vector<vector<int>> b(k + 1);
6
    for(int i = 1; i <= n;i++){
7
        cin >> a[i];
8
        b[a[i]].push_back(i);
9
    }
10
    int ma = 0; ll cnt = 0;
11
    for(int i = 1; i <= k;i++)
12
        ma = max(ma, (int)b[i].size());
13
    for(int i = 1; i <= k;i++){
14
        if((int)b[i].size() == ma || (int)b[i].size() == ma - 1)
15
            cnt++;
16
    }
17
    cout << cnt << endl;
18
}

D - Coefficient Stair#

需要枚举所有满足 $\sum_{i=1}^{N}iA_i=K$ 的非负整数序列。使用深度优先搜索依次确定 $A_1,A_2,\ldots,A_N$ 。当正在确定 $A_x$ 且剩余权值为 $rest$ 时， $A_x$ 的取值范围为 $0$ 到 $\lfloor\frac{rest}{x}\rfloor$ ；选择 $i$ 后递归处理下一维，并将剩余权值更新为 $rest-x\times i$ 。
到达最后一维时， $A_N$ 已被剩余权值唯一确定。只有 $rest$ 能被 $N$ 整除时才存在合法取值 $A_N=\frac{rest}{N}$ ，此时输出整个序列。这样不会遗漏方案，也不会重复输出。
为了保证字典序，DFS在每一维都按从小到大的顺序枚举当前值。较前位置的值更小的序列会先完成整棵子树，因此最终输出顺序自然为字典序。 $N=1$ 时唯一答案为 $(K)$ ，可以直接输出。空间复杂度为递归深度 $O(N)$ ；时间复杂度与DFS访问的状态数以及输出量成正比，而输出 $q$ 个序列本身至少需要 $O(qN)$ 的时间。

1
int n, k;
2
vector<int> a;
3

4
void dfs(int x, int rest){
5
    if(x == n){
6
        if(rest % n == 0){
7
            a[n] = rest / n;
8

9
            for(int i = 1; i <= n;i++){
10
                cout << a[i] << ' ';
11
            }
12
            cout << '\n';
13
        }
14
        return;
15
    }
16
    for(int i = 0; i <= rest / x;i++){
17
        a[x] = i;
18
        dfs(x + 1, rest - x * i);
19
    }
20
}
21

22
void solve(){
23
    cin >> n >> k;
24
    a.resize(n + 1);
25
    if(n == 1) {cout << k << '\n'; return;}
26
    dfs(1, k);
27
}

E - K-Divisible Subarrays#

将原序列任意分段后，得分只来自区间和能被 $K$ 整除的段。所有未被选入这些得分段的位置都可以单独分段或并入相邻的无贡献段，不会降低已有得分。因此问题等价于选择尽可能多的、两两不相交且区间和能被 $K$ 整除的非空子数组。
定义前缀和模 $K$ 的余数为 $P_i=(A_1+\cdots+A_i)\bmod K$ ，并令 $P_0=0$ 。区间 $(j,i]$ 的元素和能被 $K$ 整除，当且仅当 $P_j=P_i$ 。再定义 $dp_i$ 表示前 $i$ 个元素中最多能选择多少个合法且互不相交的子数组，则有两种转移：不以 $i$ 结尾时继承 $dp_{i-1}$ ；选择某个以 $i$ 结尾的合法区间 $(j,i]$ 时，贡献为 $dp_j+1$ 。
直接枚举所有 $j$ 会达到 $O(N^2)$ 。代码用 $best[r]$ 维护所有已经处理过且 $P_j=r$ 的位置中最大的 $dp_j$ ，于是 $dp_i=\max(dp_{i-1},best[P_i]+1)$ 。计算完 $dp_i$ 后，再用它更新 $best[P_i]$ 。初始状态 $best[0]=0$ 对应空前缀。使用 $unordered\_map$ 时，期望时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

1
void solve(){
2
    int n, k; cin >> n >> k;
3
    vector<int> a(n + 1, 0);
4
    for(int i = 1; i <= n;i++) cin >> a[i];
5
    unordered_map<ll, int> best;
6
    best[0] = 0;
7
    ll pre = 0;
8
    int dp = 0;
9
    for(int i = 1; i <= n;i++){
10
        pre = (pre + a[i]) % k;
11
        int ndp = dp;
12
        if(best.count(pre))
13
            ndp = max(ndp, best[pre] + 1);
14
        dp = ndp;
15
        if(best.count(pre))
16
            best[pre] = max(best[pre], dp);
17
        else best[pre] = dp;
18
    }
19
    cout << dp << '\n';
20
}

模板：

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

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

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

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

29
void solve(){
30
}
31

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

Mkrari的个人博客

A - Second Half Sum#

B - Old Maid#

C - Change Schools#

D - Coefficient Stair#

E - K-Divisible Subarrays#