Contest Notes

Codeforces Round 929 (Div. 3)

比赛链接

A

[Codeforces 1933A] Turtle Puzzle: Rearrange and Negate.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
#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];
void solve()
{
    int n = read(), ans = 0;
    for (int i = 1; i <= n; i++) ans += abs(read());
    cout << ans << '\n';
}

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

B

[Codeforces 1933B] Turtle Math: Fast Three Task.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()
{
    n = read();
    int sum = 0;
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n; i++) sum += a[i];
    if (sum % 3 == 0) return puts("0"), void();
    if ((sum + 1) % 3 == 0) return puts("1"), void();
    for (int i = 1; i <= n; i++)
        if ((sum - a[i]) % 3 == 0)
            return puts("1"), void();
    return puts("2"), void();
}

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

C

[Codeforces 1933C] Turtle Fingers: Count the Values of k.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 int INF = 1 << 30;
// const long long INF = 1LL << 60;
int a, b, l;
int work(int a, int b)
{
    int res = 0, X = l;
    std::set<int> S;
    for (int A = 1; 1; A *= a)
    {
        for (int B = 1; 1; B *= b)
            if (l % (A * B) == 0)
                S.insert(l / (A * B));
            else break;
        if (l % A != 0) break;
    }
    return S.size();
}
void solve()
{
    a = read(), b = read(), l = read();
    if (a < b) std::swap(a,  b);
    cout << work(a, b) << '\n';
}

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

D

[Codeforces 1933D] Turtle Tenacity: Continual Mods.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
#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];
void solve()
{
    int n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    std::sort(a + 1, a + 1 + n);
    if (a[n] == a[1]) return puts("NO"), void();
    int c = 0;
    for (int i = 1; i <= n; i++)
        if (a[i] == 1) c++;
    if (c > 1) return puts("NO"), void();
    if (a[2] != a[1]) return puts("YES"), void();
    for (int i = 2; i <= n; i++)
        if (a[i] % a[1] != 0)
            return puts("YES"), void();
    puts("NO");
}

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

E

[Codeforces 1933E] Turtle vs. Rabbit Race: Optimal Trainings.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 = 1e6 + 5;
const int INF = 1 << 30;
// const long long INF = 1LL << 60;
int n, a[N], b[N];
void solve()
{
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n; i++) b[i] = b[i - 1] + a[i];
    for (int q = read(), l, u; q--; )
    {
        l = read(), u = read();
        int res = l;
        for (int L = l, R = n; L <= R; )
        {
            int mid = (L + R) >> 1;
            int tot = b[mid - 1] - b[l - 1];
            int st = u - tot, ed = u - tot - a[mid] + 1;
            int sum = (st + ed) * a[mid] / 2;
            if (sum > 0) res = mid, L = mid + 1;
            else R = mid - 1;
        }
        cout << res << ' ';
    }
    cout << '\n';
}

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

F

观察到几个事情

  1. 往上走相当于把原图固定没走
  2. 往下走 1 格相当于原图把原图固定走 2 格
  3. 往右走 1 格相当于把原图固定以后 向下 1 格 + 向右 1 格
[Codeforces 1933F] Turtle Mission: Robot and the Earthquake.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 = 1e3 + 5;
const int INF = 1 << 30;
// const long long INF = 1LL << 60;
int n, m, a[N][N], f[N][N];
void upd(int &x, int y) { x = std::min(x, y); }
void solve()
{
    n = read(), m = read();
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            a[i][j] = read(), f[i][j] = -1;
    std::queue<pii> q;
    q.emplace(0, 0), f[0][0] = 0;
    int ans = INT_MAX;
    while (!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();
        if (y == m - 1)
            ans = std::min(ans, f[x][y] + ((x  - (n - 1 + f[x][y])) % n + n) % n);
        if (f[(x + 1) % n][y + 1] == -1 and a[(x + 1) % n][y + 1] == 0 and y + 1 < m)
            f[(x + 1) % n][y + 1] = f[x][y] + 1,
            q.emplace((x + 1) % n, y + 1);
        if (f[(x + 2) % n][y] == -1 and a[(x + 1) % n][y] == 0 and a[(x + 2) % n][y] == 0)
            f[(x + 2) % n][y] = f[x][y] + 1,
            q.emplace((x + 2) % n, y);
    }
    if (ans == INT_MAX) ans = -1;
    cout << ans << '\n';
}

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

Codeforces Round 929 (Div. 3)

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

Author

TosakaUCW

Posted on

2024-02-28

Updated on

2024-02-29

Licensed under

#

Comments

Catalogue

×