2026 牛客寒假算法基础集训营 1 题解

B 题：贪心、思维、数学

题意

两人各持 n 张牌，共 2n 张牌构成排列。游戏过程为比较双方当前最大牌，大者得分并弃牌，小者保留。小苯可重排自己的牌以最大化得分。

思路

只要手中大于对方最小值的牌都可以得分。策略是将大于对方最小值的牌排在前方，小于对方最小值的牌排在后方。方案数为两个组合数相乘。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
const int mod = 998244353;
int a[N], n, b[N];
long long fact[N];

void preprocess() {
    fact[0] = 1;
    for (int i = 1; i <= N; ++i) {
        fact[i] = fact[i - 1] * i % mod;
    }
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    sort(b + 1, b + 1 + n);
    int k = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] > b[1]) k++;
    }
    long long ans = fact[k] * fact[n - k] % mod;
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    preprocess();
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

C 题：签到

题意

简单题目，直接输出答案即可。

D 题：二分、贪心

题意

给定序列包含白色和黑色数字。初始可选择 k 个白数字染红，每秒红色数字会将其右侧 x 个数字里的白色数字染红。求将所有白色数字染红的最短时间。

思路

答案具有单调性，可二分时间 x。使用 check 函数模拟染色过程，从左往右贪心，维护已染色数量和最远覆盖位置。注意跳过黑色方块。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int a[N];
int pre[N];

void solve() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        int now = 0;
        if (a[i]) now = min(i + a[i] + 1, n);
        pre[i + 1] = max(now, pre[i]);
    }
    auto check = [&](int x) {
        int cur = 0;
        while (cur < n && !a[cur]) cur++;
        for (int i = 0; i < k && cur < n; i++) {
            cur++;
            for (int j = 0; j < x && pre[cur] > cur; j++) {
                cur = pre[cur];
            }
            while (cur < n && !a[cur]) cur++;
        }
        return cur == n;
    };
    int lo = 0, hi = n;
    while (lo < hi) {
        int x = (lo + hi) / 2;
        if (check(x)) hi = x;
        else lo = x + 1;
    }
    if (lo == n) lo = -1;
    cout << lo << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

E 题：枚举、贪心

题意

有 n 个小方块，第 i 个数字为 ai，另有一个万能方块数字为 1。可将万能方块从左侧插入，其余后移，末尾变为新万能方块。最大化第一个方块数字 + 万能方块数字。

思路

万能方块与第一个数字相邻。遍历所有相邻数字对，找到最大和即可。

G 题：按位贪心

题意

给定区间 [L, R]，定义 f(x) 为 x 十进制翻转后去除前导 0 的值。求区间内 f(x) 的最大值。

思路

1. 位数不同时优先选高位多的（特殊情况 r=10^k 除外）。
2. 位数相同时，公共前缀无法改变，照抄。
3. 剩余位数按位贪心，第一个不同位减 1，后续填 9。

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

void solve() {
    string L, R;
    cin >> L >> R;
    int nl = L.size(), nr = R.size();
    int l = stoll(L), r = stoll(R);
    string t = "1";
    for (int i = 0; i < nr - 1; i++) t += '0';
    if (R == t) {
        if (L == R) cout << 1 << '\n';
        else cout << r - 1 << '\n';
        return;
    }
    if (nl < nr) {
        L = t;
        L.back() += 1;
        assert(L.size() == R.size());
    }
    string ans;
    int k = -1;
    for (int i = 0; i < nr; i++) {
        if (L[i] != R[i]) {
            k = i;
            break;
        }
    }
    if (k == -1) {
        ans = L;
        while (ans.size() > 1 && ans.back() == '0') ans.pop_back();
        reverse(ans.begin(), ans.end());
    } else {
        bool flag = 1;
        for (int i = k + 1; i < nr; i++) {
            ans += '9';
            flag &= (R[i] == '9');
        }
        ans += (R[k] - !flag);
        for (int i = k - 1; i >= 0; i--) ans += L[i];
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

H 题：位或运算、前缀和优化 DP、计数

题意

给定序列 a，问有多少种方式将加号替换为位或运算符，使得运算式值不变。

思路

使用 DP 结合前缀和优化。记录上一次出现某位的索引，利用前缀和快速转移。

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    int lst = 0;
    vector<int> pre(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = lst;
        if (a[i] > 0) lst = i;
    }
    vector<int> dp(n + 2);
    vector<int> s(n + 2);
    dp[1] = 1;
    s[1] = 1;
    for (int i = 1; i <= n; i++) {
        int j = i;
        int val = 0;
        while (j > 0 && (val & a[j]) == 0) {
            val |= a[j];
            j = pre[j];
        }
        dp[i + 1] = (s[i] - s[j] + mod) % mod;
        s[i + 1] = (s[i] + dp[i + 1]) % mod;
    }
    cout << dp[n + 1] << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

I 题：位运算、构造、贪心

题意

给定区间 [l, r]，可选若干数字进行 AND 操作加入集合 S，求 S 的 MEX 最大值。

思路

1. l=0 时答案为 r+1。
2. 最高位相同则答案为 0。
3. 最高位相差两位及以上，答案为 r+1。
4. 最高位差 1 时，需判断特定区间交集情况。

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

void solve() {
    int l, r;
    cin >> l >> r;
    auto highbit = [&](int x) {
        for (int i = 32; i >= 0; i--) {
            if ((x >> i) & 1) return i;
        }
        return -1;
    };
    int b1 = highbit(l), b2 = highbit(r);
    if (b1 == -1) {
        cout << r + 1 << '\n';
    } else if (b1 == b2) {
        cout << 0 << '\n';
    } else if (b2 > b1 + 1) {
        cout << r + 1 << '\n';
    } else {
        int ans = r - (1LL << b2) + 1;
        int L = 0;
        for (int i = b1; i >= 0; i--) {
            if (!((l >> i) & 1)) break;
            else L |= (1 << i);
        }
        if (L <= ans) ans = r + 1;
        cout << ans << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

K 题：签到、构造

题意

构造字典序最小的长度为 n 的正整数数组，满足互不相同且和等于积。

思路

经尝试发现仅 n=1 和 n=3 符合。

L 题：签到

题意

简单题目，直接输出答案即可。