牛客寒假训练营-2

约 635 字大约 2 分钟

2026-02-06

Preface

全是 ad-hoc，脑子不够用了真的 qwq。

A. 比赛安排（PDF题面存放于本题）

签到思维

考虑每连续的 3 场要不同，所以不难发现 $\max\{a,b,c\}-\min\{a,b,c\}\leqslant 1$ 符合安排条件。

A.cc
#include <bits/stdc++.h>
using namespace std;

void sol()
{
    int a, b, c;
    cin >> a >> b >> c;
    int maxs = max({a, b, c});
    int mins = min({a, b, c});
    if (maxs - mins > 1)
    {
        cout << "NO";
    }
    else
    {
        cout << "YES";
    }
    cout << "\n";
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        sol();
    }
    return 0;
}

单组复杂度 $O(1)$ 。

B. NCPC

思维

如果最大的是偶数个，那就是比他少的肯定可以胜利，如果最大的是奇数个，那就是最大的必胜，其余全是 0。

B.cc
#include <bits/stdc++.h>
using namespace std;

void sol()
{

    int n;
    cin >> n;
    vector<int> vi(n);
    int maxs = -1;
    for (int i = 0; i < n; i++)
    {
        cin >> vi[i];
    }
    for (int i = 0; i < n; i++)
    {
        maxs = max(maxs, vi[i]);
    }

    int mcnt = 0;
    for (int i = 0; i < n; i++)
    {
        if (vi[i] == maxs)
            mcnt++;
    }

    for (int i = 0; i < n; i++)
    {
        if (vi[i] == maxs && mcnt % 2 == 1)
        {
            cout << 1;
        }
        else if (vi[i] != maxs && mcnt % 2 == 0)
        {
            cout << 1;
        }
        else
        {
            cout << 0;
        }
    }
    cout << "\n";
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        sol();
    }
    return 0;
}

单组复杂度 $O(n)$ 。

C. 炮火轰炸

二分并查集

把每一个炮火点附近的八个点全部存起来，WIP.

D. 数字积木

树形 dp

WIP.

E. 01 矩阵

ad-hoc 构造

很简单......吗

考虑矩阵 $n=6$ ，行从 $1\sim n-1$ 列从 $1\sim n-1$ ，对于 $(i, j)$ 的答案为 $\min(i,j) ~ \& ~ 1$ 。

可行的构造方案

E.cc
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void sol() {}
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << (min(i, j) & 1);
        }
        cout << "\n";
    }
    return 0;
}