Contest Notes

Codeforces Round 925 (Div. 3)

比赛链接

A

脑袋一片混乱，删了又写写了又删，某些常数调了半天，00:17 才 a，而且吃了发罚时，心态小崩

[Codeforces 1931A] Recovering a Small String.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
#include <bits/stdc++.h>
// #define int long long
#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];
void solve()
{
    int x = read();
    string ans = "";
    if (x > 52) ans += char('a' + x - 52 - 1), x -= (ans[0] - 'a' + 1);
    else ans += 'a', x--;
    if (x > 26) ans += char('a' + x - 26 - 1), x -= (ans[1] - 'a' + 1);
    else ans += 'a', x--;
    ans += char('a' + x - 1);
    cout << ans << '\n';
}

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

B

[Codeforces 1931B] Make Equal.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
#include <bits/stdc++.h>
#define int long long
#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];
void solve()
{
    int n = read(), sum = 0, f = 1, tot = 0;
    for (int i = 1; i <= n; i++) a[i] = read(), sum += a[i];
    sum /= n;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] > sum) tot += a[i] - sum;
        else tot -= sum - a[i];
        if (tot < 0) f = 0;
    }
    puts(f ? "YES" : "NO");
}

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

C

贪心是显然的

[Codeforces 1931C] Make Equal Again.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
#include <bits/stdc++.h>
// #define int long long
#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 = 2e5 + 5;
const int INF = 1 << 30;
// const long long INF = 1LL << 60;
int n, a[N], b[N], c[N];
void solve()
{
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    if (n == 1) return puts("0"), void();
    int l, r, ans = n;
    l = 0, r = n + 1;
    for (int i = 1; i <= n; i++)
        if (a[i] == a[1]) l = i;
        else break;
    for (int i = n; i >= 1; i--)
        if (a[i] == a[1]) r = i;
        else break;
    if (l == n and r == 1) return puts("0"), void();
    ans = r - l - 1;
    l = 0, r = n + 1;
    for (int i = 1; i <= n; i++)
        if (a[i] == a[n]) l = i;
        else break;
    for (int i = n; i >= 1; i--)
        if (a[i] == a[n]) r = i;
        else break;
    ans = std::min(ans, r - l - 1);
    cout << ans << '\n';
}

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

D

相当于 mod y 相等，mod x 互补的数对个数

[Codeforces 1931D] Divisible Pairs.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
#include <bits/stdc++.h>
#define int long long
#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 long long INF = 1LL << 60;
int n, a[N];
void solve()
{
    int n = read(), x = read(), y = read(), res = 0;
    std::map<int, std::vector<int>> cnt;
    for (int i = 1; i <= n; i++) a[i] = read(), cnt[a[i] % y].pb(a[i]);
    for (auto map : cnt)
    {
        std::map<int, int> buk;
        auto vec = map.second;
        std::map<int, int> vis;
        for (auto i : vec) buk[i % x]++;
        for (auto i : vec)
            if (!vis[i % x])
                vis[i % x] = vis[x - i % x] = 1,
                res += i % x == x - i % x ?
                        buk[i % x] * (buk[i % x] - 1) / 2 :
                        buk[i % x] * buk[x - i % x];
        res += buk[0] * (buk[0] - 1) / 2;
    }
    cout << res << "\n";
}

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

E

这傻卵题就直接模拟就行了

开个堆

因为一定是每一步贪心把后导零最多的拿出来操作

md，又大的实现细节边想边写，写的巨慢改来改去，写久了

[Codeforces 1931E] Anna and the Valentine's Day Gift.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
#include <bits/stdc++.h>
// #define int long long
#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 a[N];
struct Node
{
    int bit, cnt0;
    bool friend operator < (Node a, Node b) { return a.cnt0 < b.cnt0; }
};
int countbit(int x)
{
    int res = 0;
    while (x > 0) x /= 10, res++;
    return res;
}
int count0(int x)
{
    int res = 0;
    while (x > 0 and x % 10 == 0) x /= 10, res++;
    return res;
}
void solve()
{
    int n = read(), m = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    std::priority_queue<Node> Q;
    int T = 0, ans = 0;
    for (int i = 1; i <= n; i++) Q.push(Node{countbit(a[i]), count0(a[i])});
    for (int i = 1; i <= n - 1; i++)
    {
        int x = Q.top().bit, y = Q.top().cnt0; Q.pop();
        int k = Q.top().bit; Q.pop();
        Q.push(Node{k + x - y, 0});
    }
    ans = Q.top().bit;
    if (n == 1) ans -= Q.top().cnt0;
    puts(ans > m ? "Sasha" : "Anna");
}

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

F

md，降智了，一眼差分约束了

好久没写图论手速慢的一笔，然后多测邻接表和数组清空还搞了半天

又因为细节原因代码没搞出来下大分了

赛后发现直接判断有没有环就行了

[Codeforces 1931F] Chat Screenshots.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
#include <bits/stdc++.h>
// #define int long long
#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 = 2e5 + 5;
const int INF = 1 << 30;
int n, m, a[N], ind[N];
std::vector<int> g[N];
bool toposort()
{
    int cnt = 0; std::queue<int> Q;
    for (int i = 1; i <= n; i++) if (!ind[i]) Q.push(i);
    for (int u; !Q.empty(); )
    {
        u = Q.front(), Q.pop(), cnt++;
        for (auto v : g[u]) if (!--ind[v]) Q.push(v);
    }
    return cnt == n;
}
void solve()
{
    n = read(), m = read();
    for (int i = 1; i <= n; i++) g[i].clear(), ind[i] = 0;
    while(m--)
    {
        for (int i = 1; i <= n; i++) a[i] = read();
        for (int i = 2; i < n; i++) g[a[i]].pb(a[i + 1]), ind[a[i + 1]]++;
    }
    puts(toposort() ? "YES" : "NO");
}

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

Codeforces Round 925 (Div. 3)

https://tosakaucw.github.io/codeforces-round-925-div-3/

Author

TosakaUCW

Posted on

2024-02-13

Updated on

2024-02-19

Licensed under

#

Comments

Catalogue

×