ABC212

本期开始题目变为8道，100+200+300+400 * 2+500 * 2+600的模式。
F和G两个500分题均有难度，洛谷评分蓝

C - Min Difference

枚举$a_i$，$b$数组中二分，在结果中求最小值。这里写的有点冗余了，lower_bound查找的是大于等于target的位置。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

char s[5];
int n, m;
int a[200020];
int b[200020];

 
int main() {
    //freopen("in.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++ i) 
        scanf("%d", &a[i]);
    for(int i = 0; i < m; ++ i) {
        scanf("%d", &b[i]);
    } 
    sort(a, a + n);
    sort(b, b + m);
    ll ans = ll(1e18);
    for(int i = 0; i < n; ++ i){
        int j = lower_bound(b, b + m, a[i]) - b;
        if(j < m) {
            ll temp = abs(b[j + 1] - a[i]);
            ans = min(ans, temp);
        }
        if (j > 0) {
            ll temp = abs(b[j - 1] - a[i]);
            ans = min(ans, temp);
        }
        ll temp = abs(b[j] - a[i]);
        ans = min(ans, temp);
    }
    printf("%lld\n", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

D - Querying Multiset

堆的灵活运用，维护一个最小堆，并维护整体加的值。

/*
 * @Author: C.D.
 * @Date: 2024-02-23 11:20:19
 * @LastEditors: C.D.
 * @LastEditTime: 2024-02-27 16:29:53
 * @FilePath: \atcoder\atcoder.cpp
 *
 * Copyright (c) 2024 by C.D./tongwoo.cn, All Rights Reserved.
 */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LT(x) (x * 2)
#define RT(x) (x * 2 + 1)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

int n;
ll add;
priority_queue<ll, vector<ll>, greater<ll>> qu;


int main(){
    //freopen("in.txt", "r", stdin);
    scanf("%d", &n);
    for(int i = 0; i < n; ++ i) {
        int op;
        scanf("%d", &op);
        if(op == 1) {
            ll x;
            scanf("%lld", &x);
            qu.push(x - add);
        } else if (op == 2) {
            ll x;
            scanf("%lld", &x);
            add += x;
        } else {
            ll frt = qu.top();
            qu.pop();
            printf("%lld\n", frt + add);
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

E - Safety Journey

DP
本题的边构成反图$G$，即有$M$条边是未连通的。在做的时候只需要减去这些边即可。
设$f(i,j)$为$i$步后，走到点$j$的方法数。显然有
$$f(i,j)=\sum _{e(j,k)\in G}f(i-1,k)$$
即点$j,k$相连通
但这个$k$数量非常大，接近$O(N)$，不能直接加起来。所以反过来考虑那些$e(j,k)\notin G$的，从总数中减去$f(i-1,k)$
$$f(i,j)=\sum _{k=1}^{n}f(i-1,k)-\sum _{e(j,k)\notin G}f(i-1,k)$$

/*
 * @Author: C.D.
 * @Date: 2024-02-23 11:20:19
 * @LastEditors: C.D.
 * @LastEditTime: 2024-02-27 17:18:33
 * @FilePath: \atcoder\atcoder.cpp
 *
 * Copyright (c) 2024 by C.D./tongwoo.cn, All Rights Reserved.
 */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LT(x) (x * 2)
#define RT(x) (x * 2 + 1)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

ll dp[5005][5005];
vi g[5005];
int n, m, k;
ll mod = 998244353;


void bfs() {
    dp[0][0] = 1ll;
    ll s = 1ll;
    for(int i = 1; i <= k; ++ i) {
        ll temp = 0;
        for(int u = 0; u < n; ++ u) {
            dp[i][u] = (s + mod - dp[i - 1][u]) % mod;
            for(int v: g[u]) {
                dp[i][u] = (dp[i][u] + mod - dp[i - 1][v]) % mod;
            }
            temp = (temp + dp[i][u]) % mod;
        }
        s = temp;
    }
    printf("%lld\n", dp[k][0] % mod);
}


int main(){
    //freopen("in.txt", "r", stdin);
    scanf("%d%d%d", &n, &m, &k);
    
    for(int i = 0; i < m; ++ i) {
        int u, v;
        scanf("%d%d", &u, &v);
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    bfs();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

F - Greedy Takahashi

在有向无环图中建立倍增链，跳表的思想
$dp[i][j]$代表index为$i$的边在$2^j$次模拟操作后新边的index
set中使用lower_bound 记录$dp[i][0]$，然后倍增查询位置
具体见代码

/*
 * @Author: C.D.
 * @Date: 2024-02-23 11:20:19
 * @LastEditors: C.D.
 * @LastEditTime: 2024-02-29 14:57:49
 * @FilePath: \atcoder\atcoder.cpp
 *
 * Copyright (c) 2024 by C.D./tongwoo.cn, All Rights Reserved.
 */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LT(x) (x * 2)
#define RT(x) (x * 2 + 1)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int N = 100020;

int n, m, q;
struct Edge {
    int u, v, s, t;
};
Edge e[N];
set<pii> ss[N];
int f[N][18];


int main(){
    //freopen("in.txt", "r", stdin);
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= m; ++ i) {
        int u, v, s, t; 
        scanf("%d%d%d%d", &u, &v, &s, &t);
        Edge edge({u, v, s, t});
        e[i] = edge;
        ss[u].insert({s, i});
    }
    for (int i = 1; i <= m; ++ i) {
        int v = e[i].v, t = e[i].t;
        auto it = ss[v].lower_bound(pii({t, 0}));
        if (it != ss[v].end()) {
            f[i][0] = it->second;
        }
    }
    for(int j = 1; j <= 17; ++ j) {
        for(int i = 1; i <= m; ++ i) {
            f[i][j] = f[f[i][j - 1]][j - 1];
        }
    }
    while(q --) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        auto it = ss[y].lower_bound(pii(x, 0));
        if(it == ss[y].end() || e[it->second].s >= z) {
            printf("%d\n", y);
        } else {
            int idx = it->second;
            for(int j = 17; j >= 0; -- j) {
                if(f[idx][j] && e[f[idx][j]].s < z) {
                    idx = f[idx][j];
                }
            }
            if(e[idx].t >= z) {
                printf("%d %d\n", e[idx].u, e[idx].v);
            } else {
                printf("%d\n", e[idx].v);
            }
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

G - Power Pair

预备知识：
数论阶
欧拉函数
以及欧拉函数和数论阶之间的关系

手模一下可以列出算式：
$$1+\sum _d\phi (d)\ast d$$
其中$\phi (x)$为欧拉函数，$d$是$n-1$的因数
然后数据范围不大，直接算欧拉函数就好了

/*
 * @Author: C.D.
 * @Date: 2024-02-23 11:20:19
 * @LastEditors: C.D.
 * @LastEditTime: 2024-02-29 17:26:28
 * @FilePath: \atcoder\atcoder.cpp
 *
 * Copyright (c) 2024 by C.D./tongwoo.cn, All Rights Reserved.
 */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LT(x) (x * 2)
#define RT(x) (x * 2 + 1)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;


ll n;
ll mod = 998244353;


ll phi(ll x) {
    ll ans = x;
    for (ll i = 2; i * i <= x; ++ i) {
        if(x % i == 0) {
            ans = ans / i * (i - 1);
            while(x % i == 0) 
                x /= i;
        }
    }
    if(x > 1) {
        ans = ans / x * (x - 1);
    }
    return ans % mod;
}


int main(){
    //freopen("in.txt", "r", stdin);
    scanf("%lld", &n);
    ll p = n - 1;
    ll ans = 1;
    for(ll i = 1; i * i <= p; ++ i) {
        if(p % i == 0) {
            ans = (ans + phi(i) * i % mod) % mod;
            if (i * i != p) {
                ll t = p / i % mod;
                ans = (ans + phi(p / i) * t % mod) % mod;
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69