mobile wallpaper 1
Profile Image of the Author
Hycode
Announcement
欢迎来到我的博客！这里分享我的个人生活与学习日常！
标签
964 字
2 分钟
牛客周赛 Round 128
2026-01-27
题解
牛客
/
牛客周赛

☁️体验#

简单到我差点 AK 的一场周赛。

💡题解#

A - 小红的双层夹心#

题意#

给你一个长度为 44 的字符串，判断中间两个字符是否相同。

思路#

直接判断即可。

代码#

void solve()
{
    string s;
    cin >> s;


    if(s[1] == s[2]) Yes;
    else No;
}

B - 小红的马卡龙定位#

题意#

给你 33 个点的坐标 (x1,y1)(x_1, y_1)，(x2,y2)(x_2, y_2)，(x3,y3)(x_3, y_3)。

已知三点位于同一条直线上，判断第几个点是中点。

思路#

根据中点公式 xmid=x1+x22x_{mid} = \frac{x_1 + x_2}{2}，ymid=y1+y22y_{mid} = \frac{y_1 + y_2}{2}，判断第几个点是中点即可。

如果三点 xx 坐标相同，就通过 yy 坐标判断，反之通过 xx 坐标判断即可。

代码#

void solve()
{
    int a, b, c, x, y, z;
    cin >> a; cin >> x;
    cin >> b; cin >> y;
    cin >> c; cin >> z;


    auto f = [&](int a, int b, int c) -> void
    {
        if(a + b == 2 * c) D(3);
        else if(a + c == 2 * b) D(2);
        else D(1);
    };


    if(a == b && b == c) f(x, y, z);
    else f(a, b, c);
}

C - 小红的奶油蛋糕工坊#

题意#

给你一个长度为 nn 的排列 aa。

你需要改变 aa 中的一些元素，使得 aa 中的元素至少有 ⌈n2⌉\lceil \frac{n}{2} \rceil 个相同。

你需要尽可能使总的改变量最少，即使 ∑i=1n∣Δai∣\sum_{i=1}^n |\Delta a_i| 最小。

输出最终的 aa。

思路#

很容易想到，我们把前 ⌈n2⌉\lceil \frac{n}{2} \rceil 小的元素，即 11 ~ ⌈n2⌉\lceil \frac{n}{2} \rceil ，都改为 ⌈⌈n2⌉2⌉\lceil \frac{\lceil \frac{n}{2} \rceil}{2} \rceil 就好了。

⌈⌈n2⌉2⌉\lceil \frac{\lceil \frac{n}{2} \rceil}{2} \rceil 是 11 ~ ⌈n2⌉\lceil \frac{n}{2} \rceil 的中位数，选取中位数可以保证改变量最小。

何意味🧐

至于同一题为什么要用 / 2 和 >> 1 两种写法…

赛时写完这坨代码给我自己整乐了。大概是因为平时写二分总是用 mid = (l + r) >> 1，所以写完 mid 之后就习惯性顺手写 (...) >> 1 了。

代码#

void solve()
{
    input(n, a);
    int cnt = (n + 1) / 2;
    int mid = (cnt + 1) >> 1;
    for(int& i : a)
        if(i <= cnt) i = mid;
    vD(a);
}

D - 小红的奇数奶油球#

题意#

给你一颗树，如果删除一个点，剩余的每一个部分的节点数都是奇数，那么这个点就是一个奇数奶油球。

问你这棵树中有多少个奇数奶油球。

思路#

输入顺序可能不是拓扑的，先当无向图读进来，然后以 11 为根建树。

我一开始看样例全是按顺序输入的，就直接当有向图整了，WA 了一发🤣

然后以 11 为起点跑一遍 DFSDFS，同时记录每个点的子树大小。

判断一个节点 ii 是否是奇数奶油球，只需要判断它的子树大小是否都为奇数即可。

如果这个点不是根节点，还得判断它上方的部分是否是奇数，我们可以通过 n−d[i]n - d[i] 得出上方的部分大小。

代码#

void solve()
{
    int n;
    cin >> n;


    vector<vector<int>> g(n + 1);
    for(int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }


    vector<vector<int>> t(n + 1);
    function<void(int, int)> build = [&](int x, int fa) -> void
    {
        for(int i : g[x])
            if(i != fa)
            {
                t[x].push_back(i);
                build(i, x);
            }
    };


    build(1, 0);


    vector<int> d(n + 1);


    function<int(int)> dfs = [&](int x) -> int
    {
        int ret = 1;
        for(auto& i : t[x])
            ret += dfs(i);
        d[x] = ret;
        return ret;
    };


    dfs(1);


    int ans = 0;


    for(int i = 1; i <= n; i++)
    {
        if(i != 1)
        {
            int k = n - d[i];
            if(k % 2 == 0) continue;
        }


        bool ok = true;


        for(auto& j : t[i])
            if(d[j] % 2 == 0)
            {
                ok = false;
                break;
            }


        if(ok) ans++;
    }


    D(ans);
}

E - 小红的提拉米苏配方（easy）#

题意#

给你一个字符串 ss，包含 00，11，22 三种字符。

每次操作，你需要选取两个 11，把其中一个 11 删掉，另一个变成 22。

操作持续到无法继续操作为止。

输出字典序最大的结果。

思路#

很明显，把 22 放后面总是要好一些。

设 ss 中 11 的个数为 mm。

  • 如果 mm 是偶数，那么就把前 m2\frac{m}{2} 个 11 都删掉，把后面的 11 都变成 22。

  • 如果 mm 是奇数：

    • 首先，后 m2\frac{m}{2} 个 11 都是要变成 22 的；
    • 对于前面的 11，我们总是要留下一个。我们从左往右遍历，把遇到的第一个右边是 22 的 11 保留下来。如果没有找到，就把最后一个 11 保留下来。

代码#

void solve()
{
    string s;
    cin >> s;


    int n = s.size();


    vector<int> p;
    for(int i = 0; i < n; i++)
        if(s[i] == '1')
            p.push_back(i);


    if(p.size() <= 1)
    {
        D(s);
        return;
    }


    int m = p.size();
    for(int i = (m + 1) / 2; i < m; i++)
        s[p[i]] = '2';


    bool keep = m % 2 == 0;
    int i = 0;
    for( ; i < (m + 1) / 2; i++)
        if(!keep && s[p[i] + 1] == '2')
            keep = true;
        else s[p[i]] = '#';


    if(!keep) s[p[i - 1]] = '1';


    for(char& c : s)
        if(c != '#')
            cout << c;
}

F - 小红的提拉米苏配方 （hard）#

题意#

和 EasyEasy VersionVersion 的区别是，你可以自己决定什么时候停止操作。

思路#

我们要尽可能让 00 往前移，同时要注意 00 往前移的时候不能让 22 往前移。

和 EasyEasy VersionVersion 一样，我们把最后的 11 变成 22 总是要好一些。

如果 si=s_i = '00'，那么从这个位置往前走，直到遇到的第一个 22 的位置，这段区间内的 11 都是可以删除的。

最后，在删除的同时，维护最后的 11 的位置即可。

代码#

void solve()
{
    string s;
    cin >> s;


    int n = s.size();


    vector<int> p;
    for(int i = 0; i < n; i++)
        if(s[i] == '1')
            p.push_back(i);


    int l = 0, r = p.size() - 1;


    if(p.size() < 2)
    {
        D(s);
        return;
    }


    int p2 = -1;
    for(int i = 0; i < n; i++)
    {
        if(s[i] == '1') continue;


        if(s[i] == '2') p2 = i;
        else if(s[i] == '0')
        {
            int dl = p2 == -1 ? 0 : p2;
            int dr = i;


            while(l < r && p[l] < dl) l++;


            while(l < r && p[l] < dr)
            {
                if(p[r] < dr) break;
                s[p[l++]] = '#';
                s[p[r--]] = '2';
            }
        }
    }


    for(char& c : s)
        if(c != '#')
            cout << c;
}

🎈模板#

头文件#

#include <bits/stdc++.h>
#define inf INT_MAX
#define INF LLONG_MAX
#define MOD 1000000007
#define mod 998244353
#define all(_x) _x.begin(), _x.end()
#define vcin(_x) for(auto& _i : _x) cin >> _i
#define vvcin(_x) for(auto& _j : _x) for(auto& _i : _j) cin >> _i
#define D(_x) cout << _x << endl
#define vD(_x) for(int _i = 0; _i < _x.size(); ++_i) cout << _x[_i] << " \n"[_i == _x.size() - 1]
#define input(_n, _a) int _n; cin >> _n; vector<int> _a(_n); vcin(_a)
#define flr(_i, _l, _r) for(int _i = _l; _i <= _r; ++_i)
#define frl(_i, _r, _l) for(int _i = _r; _i >= _l; --_i)
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define yes cout << "yes" << endl
#define no cout << "no" << endl
using namespace std;


#define int long long
#define endl '\n'


void solve()
{


}


signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
cin >> _;
    while (_--)
        solve();
    return 0;
}
分享

如果这篇文章对你有帮助，欢迎分享给更多人！

牛客周赛 Round 128
https://blog.hycode.qzz.io/posts/nk-weekly-128/post/
作者
Hycode
发布于
2026-01-27
许可协议
CC BY-NC-SA 4.0

部分信息可能已经过时

牛客周赛 Round 131
Codeforces Round 1074 (Div. 4)
相关文章 智能推荐
1
牛客周赛 Round 145
题解 牛客周赛 Round 145 题解
2
牛客周赛 Round 140
题解 牛客周赛 Round 140 题解
3
牛客周赛 Round 134
题解 牛客周赛 Round 134 题解
4
牛客周赛 Round 131
题解 新年快乐！
5
牛客周赛 Round 127
题解 较为简单的一场周赛
随机文章 随机推荐
1
牛客周赛 Round 140
题解 2026-04-19
2
Codeforces Round 1072 (Div. 3)
题解 2026-01-15
3
牛客周赛 Round 134
题解 2026-03-09
4
牛客周赛 Round 127
题解 2026-01-19
5
牛客周赛 Round 145
题解 2026-05-25
© 2026 Hycode. All Rights Reserved. / RSS / Atom / Sitemap
Powered by Astro & Mizuki  Version 9.0

目录