题解 | 2026牛客寒假算法基础集训营1(ABCDEGHIKL)

A+B Problem

https://ac.nowcoder.com/acm/contest/120561/A

由于牛客的渲染问题,你可以点此链接进入我的博客查看

个人难度评级

签到:

简单:

中等:

困难:

A A+B Problem

简单的模拟数学题,先求每个数字 被点亮的概率 ,再求 中每一个数字 被点亮的概率

最后满足 的概率即为

int num[] = {0b1110111, 0b0100100, 0b1011101, 0b1101101, 0b0101110, 0b1101011, 0b1111011, 0b0100101, 0b1111111, 0b1101111};

void solve() {
    int C;
    cin >> C;
    vector<Z> p(7);
    for (int i = 0; i < 7; ++i)
        cin >> p[i], p[i] /= 100;
    vector<Z> q(10, 1);
    for (int i = 0; i <= 9; ++i) {
        auto msk = num[i];
        for (int j = 0; j < 7; ++j) {
            if (msk & (1 << j))
                q[i] *= p[j];
            else
                q[i] *= 1 - p[j];
        }
    }
    vector<Z> P(10000);
    for (int a = 0; a < 10; a++) {
        if (q[a] == 0)
            continue;
        for (int b = 0; b < 10; b++) {
            if (q[b] == 0)
                continue;
            for (int c = 0; c < 10; c++) {
                if (q[c] == 0)
                    continue;
                for (int d = 0; d < 10; d++) {
                    if (q[d] == 0)
                        continue;
                    int N = a * 1000 + b * 100 + c * 10 + d;
                    P[N] = q[a] * q[b] * q[c] * q[d];
                }
            }
        }
    }
    Z ans = 0;
    for (int i = 0; i <= C; ++i) {
        int j = C - i;
        if (C >= 0)
            ans += P[i] * P[j];
    }
    cout << ans << endl;
}

B Card Game

如果记 ,那么只要大于 的牌就一定能得分,小于 的牌一定不能得分。并且这张牌如果小于 ,它就无法战胜 中的任何一张牌,于是他会把 的所有牌都消耗掉,使得它后面的所有牌都无法得分。所以我们把 的牌分成两类,一类大于 ,一类小于 。先用大于 的牌把所有能拿的分都拿到,然后小于 的牌放在那不管就行。

记大于 的牌有 张,最后的答案为

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    int mn = inf;
    for (int i = 0, x; i < n; ++i)
        cin >> x, mn = min(mn, x);
    int k = 0;
    for (auto v : a)
        k += v >= mn;
    cout << C.fac(k) * C.fac(n - k) << endl;
}

C Array Covering

我们可以用最大的数 尽可能覆盖所有数字,由于边界不会被覆盖,所以最后的答案为

注意数据范围

void solve() {
    int n;
    ll mx = -1;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    cout << 1ll * mx * (n - 2) + a[0] + a[n - 1] << endl;
}

D Sequence Coloring

显然如果时间 可行,则 ​ 也可行。不难想到我们可以使用二分。

覆盖显然是贪心的,第一个种子必须覆盖第一个白色元素;假设前一个种子覆盖到了第 个白色元素,那么下一个种子应该放在第 个白色元素处,并尽可能向右延伸。

但是模拟处理染色扩散的过程太慢,所以我们用倍增数组 表示从前缀 出发,经过 秒能够覆盖的最远白色元素的下标, 就是 所有元素单步能到的最远位置的最大值,

对于二分的 ,我们初始令 ,表示没有元素被覆盖。每次使用一个种子,放在 的位置。由于已经覆盖了 ,我们可以利用倍增数组从 跳跃 ​ 步。

constexpr int LOGN = 20;

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

    vector<int> a(n + 1), pos;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        if (a[i] > 0) {
            pos.pb(i);
        }
    }

    int m = pos.size();
    if (m == 0 || k >= m) {
        cout << 0 << endl;
        return;
    }

    vector<int> nxt(m + 1);
    for (int i = 1; i <= m; ++i) {
        ll lim = pos[i - 1] + a[pos[i - 1]];
        int idx = upper_bound(all(pos), lim) - pos.begin();
        nxt[i] = max(i, idx);
    }

    vector<vector<int>> up(LOGN, vector<int>(n + 1));
    up[0][0] = 0;
    for (int i = 1; i <= m; ++i) {
        if (i == 1)
            up[0][i] = nxt[i];
        else
            up[0][i] = max(up[0][i - 1], nxt[i]);

        if (up[0][i] > m)
            up[0][i] = m;
    }

    for (int j = 1; j < LOGN; ++j) {
        for (int i = 1; i <= m; ++i) {
            up[j][i] = up[j - 1][up[j - 1][i]];
        }
    }

    auto check = [&](int t, int m) -> bool {
        int cur = 0, sds = 0;

        while (cur < m) {
            sds++;
            if (sds > k)
                return false;

            int node = cur + 1;

            for (int j = LOGN - 1; j >= 0; --j) {
                if ((t >> j) & 1) {
                    node = up[j][node];
                }
            }

            cur = node;
        }
        return true;
    };

    int lo = 0, hi = n, ans = -1;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (check(mid, m)) {
            ans = mid;
            hi = mid - 1;
        } else
            lo = mid + 1;
    }

    cout << ans << endl;
}

E Block Game

我们直接把万能方块看作整个序列的最后一个元素,不难发现,第一个数字和万能方块只会是相邻的元素(将序列看成一个环)。

constexpr int inf = 1e9 + 7;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    a.pb(k);
    int mx = a[0] + a[n];
    for (int i = 1; i <= n; ++i)
        mx = max(mx, a[i] + a[i - 1]);
    cout << mx << endl;
}

G Digital Folding

我们考虑去枚举长度,对于每一个长度 ,取 和这个长度对应的区间取交集,得到当前的有效区间 。因为我们需要反转后的数字尽可能大,所以从低位向高位贪心。我们从右往左逐位尝试放数字 得到后缀 ,然后检查是否存在一个数 ,使得 的后缀等于当前构造的后缀,也就是检查同余方程 是否有解( ​ 是当前尝试的位 )。如果有解,说明这一位可以填 ,记录 ,更新后缀值,并跳出当前位的枚举;否则继续尝试更小的

然后比较所有长度下的最大折叠数即为答案。

vector<ll> P(20);

void init() {
    P[0] = 1;
    for (int i = 1; i < 20; ++i)
        P[i] = P[i - 1] * 10;
}

void solve() {
    ll l, r;
    cin >> l >> r;
    ll ans = 0;

    auto rev = [&](ll x) {
        string s = to_string(x);
        reverse(all(s));
        return stoll(s);
    };
    auto siz = [&](ll x) {
        return to_string(x).size();
    };

    for (int t = 0; t < 19 && P[t] <= r; ++t) {
        ll p = P[t];
        ll A = (l + p - 1) / p, B = r / p;
        if (B <= 0)
            continue;
        if (A <= 0)
            A = 1;
        if (A > B)
            continue;

        unordered_set<ll> st;

        auto add = [&](ll x) {
            if (x < A || x > B)
                return;
            if (x % 10 == 0) {
                if (x - 1 >= A)
                    st.insert(x - 1);
                if (x + 1 <= B)
                    st.insert(x + 1);
            } else
                st.insert(x);
        };

        add(A);
        add(B);

        int la = siz(A), lb = siz(B);
        for (int len = la; len <= lb; ++len) {
            for (int k = 1; k <= len; ++k) {
                ll n1 = A - P[k] + 1, n2 = B - P[k] + 1;
                if (n2 < 0)
                    continue;
                ll mx = n2 / P[k], mn = (n1 <= 0) ? 0 : ((n1 + P[k] - 1) / P[k]);
                if (mx < mn)
                    continue;
                ll b = mx * P[k] + P[k] - 1;
                if (b >= A && b <= B && b % 10 != 0)
                    st.insert(b);
            }
        }

        for (auto b : st) {
            ll rv = rev(b);
            if (rv > ans)
                ans = rv;
        }
    }
    cout << ans << endl;
}

H Blackboard

当且仅当每一位上最多只有一个

所以问题等价于:把序列分成若干连续段,使得每个段内的数在二进制位上两两不重叠。问这样的分割方式数目。

表示前 个数的合法分割数。 。对每一个 用双指针维护最小左端 ( 使 合法),即维护窗口中每一位的出现次数,当加入 时若与窗口中已有位重叠则移动左指针移除直到无冲突,则

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    vector<Z> dp(n + 1), pre(n + 1);
    dp[0] = pre[0] = 1;
    int l = 1, cur = 0;
    array<int, 31> cnt{};
    for (int i = 1; i <= n; ++i) {
        while ((cur & a[i]) != 0) {
            int x = a[l];
            for (int j = 0; j < 31; j++) {
                if ((x >> j) & 1) {
                    cnt[j]--;
                    if (cnt[j] == 0) {
                        cur &= (~(1 << j));
                    }
                }
            }
            l++;
        }
        int x = a[i];
        for (int j = 0; j < 31; j++) {
            if ((x >> j) & 1) {
                cnt[j]++;
                if (cnt[j] == 1) {
                    cur |= (1 << j);
                }
            }
        }
        int L = l;
        Z sum = pre[i - 1];
        if (L >= 2)
            sum -= pre[L - 2];
        dp[i] = sum;
        pre[i] = pre[i - 1] + dp[i];
    }
    cout << dp[n] << endl;
}

I AND vs MEX

我们需要找到一个最小的非负整数 ,使得 无法通过区间 ​ 中若干个数的按位与得到。

如果一个数能被生成,那么一定有:

  • 存在
  • 存在 ,使得对于任意一个 的二进制位, 满足 的此位为

我们可以通过枚举导致失败的边界来找到最小的

对于第一个条件:

的某些位必须为 ,而导致满足条件的最小 超过了 时,条件 失败。

我们可以枚举 中为 的位 。如果我们强制让这一位变为 ,那么满足该条件的最小数 (即保持 高位不变,第 位置 ,低位全清零)就是起点。

  • 如果 ,说明我们无法把第 位变成 ,那么 就是一个候选解。
  • 如果 ,我们可以计算出剩余的容量 。我们需要找到一个最小的低位后缀 ,使得 。这样一来, 就会超过 。此时 是候选解。

对于第二个条件:

的某一位 ,但区间 中所有 的超集的第 位都是 时,条件 失败。

这种情况只会在 的第 位本身就是 时发生(因为如果 的第 位是 ,那么 本身就可以用来清除该位)。

我们需要找到比 大的、且第 位为 的最小数。这意味着我们要找到 之上的第一个为 的位 ,并将 翻转为 (类似进位),从而得到一个新的基准值

  • 如果这样的 ,说明区间内所有数的第 位都是 ,任何 位为 都无法生成。此时 是候选解。
  • 如果 ,我们需要找一个最小的 (第 位为 ),使得 加上 超过 (即无法在区间内找到既是 超集又有 位为 的数)。
void solve() {
    ll l, r;
    cin >> l >> r;

    ll ans = r + 2;

    auto get = [&](ll l, int k) {
        ll mask = ~((1ll << (k + 1)) - 1);
        return (l & mask) | (1ll << k);
    };

    for (int k = 0; k <= 30; ++k) {
        if (!((l >> k) & 1)) {
            ll B = get(l, k), lim = r - B;

            if (lim < 0) {
                ans = min(ans, (1ll << k));
            } else {
                ll suff = lim + 1;
                if (suff < (1ll << k)) {
                    ans = min(ans, (1ll << k) + suff);
                }
            }
        }
    }

    for (int i = 0; i <= 30; ++i) {
        if ((l >> i) & 1) {
            int P = -1;
            for (int k = i + 1; k <= 31; ++k) {
                if (!((l >> k) & 1)) {
                    P = k;
                    break;
                }
            }

            if (P == -1) {
                ans = 0;
                break;
            }

            ll B = get(l, P), lim = r - B;

            if (lim < 0) {
                ans = min(ans, 0ll);
            } else {
                ll st = lim + 1;
                if (st < (1ll << P)) {
                    if ((st >> i) & 1) {
                        ll incr = (1ll << i), msk = (1ll << (i + 1)) - 1;
                        ll cand = (st + incr) & ~msk;
                        if (cand < (1ll << P)) {
                            ans = min(ans, cand);
                        }
                    } else {
                        ans = min(ans, st);
                    }
                }
            }
        }
    }
    cout << ans << endl;
}

K Constructive

不难猜出,能符合这些条件的 一定很少且很小,因为乘积的增幅比加要大很多,手玩一下发现只有 符合。

void solve() {
    int n;
    cin >> n;
    if (n == 1) {
        cout << "YES" << endl;
        cout << "1" << endl;
    } else if (n == 3) {
        cout << "YES" << endl;
        cout << "1 2 3" << endl;
    } else {
        cout << "NO" << endl;
    }
}

L Need Zero

我们可以想一下每一个尾数对应哪个数字:

整理一下输出即可

void solve() {
    int x;
    cin >> x;
    if (x % 10 == 0)
        cout << 1 << endl;
    else if (x % 5 == 0)
        cout << 2 << endl;
    else if (x % 2 == 0)
        cout << 5 << endl;
    else
        cout << 10 << endl;
}

头文件

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define endl "\n"
using namespace std;

using ll = long long;
using ld = long double;
using ui = unsigned;
using ull = unsigned long long;
using i128 = __int128;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
using TIII = tuple<int, int, int>;
using TLLL = tuple<ll, ll, ll>;

void init() {
}

void solve() {
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    init();

    int t = 1;
    cin >> t;
    cout << fixed << setprecision(15);
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }

    return 0;
}

自动取模

constexpr int MOD = 998244353;

template <class T>
constexpr T ksm(T a, ll b) {
    T res = 1;
    while (b) {
        if (b & 1)
            res *= a;
        b >>= 1;
        a *= a;
    }
    return res;
}

template <int P>
struct MInt {
    int x;
    constexpr MInt() : x() {}
    constexpr MInt(ll x) : x{norm(x % getMod())} {}
    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return ksm(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr istream &operator>>(istream &is, MInt &a) {
        ll v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr ostream &operator<<(ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};

template <>
int MInt<0>::Mod = 998244353;

template <int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

using Z = MInt<MOD>;

组合数学

struct Comb {
    int n;
    vector<Z> _fac, _inv;

    Comb() : n(0), _fac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }
    void init(int m) {
        if (m <= n)
            return;
        _fac.resize(m + 1);
        _inv.resize(m + 1);
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _inv[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _inv[i - 1] = _inv[i] * i;
        }
        n = m;
    }
    Z fac(int x) {
        if (x > n)
            init(x);
        return _fac[x];
    }
    Z inv(int x) {
        if (x > n)
            init(x);
        return _inv[x];
    }
    Z C(int x, int y) {
        if (x < 0 || y < 0 || x < y)
            return 0;
        return fac(x) * inv(y) * inv(x - y);
    }
    Z A(int x, int y) {
        if (x < 0 || y < 0 || x < y)
            return 0;
        return fac(x) * inv(x - y);
    }
};
全部评论
太强了,A看到好多都写得很麻烦,自己想的时候也觉得很难写,简化的太好了
点赞 回复 分享
发布于 02-04 16:31 陕西
谁懂点进链接那一刻的救赎感啊,泪目了
点赞 回复 分享
发布于 02-04 16:25 陕西

相关推荐

01-30 16:13
浙江大学 Java
点赞 评论 收藏
分享
2025-12-28 20:47
已编辑
北京工商大学 Java
程序员牛肉:我靠你这个实习经历其实最需要担心的点是你做的太多了,可能会被面试官怀疑是你伪造的。 交易状态机是你做的,支付多渠道是你做的,对账是你做的,结算还是你做的,重复支付也是你做的,整个服务的异常处理也是你做的。 其实你这个反而问题很大的,你想想站在面试官的角度,他是真的会相信你的能力很强,还是相信这份实习你伪造了大部分?我相信你真的做了这么多,但是删一些,废话删一删。你这个做的太多了反而真实性不可信。 后面再补一个项目,在github上找一个高star的项目学一学然后写到自己简历上。我觉得你能力肯定没问题。28届能做到这个份上很厉害,但是在求职市场中,你不是在跟28届的同学比,把你这个简历放到27届其实也就一般水平。 所以后续要想一想看看能不能给自己简历上搞点亮点,比如开源贡献呢?比如博客呢?
实习要如何选择和准备?
点赞 评论 收藏
分享
评论
8
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务