文章导读

牛客集训第四场赛后总结

RonF02 2026年2月9日 89

今天牛客集训开了五道，因错误开题，导致来不及做（虽然没有开错题也不一定做得出），出现了一部分的知识盲区

A.八氏二分法

链接：https://ac.nowcoder.com/acm/contest/120564/A
来源：牛客网

老八提出了八氏二分法，在数组中，对于第 $x$ 个数字 $a_x$ ，如果其他数字中有至少 $80\%$ 的数字小于等于 $a_x$ ，则将第 $x$ 个数字分在 A 组，否则分在 B 组。
$\hspace{15pt}$ 求 A 组中的数字之和。

第一行输入一个正整数 𝑛(2≤𝑛≤1e3)，表示数组大小。
第二行输入 𝑛 个整数 𝑎1,𝑎2,…,𝑎𝑛(1≤𝑎𝑖≤1e3)，表示数组。

重点之一在于读懂题目，重点在于其他数字中，也就是排除本身，sort后要根据

\lceil (n – 1) * 0.8 \rceil

计算最小的下标，然后再用前缀和从这一项的后面一项开始逐个往前加

for (int i = n; a[i] >= a[ceil(0.8 * (n - 1)) + 1]; i -- ) ans += a[i];

for (int i = n; a[i] >= a[ceil(0.8 * (n - 1)) + 1]; i -- ) ans += a[i];

这样能够保证所有值等于a[符合条件的数]都计算进去。

好吧，其实这并不是什么思路很清楚的办法，根据官方题解，鉴于n的范围非常小，只有1e3，所以可以暴力枚举，O(n^2)的算法就足够解这道题了

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

int main() 
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) 
        cin >> a[i];
    
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        int cnt = 0; // 有多少个小于等于当前的数
        for (int j = 1; j <= n; j++) 
        {
            if (j == i) continue;
            if (a[j] <= a[i]) cnt++;
        }
        if (cnt * 10 >= (n - 1) * 8) sum += a[i]; // 计算是否大于80%
    }
    cout << sum << endl;
}

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

int main() 
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) 
        cin >> a[i];
    
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        int cnt = 0; // 有多少个小于等于当前的数
        for (int j = 1; j <= n; j++) 
        {
            if (j == i) continue;
            if (a[j] <= a[i]) cnt++;
        }
        if (cnt * 10 >= (n - 1) * 8) sum += a[i]; // 计算是否大于80%
    }
    cout << sum << endl;
}

思路非常简单

C 墨提斯的排列

链接：https://ac.nowcoder.com/acm/contest/120564/C
来源：牛客网

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 排列相邻位异或起来求和——和异位！
$\hspace{15pt}$ 萨莉亚——和意味！

$\hspace{15pt}$ 墨提斯想构造一个长度为 $2 ^ n$ 2n 的排列 $p_0,p_1,\ldots,p_{(2 ^ n – 1)}$ ，使得相邻两项异或值之和最小。换句话说，最小化：

$\displaystyle\sum\limits_{i = 1}^{2 ^ n – 1} \Big(p_{i-1} \oplus p_i\Big)$

$\hspace{15pt}$ 可以证明，最优解一定存在。

【名词解释】
$\hspace{15pt}$ 长度为 $n$ 的排列：由 $0,1,\ldots,n-1$ 这 $n$ 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如， $\{1,2,0,4,3\}$ 是一个长度为 $5$ 的排列，而 $\{0,1,1\}$ 和 $\{0,2,3\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。
$\hspace{15pt}$ $\oplus$ ：指位运算中的按位异或（Bitwise XOR），对两个整数的二进制表示按位进行异或运算。如果您需要更多位运算相关的知识，可以参考 OI-Wiki的相关章节。

输入描述:

 $\hspace{15pt}$ 输入一个正整数  $n \left(1 \leq n \leq 18\right)$ 。

输出描述:

 $\hspace{15pt}$ 在一行中输出  $2 ^ n$  个整数，表示构造的排列。

 $\hspace{15pt}$ 如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

题解

这道题有一个知识盲区——格雷码

格雷码有一个性质是：相邻两个数字在二进制中有且仅有一位不同。事实上，做题的时候根据这一点也可以做出来。

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

int main()
{
    int n; cin >> n;
    
    vector<int> available((1 << n), 1);
    int tmp = 0;
    available[0] = 0;
    
    for (int i = 0; i < (1 << n); i ++ )
    {
        cout << tmp << ' ';
        // for (auto i : available) cerr << i << ' ';
        // cerr << '\n';
        for (int i = 0; i < n; i ++ )
        {
            // cerr << (tmp ^ (1 << i)) << '\n';
            if (available[tmp ^ (1 << i)] == 1)
            {
                tmp = tmp ^ (1 << i);
                available[tmp] = 0;
                break;
            }
        }
    }
    
    
    
    return 0;
}

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

int main()
{
    int n; cin >> n;
    
    vector<int> available((1 << n), 1);
    int tmp = 0;
    available[0] = 0;
    
    for (int i = 0; i < (1 << n); i ++ )
    {
        cout << tmp << ' ';
        // for (auto i : available) cerr << i << ' ';
        // cerr << '\n';
        for (int i = 0; i < n; i ++ )
        {
            // cerr << (tmp ^ (1 << i)) << '\n';
            if (available[tmp ^ (1 << i)] == 1)
            {
                tmp = tmp ^ (1 << i);
                available[tmp] = 0;
                break;
            }
        }
    }
    
    
    
    return 0;
}

解题的时候写了这个O(n*2^n)的算法，通过标记实现仅改变一位二进制位的效果。实际上根据题解有O(2^n)的优美算法：

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

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < 1 << n; i++)
        cout << (i ^ (i >> 1)) << " ";
    cout << endl;
}

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

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < 1 << n; i++)
        cout << (i ^ (i >> 1)) << " ";
    cout << endl;
}

核心公式是

G_i​=i⊕(i>>1)

至于为什么正确，现在还不会证明

F 爱音的01串构造

考场没做出来，可能再多给一点时间也做不出，但也没有难到看不懂题解。直接贴题解。

#include<bits/stdc++.h>
using namespace std;
int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        int a, b;
        cin >> a >> b;
        string t;
        if (a == b) {
            for (int i = 1; i <= a; i++) {
                t += "10";
            }
        } else {
            char c0 = '0', c1 = '1';
            if (a < b) {
                swap(a, b);
                swap(c0, c1);
            }
            int x = a / (b + 1);
            int k = a % (b + 1);
            for (int i = 1; i <= b + 1; i++) {
                t += string(x + (k > 0), c0);
                if (k > 0) k -= 1;
                t += c1;
            }
            t.pop_back();
        }
        cout << t << endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        int a, b;
        cin >> a >> b;
        string t;
        if (a == b) {
            for (int i = 1; i <= a; i++) {
                t += "10";
            }
        } else {
            char c0 = '0', c1 = '1';
            if (a < b) {
                swap(a, b);
                swap(c0, c1);
            }
            int x = a / (b + 1);
            int k = a % (b + 1);
            for (int i = 1; i <= b + 1; i++) {
                t += string(x + (k > 0), c0);
                if (k > 0) k -= 1;
                t += c1;
            }
            t.pop_back();
        }
        cout << t << endl;
    }
}

就先开到mid为止吧

查看评论列表

暂无评论

发表评论取消回复

访客未填写邮箱

[填写昵称邮箱后可以评论]

是先学算法，先刷题，还是先写日记呢？

加载中

牛客集训第四场赛后总结

A.八氏二分法

C 墨提斯的排列

题目描述

输入描述:

输出描述:

题解

F 爱音的01串构造

评论（0）

发表评论取消回复

插入代码

RonF02的博客

搜索

归档

个人信息

是先学算法，先刷题，还是先写日记呢？

加载中

牛客集训第四场赛后总结

A.八氏二分法

C 墨提斯的排列

题目描述

输入描述:

输出描述:

题解

F 爱音的01串构造

评论（0）

发表评论 取消回复

插入代码

RonF02的博客

搜索

归档

个人信息

发表评论取消回复