AC手记

记录从暴力到最优的每一步

0%

2026牛客寒假集训营第二场比赛实况及题解

发表于 更新于 分类于 6.6k 6 分钟

2026牛客寒假集训营第二场比赛实况及题解

比赛实况

本场A、B、F、I题较为简单，本人依旧前期展示手速，$38min$$2$罚时迅速解决。但是却被H题卡了好久，最终还是没能做出来。不得不说，H题是很经典的拆贡献计数题，其中可能用到了一定的动态规划思想，我这方面似乎比较薄弱，之前CF、Atc或牛客周赛遇到这类题基本很难做出来，所以可能需要这方面的特训。不过这次很值得一题的是，今天本人成功当了一回构学长，在E题只有$200$人通过时，通过不停手玩成功构造出答案，直接一发通过，加上前期手速的优势，使我本场虽然没能成功做出$6$题，但是因为罚时的优势导致排名较高，算是近期的一次比价好的成绩。希望自己后面再接再厉，继续保持今天的状态吧。此外一些经典模型记得要多加训练，这样能很大程度上提高自己的下限（实际上今天如果E没构造出来就炸了）。

题解

A.比赛安排

题目大意是说有三种类型的比赛，分别有$a$,$b$,$c$场，问是否存在安排方案使连续三场的比赛类型互不相同。那么显然只有当不同类型的比赛数量最多相差$1$的时候才存在这样的安排方案，因此我们只需要通过给定三个数的最大值和最小值之差判断即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void moth()
{
    ll a, b, c;
    cin >> a >> b >> c;
    if (a > b)
        swap(a, b);
    if (a > c)
        swap(a, c);
    b -= a;
    c -= a;
    if (b > 1 || c > 1)
        cout << "NO\n";
    else
        cout << "YES\n";
}

B.NCPC

题目大意是说总共$n$名选手进行比赛，每个选手有一个美味值$a_i$，每次会随机选两名选手进行比赛，如果美味值相等，则两个人都淘汰，否则美味值较低的淘汰，问对于$1\leq i \leq n$，是否存在一种比赛安排使得$i$获胜。

首先，如果一种美味值出现的次数为偶数，那么他们是可以互相抵消的。那么我们可以看最大值出现次数的奇偶性，如果是偶数，就意味着，除了自身之外，其他数字都可以被他们淘汰，所以此时除了他们本身之外，其它任何数都存在一种可以获胜的方案；如果最大值个数为奇数，那没有数字能淘汰掉最大值，最大值必然在最后会剩下至少一个，并且淘汰掉所有其它数字，所以此时除了最大值本身，其他数字均没有获胜的方案。

代码如下（写的有点麻烦）：

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
void moth()
{
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    map<ll, ll> cnt;
    ll mx = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        cnt[a[i]]++;
        mx = max(mx, a[i]);
    }
    if (cnt.size() == 1)
    {
        if (cnt[mx] % 2 == 0)
        {
            for (int i = 1; i <= n; i++)
                cout << 0;
            cout << '\n';
        }
        else
        {
            for (int i = 1; i <= n; i++)
                cout << 1;
            cout << '\n';
        }
    }
    else
    {
        if (cnt[mx] % 2 == 0)
        {
            for (int i = 1; i <= n; i++)
            {
                if (a[i] == mx)
                    cout << 0;
                else
                    cout << 1;
            }
            cout << '\n';
        }
        else
        {
            for (int i = 1; i <= n; i++)
            {
                if (a[i] == mx)
                    cout << 1;
                else
                    cout << 0;
            }
            cout << '\n';
        }
    }
}

E.01矩阵

题目大意是要求我们构造一个仅由$0$和$1$构成的$n$阶矩阵，满足以下三个条件：

  • 设每一行的元素为$row_i$，要求$0\leq row_i \leq n-1$，且每个数字只出现一次
  • 设每一列的元素为$col_i$，要求$0\leq col_i \leq n-1$，且每个数字只出现一次
  • $0$和$1$组成的连通块个数之和为$n$

构造题没有通用解法，只能靠注意力和手玩。本人的构造方法是：先处理出$1$.$2$,$3$的情况，然后后续就是在前一个的左侧以"L"型交替填写$1$或$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
void moth()
{
    vector<vector<int>> a(1001, vector<int>(1001));
    a[1][1000] = a[3][999] = a[3][1000] = 1;
    a[1][999] = a[1][998] = a[2][998] = a[2][999] = a[2][1000] = a[3][998] = 0;
    int st = 0;
    for (int c = 997; c >= 1; c--)
    {
        st = c % 2;
        int sz = 1000 - c + 1;
        int len = sz - st;
        for (int i = 1; i <= len; i++)
            a[i][c] = st;
        if (len == sz)
        {
            for (int i = 1000 - sz + 2; i <= 1000; i++)
                a[sz][i] = st ^ 1;
        }
        else
        {
            for (int i = 1000 - sz + 1; i <= 1000; i++)
                a[sz][i] = st ^ 1;
        }
    }
    int n;
    cin >> n;
    if (n == 1)
    {
        cout << 0 << '\n';
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1000 - n + 1; j <= 1000; j++)
            cout << a[i][j];
        cout << '\n';
    }
}

F.x?y?n!

题目要求构造两个不同的数$x$和$y$，在满足$\gcd(x,y)=n$的前提下使得$x\oplus y$的值最小。

因为$|x-y|\leq x \oplus y$，$\gcd(x,y)=n$且$x\neq y$，所以$x$和$y$是$n$的不同倍数。则$|x-y|$至少是$n$的$1$倍，即$n\leq |x-y| \leq x \oplus y$，所以此时$x \oplus y$的最小值为$n$。

那么接下来我们考虑如何构造：首先将$n$左移得到的数一定会是$n$的倍数，将这个数加上$n$（或者按位或）之后的结果也一定是$n$的倍数。假设$n$的二进制形式有$bit$位，那么我们将$n$左移$bit$位，再加上$n$（或者按位或），那么这两个数的最大公约数一定为$n$，并且它们的前$bit$位按位异或之后均为$0$，后$bit$位按位异或后得到$n$，此时满足了$x \oplus y=n$。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void moth()
{
    ll n;
    cin >> n;
    ll bit = 0;
    ll c = n;
    while (c)
    {
        c /= 2;
        bit++;
    }
    // cout << bit << '\n';
    cout << (n << bit) << ' ' << ((n << bit) | n) << '\n';
}

H.权值计算

题目定义一个数组的权值为其所有前缀中不同元素的个数的总和，求所有非空子数组的权值之和。

由于子数组有$n^2$个，所以我们可以直接考虑每个元素对子数组的贡献。对于$i$位置，包括$a_i$的子数组$[l,r]$，显然满足：$l \leq i \leq r$ 。并且只有当$a_i$在子数组中第一次出现时才会增加不同元素的个数，所以此时我们假设$a_i$上一次出现的位置为$j$，则当$j < l \leq i$时$a_i$都是新元素，此时左端点有$i-j$种选择。再考虑$a_i$对当前子数组的贡献，从以$i$为结尾的前缀开始，到以$r$为结尾的前缀，$a_i$都会产生贡献，所以一共产生了$r-i+1$次贡献。又因为$r\in[i,n]$，所以总共产生了$\frac{(1+n-i+1)(n-i+1)}{2}$次贡献（等差数列求和），考虑上左端点的选择个数，则每个$a_i$对答案的贡献为$(i-j) \frac{(1+n-i+1)(n-i+1)}{2}$。最后对每个$a_i$都进行这样的计算，再累加求和即可、

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void moth()
{
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    map<ll, ll> pre;
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (pre.find(a[i]) == pre.end())
            ans += 1ll * i * (1 + (n - i + 1)) * (n - i + 1) / 2;
        else
            ans += 1ll * (i - pre[a[i]]) * (1 + (n - i + 1)) * (n - i + 1) / 2;
        pre[a[i]] = i;
    }
    cout << ans << '\n';
}

I.01回文

题目大意是给了一个$n \times m$的仅由$0$和$1$组成的矩阵，每次可以走与当前位置曼哈顿距离为$1$的点，问对于矩阵中的每个点是否存在一条路径使经过的数字组成的字符串是回文的。

实际上，只有当矩阵中只有一个"$1$"，其余都是"$0$"；或者只有一个"$0$",其余都是"$1$"时该位置找不到回文路径，所以直接统计矩阵中"$1$"的数量即可。

代码如下：

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
void moth()
{
    int n, m;
    cin >> n >> m;
    int one = 0;
    vector<vector<char>> a(n + 1, vector<char>(m + 1)), ans(n + 1, vector<char>(m + 1));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            if (a[i][j] == '1')
                one++;
        }
    }
    if (one == 1)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (a[i][j] == '1')
                    ans[i][j] = 'N';
                else
                    ans[i][j] = 'Y';
            }
        }
    }
    else if (one == n * m - 1)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (a[i][j] == '0')
                    ans[i][j] = 'N';
                else
                    ans[i][j] = 'Y';
            }
        }
    }
    else
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
                ans[i][j] = 'Y';
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            cout << ans[i][j];
        cout << '\n';
    }
}

J.终于再见

题目将所有的点按度数分等级，要求出每个点到等级严格高于它的点的最短距离。

我们在图论中学过，所有点的度数之和等于边数的两倍，那么就意味着，在$m$条边的情况下，所有的点最多被分为$O(\sqrt{m})$个等级。那么我们可以枚举每个等级，将所有等级高于它的点进行多源$BFS$来找到最小值，并且只对当前等级的点更新即可。时间复杂度为$O(\sqrt{m}(n+m))$。

代码如下：

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
void moth()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1);
    vector<ll> deg(n + 1), ans(n + 1, -1);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }
    vector<ll> X;
    for (int i = 1; i <= n; i++)
        X.push_back(deg[i]);
    sort(X.begin(), X.end());
    X.erase(unique(X.begin(), X.end()), X.end());
    int k = X.size();
    vector<vector<ll>> node(k + 1);
    for (int i = 1; i <= n; i++)
    {
        int t = lower_bound(X.begin(), X.end(), deg[i]) - X.begin() + 1;
        node[t].push_back(i);
    }
    for (int i = 1; i <= k; i++)
    {
        queue<int> q;
        vector<ll> d(n + 1, 1e18);
        for (int j = i + 1; j <= k; j++)
        {
            for (auto x : node[j])
            {
                q.push(x);
                d[x] = 0;
            }
        }
        while (q.size())
        {
            int x = q.front();
            q.pop();
            for (auto y : g[x])
            {
                if (d[y] != 1e18)
                    continue;
                d[y] = d[x] + 1;
                q.push(y);
            }
        }
        for (auto x : node[i])
        {
            if (d[x] != 1e18)
                ans[x] = d[x];
        }
    }
    for (int i = 1; i <= n; i++)
        cout << ans[i] << ' ';
}