题解 | 2026牛客寒假算法基础集训营1（ABCDEGHIKL）
|
93
|
0
|
牛客

2471 字
|
37 分钟

个人难度评级

签到：$\text{CEKL}$

简单：$ABG$

中等：$DHI$

困难：$FJ$

A A+B Problem

简单的模拟数学题，先求每个数字 $x$ 被点亮的概率 $q[x]$ ，再求 $0000\sim 9999$ 中每一个数字 $\overline{abcd}$ 被点亮的概率
$$P[\overline{abcd}] = q[a]\times q[b]\times q[c]\times q[d]$$
最后满足 $A+B=C$ 的概率即为 $\sum\limits_{i+j=C}P[i]\times P[j]$

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

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

记大于 $mn$ 的牌有 $k$ 张，最后的答案为 $k!\times (n-k)!$

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

我们可以用最大的数 $mx$ 尽可能覆盖所有数字，由于边界不会被覆盖，所以最后的答案为
$$a[1]+a[n]+(n-2)\times mx$$
注意数据范围

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

显然如果时间 $T$ 可行，则 $T+1$​ 也可行。不难想到我们可以使用二分。

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

但是模拟处理染色扩散的过程太慢，所以我们用倍增数组 $up[k][i]$ 表示从前缀 $[1,i]$ 出发，经过 $2^k$ 秒能够覆盖的最远白色元素的下标， $up[0][i]$ 就是 $[1,i]$ 所有元素单步能到的最远位置的最大值，$up[k][i] = up[k-1][up[k-1][i]]$ 。

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

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

我们考虑去枚举长度，对于每一个长度 $len$ ，取 $[l,r]$ 和这个长度对应的区间取交集，得到当前的有效区间 $[L,R]$ 。因为我们需要反转后的数字尽可能大，所以从低位向高位贪心。我们从右往左逐位尝试放数字 $d$ 得到后缀 $suf$ ，然后检查是否存在一个数 $x\in[L,R]$ ，使得 $x$ 的后缀等于当前构造的后缀，也就是检查同余方程 $x\equiv suf \pmod {10^{pos}}$ 在 $[L,R]$ 是否有解（ $pos$​ 是当前尝试的位 ）。如果有解，说明这一位可以填 $d$，记录 $d$，更新后缀值，并跳出当前位的枚举；否则继续尝试更小的 $d$ 。

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

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

$Or = Sum$ 当且仅当每一位上最多只有一个 $1$ 。

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

用 $dp[i]$ 表示前 $i$ 个数的合法分割数。$dp[i] = \sum\limits_{(j+1,i)\text{合法}}dp[j]$ 。对每一个 $i$ 用双指针维护最小左端 $L$（ 使 $[L,i]$ 合法），即维护窗口中每一位的出现次数，当加入 $a[i]$ 时若与窗口中已有位重叠则移动左指针移除直到无冲突，则 $dp[i] = \sum\limits_{j=[L-1,i-1]} dp[j]$ 。

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

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

如果一个数能被生成，那么一定有：

  • 存在 $S\subseteq [l,r]$ ，$\forall v\in S,v\&x=x$
  • 存在 $S\subseteq[l,r]$ ，使得对于任意一个 $x$ 为 $0$ 的二进制位， $\exists v\in S$ 满足 $v$ 的此位为 $0$

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

对于第一个条件：

当 $x$ 的某些位必须为 $1$ ，而导致满足条件的最小 $v$ 超过了 $r$ 时，条件 $1$ 失败。

我们可以枚举 $l$ 中为 $0$ 的位 $k$ 。如果我们强制让这一位变为 $1$ ，那么满足该条件的最小数 $B$（即保持 $l$ 高位不变，第 $k$ 位置 $1$ ，低位全清零）就是起点。

  • 如果 $B>r$ ，说明我们无法把第 $k$ 位变成 $1$，那么 $x=(1≪k)$ 就是一个候选解。
  • 如果 $B\leq r$ ，我们可以计算出剩余的容量 $lim=r−B$ 。我们需要找到一个最小的低位后缀 $suff$，使得 $suff>lim$ 。这样一来，$B+suff$ 就会超过 $r$。此时 $x=(1≪k)+suff$ 是候选解。

对于第二个条件：

当 $x$ 的某一位 $i$ 为 $0$ ，但区间 $[l,r]$ 中所有 $x$ 的超集的第 $i$ 位都是 $1$ 时，条件 $2$ 失败。

这种情况只会在 $l$ 的第 $i$ 位本身就是 $1$ 时发生（因为如果 $l$ 的第 $i$ 位是 $0$ ，那么 $l$ 本身就可以用来清除该位）。

我们需要找到比 $l$ 大的、且第 $i$ 位为 $0$ 的最小数。这意味着我们要找到 $l$ 在 $i$ 之上的第一个为 $0$ 的位 $P$ ，并将 $P$ 翻转为 $1$（类似进位），从而得到一个新的基准值 $B$。

  • 如果这样的 $B>r$，说明区间内所有数的第 $i$ 位都是 $1$ ，任何 $i$ 位为 $0$ 的 $x$ 都无法生成。此时 $0$ 是候选解。
  • 如果 $B\leq r$ ，我们需要找一个最小的 $x$（第 $i$ 位为 $0$ ），使得 $B$ 加上 $x$ 超过 $r$（即无法在区间内找到既是 $x$ 超集又有 $i$ 位为 $0$ 的数）。
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

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

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

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

  • $0\rightarrow 1$
  • $1\rightarrow 10$
  • $2\rightarrow 5$
  • $3\rightarrow 10$
  • $4\rightarrow 5$
  • $5\rightarrow 2$
  • $6\rightarrow 5$
  • $7\rightarrow 10$
  • $8\rightarrow 5$
  • $9\rightarrow 10$

整理一下输出即可

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°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇