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

A - Not X#

只需要构造一个属于 $[1,3]$ 且不等于 $X$ 的整数。若 $X=1$ 就输出 $2$ ，否则输出 $1$ ，两种情况都一定满足要求。时间复杂度和空间复杂度均为 $O(1)$ 。

1
void solve(){
2
    int x; cin >> x;
3
    if(x == 2) cout << 1 << '\n';
4
    if(x == 3) cout << 1 << '\n';
5
    if(x == 1) cout << 2 << '\n';
6
}

B - Exit Order#

按照编号每 $10$ 个元素划分一组，第 $i$ 个位置应当由第 $\lfloor\frac{i-1}{10}\rfloor+1$ 组中的元素占据。该组允许出现的最大编号为 $\left(\lfloor\frac{i-1}{10}\rfloor+1\right)\times10$ 。因此依次检查 $P_i$ 是否超过这个上界即可。虽然代码没有显式检查当前组的下界，但 $P$ 是一个排列：前面的完整位置组已经用完了所有更小编号，所以当前元素不可能属于更早的组。若所有元素均未超过对应上界，分组顺序就是合法的。时间复杂度为 $O(N)$ ，额外空间复杂度为 $O(1)$ 。

1
void solve(){
2
    int n; cin >> n;
3
    bool f = true;
4
    for(int i = 1; i <= n;i++){
5
        int x; cin >> x;
6
        int val = ((i - 1) / 10 + 1) * 10;
7
        if(x > val) f = false;
8
    }
9
    if(f) cout << "Yes" << '\n';
10
    else cout << "No" << '\n';
11
}

C - Remove and Append#

直接在数组中删除元素会引起整体移动，单次操作最坏需要 $O(N)$ 。由于 $P$ 是 $1$ 到 $N$ 的排列，可以直接以元素值作为下标，用 $pre[x]$ 和 $nxt[x]$ 分别记录 $x$ 的前驱和后继，从而用数组模拟双向链表；同时维护链表的 $head$ 和 $tail$ 。将 $x$ 移动到末尾时，先用它的前驱和后继相互连接。若 $x$ 原本是头节点，则改为更新 $head$ ；然后令原来的 $tail$ 指向 $x$ ，并将 $x$ 设为新的尾节点。若 $x$ 已经位于末尾，序列不会改变，可以直接跳过。每次修改只涉及常数个指针，全部询问处理完后从 $head$ 沿 $nxt$ 遍历即可恢复最终排列。建立链表和输出排列均为 $O(N)$ ，处理询问为 $O(Q)$ ，总时间复杂度为 $O(N+Q)$ ，空间复杂度为 $O(N)$ 。

1
void solve(){
2
    int n, q;
3
    cin >> n >> q;
4
    vector<int> pre(n + 1), nxt(n + 1);
5
    vector<int> a(n + 1);
6
    int head = -1, tail = -1;
7
    for(int i = 1; i <= n;i++){
8
        cin >> a[i];
9
        if(i == 1) head = a[i];
10
        if(i > 1){
11
            pre[a[i]] = a[i - 1];
12
            nxt[a[i - 1]] = a[i];
13
        }
14
    }
15
    tail = a[n];
16
    for(int i = 1; i <= q;i++){
17
        int x; cin >> x;
18
        if(tail == x) continue;
19
        if(pre[x] != 0) nxt[pre[x]] = nxt[x];
20
        else head = nxt[x];
21
        if(nxt[x] != 0) pre[nxt[x]] = pre[x];
22
        nxt[tail] = x;
23
        pre[x] = tail;
24
        nxt[x] = 0;
25
        tail = x;
26
    }
27
    int cur = head;
28
    while(cur){
29
        cout << cur << " ";
30
        cur = nxt[cur];
31
    }
32
    cout << '\n';
33
}

D - Outweigh#

令 $c_i=A_i-B_i$ ，要求等价于构造正整数权值，使 $\sum_{i=1}^{N}c_iW_i>0$ 。若所有 $c_i\leq0$ ，由于每个 $W_i$ 都必须为正数，上式不可能严格大于 $0$ ，因此无解。若存在 $c_i>0$ ，则把所有正系数对应的权值设为 $10^{18}$ ，其余权值设为 $1$ 。正系数均为整数，所以正贡献至少为 $10^{18}$ ；另一方面，负系数的绝对值小于 $10^9$ ，且 $N\leq10^5$ ，全部负贡献的绝对值小于 $10^{14}$ 。因此正贡献一定严格大于负贡献，构造合法。只需遍历数组判断是否存在正系数并输出对应权值，时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

1
void solve(){
2
    int n; cin >> n;
3
    vector<ll> a(n + 1), b(n + 1);
4
    vector<ll> c(n + 1);
5
    bool has_z = false;
6
    vector<int> z;
7
    for(int i = 1; i <= n;i++) cin >> a[i];
8
    for(int i = 1; i <= n;i++) cin >> b[i];
9
    for(int i = 1; i <= n;i++){
10
        c[i] = a[i] - b[i];
11
        if(c[i] > 0) {has_z = true; z.push_back(i);}
12
    }
13
    vector<ll> ans(n + 1);
14
    if(!has_z) {cout << "No" << '\n'; return;}
15
    cout << "Yes" << '\n';
16
    for(auto &it : z){
17
        ans[it] = (ll)1e18;
18
    }
19
    for(int i = 1; i <= n;i++){
20
        if(ans[i] == 0) ans[i] = 1;
21
        cout << ans[i] << " ";
22
    }
23
}

E - One Time Coupon#

设最终有 $i$ 种商品使用优惠券完成至少一次购买，其余 $N-i$ 种商品按 $A_j$ 购买。先假设所有商品都按原价购买，基础费用为 $base=\sum A_j$ 。把商品 $j$ 改为使用优惠券后，费用变化量为 $B_j-A_j$ 。因此当 $i$ 固定时，应选择变化量最小的 $i$ 种商品；将所有 $B_j-A_j$ 排序后取前缀和即可。按原价购买一次会产生一张优惠券，而使用优惠券购买会消耗一张。上述方案产生 $N-i$ 张、消耗 $i$ 张优惠券。当 $i\leq N-i$ 时，不需要额外购买；当 $i>N-i$ 时，还缺少 $2i-N$ 张优惠券。每张缺少的优惠券都可以通过额外按原价购买任意商品获得，而重复购买的最低单价是 $\min A_j$ ，所以补充费用为 $\max(0,2i-N)\times\min A_j$ 。枚举 $i=0,1,\ldots,N$ ，维护排序后变化量的前缀和，并对 $base+\sum_{j=1}^{i}diff_j+\max(0,2i-N)\times\min A_j$ 取最小值。排序占用 $O(N\log N)$ 时间，枚举占用 $O(N)$ 时间，空间复杂度为 $O(N)$ 。

1
void solve(){
2
    int n; cin >> n;
3
    ll base = 0;
4
    ll mia = LLONG_MAX;
5
    vector<ll> diff;
6
    for(int i = 1; i <= n;i++){
7
        ll a, b; cin >> a >> b;
8
        base += a;
9
        mia = min(mia, a);
10
        diff.push_back(b - a);
11
    }
12
    sort(diff.begin(), diff.end());
13
    ll ans = base, cur = base;
14
    for(int i = 1; i <= n;i++){
15
        cur += diff[i - 1];
16
        ll extra = max(0, 2 * i - n);
17
        ans = min(ans, cur + extra * mia);
18
    }
19
    cout << ans << '\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
struct DSU{
30
    vector<int> fa, sz;
31
    DSU(int n){
32
        fa.resize(n + 1);
33
        sz.resize(n + 1, 1);
34
        for(int i = 1; i <= n;i++){
35
            fa[i] = i;
36
        }
37
    }
38
    int find(int x){
39
        if(fa[x] == x) return x;
40
        return fa[x] = find(fa[x]);
41
    }
42

43
    bool merge(int x, int y){
44
        x = find(x);
45
        y = find(y);
46
        if(x == y) return false;
47
        if(sz[x] > sz[y]) swap(x, y);
48
        fa[y] = x;
49
        sz[x] += sz[y];
50
        return true;
51
    }
52
};
53

54
void solve(){
55
}
56

57
int main(){
58
    ios::sync_with_stdio(false),
59
    cin.tie(nullptr), cout.tie(nullptr);
60
    int _ = 1;
61
    //cin >> _;
62
    while(_--){
63
        solve();
64
    }
65
    return 0;
66
}

Mkrari的个人博客

A - Not X#

B - Exit Order#

C - Remove and Append#

D - Outweigh#

E - One Time Coupon#