Contest Notes

Codeforces Round 930 (Div. 2)

比赛链接

A

[Codeforces 1937A] Shuffle Party.cpp >folded
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
#include <bits/stdc++.h>
#define int long long
using pii = std::pair<int, int>;
#define pb push_back
using std::cin, std::cout, std::string;
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
const int N = 1e6 + 5;
const int INF = 1 << 30;
// const long long INF = 1LL << 60;
int n, m, a[N];
void solve()
{
    n = read();
    int res = 1;
    for (int k = 1; k <= n; k *= 2LL) res = k;
    cout << res << '\n';
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
#endif
    for (int T = read(); T--; solve());
    return 0;
}

B

[Codeforces 1937B] Binary Path.cpp >folded
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
#include <bits/stdc++.h>
// #define int long long
using pii = std::pair<int, int>;
#define pb push_back
using std::cin, std::cout, std::string;
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
const int N = 1e6 + 5;
const int INF = 1 << 30;
// const long long INF = 1LL << 60;
int n;
void solve()
{
    string s1, s2;
    cin >> n >> s1 >> s2;
    string res = s1[0] + s2;
    int ans = 0;
    for (int i = 1; i < n; i++)
        if (res[i] > s1[i])
            res[i] = s1[i], ans = 0;
        else if (res[i] == s1[i])
            ans++;
        else if (res[i] < s1[i])
            break;
    cout << res << '\n' << ans + 1 << '\n';
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("B.in", "r", stdin);
#endif
    for (int T = read(); T--; solve());
    return 0;
}

C

先找出最大的（n-1）。再在或最大里面找最小的

[Codeforces 1937C] Bitwise Operation Wizard.cpp >folded
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
#include <bits/stdc++.h>
// #define int long long
using pii = std::pair<int, int>;
#define pb push_back
using std::cin, std::cout, std::string;
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
const int N = 1e6 + 5;
const int INF = 1 << 30;
// const long long INF = 1LL << 60;
void solve()
{
    int n = read();
    int p = 0;
    for (int i = 1; i < n; i++)
    {
        printf("? %d %d %d %d\n", p, p, i, i), fflush(stdout);
        char ch; cin >> ch; if (ch == '<') p = i;
    }
    std::vector<int> a;
    int q = p;
    for (int i = 0; i < n; i++)
    {
        printf("? %d %d %d %d\n", p, q, p, i), fflush(stdout);
        char ch; cin >> ch;
        if (ch == '<') a.clear(), a.pb(i), q = i;
        else if (ch == '=') a.pb(i);
    }
    int m = a.size();
    int t = a[0];
    for (int i = 1; i < m; i++)
    {
        printf("? %d %d %d %d\n", t, t, a[i], a[i]), fflush(stdout);
        char ch; cin >> ch; if (ch == '>') t = a[i];
    }
    printf("! %d %d\n", t, p), fflush(stdout);
}

signed main()
{
#ifndef ONLINE_JUDGE
    // freopen("C.in", "r", stdin);
#endif
    for (int T = read(); T--; solve());
    return 0;
}

D

其实应该算一个高级点的模拟题

[Codeforces 1937D] Pinball.cpp >folded
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
#include <bits/stdc++.h>
#define int long long
using pii = std::pair<int, int>;
#define pb push_back
using std::cin, std::cout, std::string;
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
const int N = 1e6 + 5;
const int INF = 1 << 30;
// const long long INF = 1LL << 60;
int n, a[N], b[N];
void solve()
{
    string s; cin >> n >> s;
    std::vector<int> ans(n, -1), l, r;

    for (int i = 0; i < n; i++)
        if (s[i] == '>') r.pb(i);
        else l.pb(i);
    std::reverse(l.begin(), l.end());
    for (int i = 0, tot = 0; i < n and !l.empty(); i++)
        tot += (l.back() - i) * 2, l.pop_back(), ans[i] = i + 1 + tot;
    for (int i = n - 1, tot = 0; ~i and !r.empty(); i--)
        tot += (i - r.back()) * 2, r.pop_back(), ans[i] = n - i + tot;
    for (int i = 0; i < n; i++) cout << ans[i] << ' ';
    puts("");
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("D.in", "r", stdin);
#endif
    for (int T = read(); T--; solve());
    return 0;
}

E

看了题解，有一个叫 前后缀优化建边 的 trick

并不需要那么多边，可以将 m 个属性离散化，然后 m 个属性之间 从小到大连边。

[Codeforces 1937E] Pokémon Arena.cpp >folded
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
#include <bits/stdc++.h>
#define int long long
using pii = std::pair<int, int>;
using tuu = std::tuple<int, int, int>;
#define pb push_back
using std::cin, std::cout, std::string, std::vector;
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
const int N = 1e6 + 5;
const int INF = 1e18;
int n, m, a[N];
void solve()
{
    n = read(), m = read();
    vector<int> c(n + 1);
    for (int i = 1; i <= n; i++) c[i] = read();
    vector<vector<int>> a(n + 1, vector<int>(m + 1));
    vector<vector<pii>> b(m + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            a[i][j] = read(), b[j].pb({a[i][j], i});
    vector<vector<int>> rk(n + 1, vector<int>(m + 1));
    vector<vector<int>> dec(n + 1, vector<int>(m + 1));
    for (int j = 1; j <= m; j++)
    {
        std::sort(b[j].begin(), b[j].end());
        for (int i = 0; i < n; i++)
        {
            auto [x, id] = b[j][i];
            rk[id][j] = i + 1;
            dec[i + 1][j] = id;
        }
    }

    int ans = INF;
    vector<int> vis(n + 1, 0);
    vector<vector<int>> dist(n + 1, vector<int>(m + 1, INF));
    std::priority_queue<tuu, vector<tuu>, std::greater<tuu>> Q;
    vis[1] = 1;
    for (int j = 1; j <= m; j++) dist[1][j] = 0, Q.push({dist[1][j], 1, j});
    while (!Q.empty())
    {
        auto [w, x, t] = Q.top(); Q.pop();
        // cout << w << x << t << '\n';
        if (dist[x][t] < w) continue;
        if (x == n) ans = std::min(ans, w + c[n]);
        if (rk[x][t] < n)
        {
            int z = dec[rk[x][t] + 1][t];
            if (w < dist[z][t])
                dist[z][t] = w, Q.push({dist[z][t], z, t});
        }
        if (rk[x][t] > 1)
        {
            int z = dec[rk[x][t] - 1][t];
            if (w + a[x][t] - a[z][t] < dist[z][t])
                dist[z][t] = w + a[x][t] - a[z][t], Q.push({dist[z][t], z, t});
        }
        if (!vis[x])
        {
            vis[x] = 1;
            for (int j = 1; j <= m; j++)
                if (w + c[x] < dist[x][j])
                    dist[x][j] = w + c[x], Q.push({dist[x][j], x, j});
        }
    }
    cout << ans << '\n';
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("E.in", "r", stdin);
#endif
    for (int T = read(); T--; solve());
    return 0;
}

Codeforces Round 930 (Div. 2)

https://tosakaucw.github.io/codeforces-round-930-div-2/

Author

TosakaUCW

Posted on

2024-03-04

Updated on

2024-03-25

Licensed under

#

Comments

Catalogue

×