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

A - Nine or Nein#

分别计算 $A+B$ 、 $A-B$ 、 $A\times B$ 和 $A\div B$ ，判断其中是否至少有一个结果等于 $9$ 。由于 $B$ 为正整数，不需要处理除数为 $0$ 的情况。满足任意一个条件就输出 $Nine$ ，否则输出 $Nein$ 。

1
void solve(){
2
    int a, b;
3
    cin >> a >> b;
4
    if(a + b == 9 || a - b == 9 || a * b == 9 || a * 1.0 / b == 9)
5
        cout << "Nine" << endl;
6
    else cout << "Nein" << endl;
7
}

B - Survey Tabulation#

题目不区分大小写，所以需要先把每个字符串转换成统一形式，再进行频次统计。代码将所有小写字母映射为对应的大写字母，从而使仅大小写不同的字符串得到相同的键。
使用 $map$ 记录规范化后每个字符串出现的次数，并在插入时同步维护最大频次 $ans$ 。设所有字符串的总长度为 $L$ ，时间复杂度为 $O(LlogN)$ 。

1
void solve(){
2
    int n; cin >> n;
3
    int ans = 0;
4
    map<string, int> mp;
5
    for(int i = 1; i <= n;i++){
6
        string s;
7
        cin >> s;
8
        for(auto& it : s){
9
            if(it - 'a' >= 0){
10
                it = char('A' + it -'a');
11
            }
12
        }
13
        mp[s]++;
14
        ans = max(mp[s], ans);
15
    }
16
    cout << ans << endl;
17
}

C - Cookies and Greedy Takahashi#

将所有负坐标从大到小排序，所有正坐标从小到大排序。这样在任意时刻，负半轴上尚未访问且最靠近当前位置的候选点一定是 $neg[i]$ ，正半轴上的对应候选点一定是 $pos[j]$ ，其他未访问点都位于这两个边界点的外侧，不可能更近。
因此每一步只需要比较当前坐标 $x$ 到 $neg[i]$ 与 $pos[j]$ 的距离。若一侧已经取完，就选择另一侧；否则选择距离更小的一侧。两者距离相等时，负坐标更小，按照题目的次级规则应优先选择负侧，所以代码在 $x-neg[i]\leq pos[j]-x$ 时移动到 $neg[i]$ 。
每个坐标只会被访问一次，排序后的双指针模拟为 $O(N)$ ，加上排序后总时间复杂度为 $O(NlogN)$ ，空间复杂度为 $O(N)$ 。

1
void solve(){
2
    int n; cin >> n;
3
    vector<ll> neg(n), pos(n);
4
    for(int i = 1; i <= n;i++){
5
        int x; cin >> x;
6
        if(x < 0) neg.push_back(x);
7
        else pos.push_back(x);
8
    }
9
    sort(neg.begin(), neg.end(), greater<ll>());
10
    sort(pos.begin(), pos.end());
11
    ll ans = 0, x = 0;
12
    int i = 0, j = 0;
13
    int neg_ptr = (int)neg.size(), pos_ptr = (int)pos.size();
14
    while(i < neg_ptr || j < pos_ptr){
15
        if(j == pos_ptr || (i < neg_ptr && x - neg[i] <= pos[j] - x)){
16
            ans += x - neg[i];
17
            x = neg[i];
18
            i++;
19
        }
20
        else{
21
            ans += pos[j] - x;
22
            x = pos[j];
23
            j++;
24
        }
25
    }
26
    cout << ans << endl;
27
}

D - Chargers#

对于在时刻 $t_0$ 插入、初始电量为 $w$ 的电池，它达到满电的时刻为 $key=t_0+(V-w)$ 。在后续时刻 $t$ ，其电量可以写成 $\min(V,t-key+V)$ 。对于固定的查询时刻 $t$ ，这个值关于 $key$ 单调不增，因此 $key$ 越小，当前电量越大。问题就转化为动态维护所有电池的 $key$ ，每次取出最小值。
代码使用 $multiset$ 保存 $key$ 。插入操作加入 $t+(V-w)$ ；取出操作删除集合中的最小元素，并用 $\min(V,t-key+V)$ 还原当前电量。如果集合为空则输出 $-1$ 。每次操作的时间复杂度为 $O(logQ)$ ，总时间复杂度为 $O(QlogQ)$ ，空间复杂度为 $O(Q)$ 。

1
void solve(){
2
    int Q; ll V;
3
    cin >> Q >> V;
4
    multiset<ll> st;
5
    while(Q--){
6
        int op; cin >> op;
7
        if(op == 1){
8
            int t; ll w;
9
            cin >> t >> w;
10
            st.insert(t + (V - w));
11
        }
12
        else{
13
            int t; cin >> t;
14
            if(st.empty()) cout << -1 << '\n';
15
            else{
16
                ll val = *st.begin();
17
                st.erase(st.begin());
18
                ll cur = t - val + V;
19
                if(cur > V) cur = V;
20
                cout << cur << '\n';
21
            }
22
        }
23
    }
24
}

E - Sum of Square of Sum#

对于一个选出的大小为 $K$ 的下标集合 $S$ ，将平方展开可得 $(\sum_{i\in S}A_i)^2=\sum_{i\in S}A_i^2+2\sum_{i<j,\ i,j\in S}A_iA_j$ 。
固定一个下标 $i$ ，包含它的大小为 $K$ 的集合共有 $\binom{N-1}{K-1}$ 个，所以所有单项平方的总贡献为 $\binom{N-1}{K-1}\sum_i A_i^2$ 。
固定一对不同下标 $i,j$ ，同时包含它们的集合共有 $\binom{N-2}{K-2}$ 个。又因为 $(\sum_i A_i)^2-\sum_i A_i^2=2\sum_{i<j}A_iA_j$ ，所以所有交叉项的总贡献为 $\binom{N-2}{K-2}\left((\sum_i A_i)^2-\sum_i A_i^2\right)$ 。
我们只需要预处理阶乘和逆阶乘来计算两个组合数，再将两部分贡献相加。预处理与求和的时间复杂度为 $O(N+logMOD)$ ，空间复杂度为 $O(N)$ 。

1
void solve(){
2
    ll n, k;
3
    cin >> n >> k;
4

5
    ll s1 = 0, s2 = 0;
6
    vector<ll> A(n);
7
    for(ll i = 0; i < n;i++){
8
        cin >> A[i];
9
        A[i] %= mod;
10
        s1 = (s1 + A[i]) % mod;
11
        s2 = (s2 + A[i] * A[i]) % mod;
12
    }
13

14
    vector<ll> fact(n + 1), inv_fact(n + 1);
15
    fact[0] = 1;
16
    for(ll i = 1; i <= n;i++){
17
        fact[i] = fact[i - 1] * i % mod;
18
    }
19

20
    inv_fact[n] = fast_pow(fact[n], mod - 2, mod);
21
    for(ll i = n; i >= 1; i--){
22
        inv_fact[i - 1] = inv_fact[i] * i % mod;
23
    }
24

25
    ll c1 = C(n - 1, k - 1, fact, inv_fact);
26
    ll c2 = C(n - 2, k - 2, fact, inv_fact);
27
    ll cross = (s1 * s1 % mod - s2 + mod) % mod;
28
    ll ans = (c1 * s2 % mod + c2 * cross % mod) % mod;
29

30
    cout << ans << endl;
31
}

模板：

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

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

Mkrari的个人博客

A - Nine or Nein#

B - Survey Tabulation#

C - Cookies and Greedy Takahashi#

D - Chargers#

E - Sum of Square of Sum#