Contest Notes

Codeforces Round 934 (Div. 2)

比赛链接

A

[Codeforces 1944A] Destroying Bridges.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
#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();
    if (m >= n - 1) return puts("1"), void();
    int k = n - 1;
    while (m >= k and k > 0) n--, m -= k, k--;
    cout << n << '\n';
}

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

B

[Codeforces 1944B] Equal XOR.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
#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() * 2;
    int cnta = m, cntb = m;
    vector<int> a(n), b(n), ansa, ansb;
    for (int i = 0; i < n; i++) a[i] = read() - 1;
    for (int i = 0; i < n; i++) b[i] = read() - 1;
    vector<int> visa(n, 0), visb(n, 0), pushed(n, 0);
    for (int i = 0; i < n and cnta > 0; i++)
    {
        if (visa[a[i]] and cnta >= 2) cnta -= 2, ansa.pb(a[i]), ansa.pb(a[i]), pushed[a[i]] = 1;
        visa[a[i]] = 1;
    }
    for (int i = 0; i < n and cntb != cnta; i++)
    {
        if (visb[b[i]] and cntb >= 2) cntb -= 2, ansb.pb(b[i]), ansb.pb(b[i]), pushed[b[i]] = 1;
        visb[b[i]] = 1;
    }
    for (int i = 0; i < n and cnta > 0; i++)
        if (!pushed[a[i]]) ansa.pb(a[i]), ansb.pb(a[i]), cnta --;
    for (auto x : ansa) cout << x + 1 << ' ';
    puts("");
    for (auto x : ansb) cout << x + 1 << ' ';
    puts("");
}

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

C

[Codeforces 1944C] MEX Game 1.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>;
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();
    vector<int> cnt(n + 1, 0);
    for (int i = 1; i <= n; i++) a[i] = read(), cnt[a[i]] ++;
    for (int i = 0, tmp = 0; i <= n; i++)
    {
        tmp += (cnt[i] == 1);
        if (!cnt[i] or cnt[i] and tmp == 2)
        {
            cout << i << '\n';
            break;
        }
    }
}

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

D

A string $t$ is said to be $k$-good if there exists at least one substring$^\dagger$ of length $k$ which is not a palindrome$^\ddagger$. Let $f(t)$ denote the sum of all values of $k$ such that the string $t$ is $k$-good.

You are given a string $s$ of length $n$. You will have to answer $q$ of the following queries:

  • Given $l$ and $r$ ($l < r$), find the value of $f(s_ls_{l + 1}\ldots s_r)$.

一个字符串 t 如果至少存在一个长度为 k 的子串不是回文，则可以被称作是 k-good。
每次求一个串的所有 k-good 的和

e.g. 对于 s[1…..10]，如果 k = 4，而且 s[1…4] 是回文串。也就是说 s[1] == s[4], s[2] == s[3]

假如后面也都是回文串，那么有 s[2] == s[5], s[3] == s[4] ……

不考虑自身的情况下：

如果一个串偶数位奇数位对应相等，那么对于所有 奇数 k 都是不好的

如果一个串每一位都相等，那么对于所有 k 都是不好的

如果一个串不是奇数位和偶数位都对应相等，那么 2 <= k <= len - 1 的奇数 k 也都是好的

如果一个串不是每一位都相等，那么 2 <= k <= len - 1 的偶数 k 都是好的

接下来再考虑一下自身是不是回文串即可

唉这个题赛时没发现这个性质，然后补题发现 hash 也不会打了

CF 赛制单模数 hash 也容易被 hack，最保险的是双随机模数 hash

[Codeforces 1944D] Non-Palindromic Substring.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
#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];
std::vector<int> manacher(string s)
{
    string t = "#";
    for (auto ch : s) t += ch, t += '#';
    int n = t.size();
    vector<int> r(n);
    for (int i = 0, j = 0; i < n; i++)
    {
        if (2 * j - i >= 0 and j + r[j] > i) r[i] = std::min(r[2 * j - i], j + r[j] - i);
        while (i - r[i] >= 0 and i + r[i] < n and t[i - r[i]] == t[i + r[i]]) r[i]++;
        if (i + r[i] > j + r[j]) j = i;
    }
    return r;
}
void solve()
{
    n = read(), m = read();
    string s; cin >> s;
    vector<int> f1(n), f2(n);
    for (int i = n - 1; ~i; i--)
        f1[i] = i + 1 < n and s[i] == s[i + 1] ? f1[i + 1] : i,
        f2[i] = i + 2 < n and s[i] == s[i + 2] ? f2[i + 2] : i;
    auto rad = manacher(s);
    for (int l, r; m--; )
    {
        l = read() - 1, r = read() - 1;
        int ans = 0, len = r - l + 1;
        if (f1[l] < r)
        {
            // 存在偶数 k
            int m = (len - 1) - (len - 1) % 2;
            ans += (m + 2) * (m / 2) / 2;
        }
        if (f2[l] + 1 < r or f2[l + 1] + 1 < r)
        {
            // 存在奇数 k
            int m = len - 1 - len % 2;
            ans += (m + 3) * ((m - 1) / 2) / 2;
        }
        if (rad[l + r + 1] < len) ans += len;
        cout << ans << '\n';
    }
}

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

E

给你一棵树，树上有 $n$ 个顶点，编号为 $1, 2, \ldots, n$ 。最初，所有顶点都被涂成白色。

您可以执行以下两步操作：

  1. 选择顶点 $v$ ( $1 \leq v \leq n$ ) 和距离 $d$ ( $0 \leq d \leq n-1$ )。
  2. 对于所有顶点 $u$ ( $1 \leq u \leq n$ ) 且 $\text{dist}^\dagger(u,v)=d$ 的顶点，将 $u$ 着色为黑色。
    构造一个操作序列，用尽可能少的操作次数将树中的所有节点涂成黑色。可以证明，我们总是可以用最多 $n$ 次的操作来实现这一目的。

考虑一条链上的情况，分奇偶讨论，最优的方法一定是从中心开始，向两边拓展

树上呢？用直径即可

[Codeforces 1944E] Tree Compass.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
#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();
    vector<vector<int>> g(n);
    for (int i = 1, u, v; i < n; i++)
        u = read() - 1, v = read() - 1,
        g[u].pb(v), g[v].pb(u);
    vector<int> fa(n);
    auto find = [&](int rt)
    {
        vector<int> dep(n, -1);
        fa[rt] = -1, dep[rt] = 0;
        std::queue<int> Q;
        Q.push(rt);
        for (int u; !Q.empty(); )
        {
            u = Q.front(); Q.pop();
            for (auto v : g[u])
                if (dep[v] == -1)
                    dep[v] = dep[u] + 1, Q.push(v), fa[v] = u;
        }
        return std::max_element(dep.begin(), dep.end()) - dep.begin();
    };
    int X = find(0);
    int Y = find(X);
    vector<int> a;
    for (int i = Y; i != -1; i = fa[i]) a.pb(i);
    vector<pii> ans;
    int d = a.size();
    if (d & 1)
    {
        int p = a[d / 2];
        for (int i = 0; i <= d / 2; i++)
            ans.pb({p, i});
    }
    else
    {
        int p = a[d / 2], q = a[(d - 1) / 2];
        for (int i = 1; i <= d / 2; i += 2)
            ans.pb({p, i}), ans.pb({q, i});
    }
    cout << ans.size() << '\n';
    for (auto [x, y] : ans) cout << x + 1 << ' ' << y << '\n';
}

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

F1

这是问题的简单版本。两个版本的唯一区别在于对 $n$ 的限制。只有两个版本的问题都解决了，才能进行破解。

一个由 $m$ 个非负整数组成的数组 $b$ 中，如果 $b$ 中的所有元素都可以通过下面的操作使其等于 $0$ ，那么这个数组就是好数组：

  • 选择两个不同的索引 $l$ 和 $r$ ( $1 \leq l \color{red}{<} r \leq m$ )，然后从所有 $b_i$ 中减去 $1$ 使得 $l \leq i \leq r$ .

给你两个正整数 $n$ ， $k$ 和一个质数 $p$ 。

在所有长度为 $n$ 的所有 $(k+1)^n$ 数组中，对于所有 $1 \leq i \leq n$ ，长度为 $0 \leq a_i \leq k$ 的数组有多少个？

由于这个数字可能太大，所以只要求求出取模 $p$ 的个数。

观察性质题又没找到性质哈哈

每次对 i 的操作必然包含了 i - 1 或 i + 1, 所以 i 能减到 0 的必要条件是 a[i] <= a[i - 1] + a[i + 1]

那么这是否是充分的呢？官方 editorial 里面有归纳法的证明。

不妨感性理解一下（）

设相邻的三个数为 abc，那么要满足 b <= a + c, 也就是 c >= b - a

f[a][b] 表示最后两个数分别是 a, b 的个数

那么 f[b][c] 就等于所有 b - a <= c 的 f[a][b] 之和

[Codeforces 1944F1] Counting Is Fun (Easy Version).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
#include <bits/stdc++.h>
using namespace std;
#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, k, p;
void solve()
{
    n = read(), k = read(), p = read();
    vector<vector<int>> f(k + 1, vector<int>(k + 1, 0));
    f[0][0] = 1;

    for (int i = 1; i <= n; i++)
    {
        vector<vector<int>> g(k + 1, vector<int>(k + 1, 0));
        // g 先存恰好 c = b - a 的，最后再求和
        for (int b = 0; b <= k; b++)
        {
            for (int a = 0; a <= k; a++)
            {
                int c = std::max(0LL, b - a);
                g[b][c] += f[a][b], g[b][c] %= p;
            }
            for (int j = 1; j <= k; j++)
                g[b][j] += g[b][j - 1], g[b][j] %= p;
        }
        f.swap(g);
    }

    int ans = 0;
    for (int a = 0; a <= k; a++)
        for (int b = 0; b <= a; b++)
            ans += f[a][b], ans %= p;
    cout << ans << '\n';
}

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

Codeforces Round 934 (Div. 2)

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

Author

TosakaUCW

Posted on

2024-03-17

Updated on

2024-04-08

Licensed under

#

Comments

Catalogue

×