2026牛客寒假算法基础集训营1 补题 - Karasu's Notes

2026牛客寒假算法基础集训营1 思路与题解（L K C E B A G）

ninelie – Aimer,EGOIST

「Don’t be afraid daybreak has come」
　无需畏惧黎明已然降临

官方题解：https://blog.karasu.us/wp-content/uploads/2026/02/寒假营第一场题解.pdf

L Need Zero

题意：

给定正整数 $n$。求最小的正整数 $x$，使得 $n \times x$ 的末尾为 $0$。

#include <iostream>
using namespace std;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n;
    cin >> n;
    //答案不超过 10
    if (n % 10 == 0) cout << 1;
    else if (n % 5 == 0) cout << 2; //0,2,4,6,8 都可以通过乘以 5 变成十的倍数
    else if (n % 2 == 0) cout << 5; //反之 5 通过乘以 2 变成十的倍数
    else cout << 10;

    return 0;
}

K Constructive

题意：

构造字典序最小的，长度为 $n$ 的数组满足：

所有数字均为正整数
所有数字互不相同
所有数字的和等于所有数字的乘积

#include <iostream>
using namespace std;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        if (n == 1 || n == 3)    //注意到只有 1 和 3 有解
        {
            cout << "YES\n";
            for (int i = 1; i <= n; i++) cout << i << ' ';
            cout << '\n';
        }
        else cout << "NO\n";
    }

    return 0;
}

C Array Covering

题意：

给定一个序列，可以任意次操作，每次选择一个区间，把区间中（不包含端点）的数字都变为 $\max(a_l, a_r)$，问序列所有数字的总和最大值可以达到多少。

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
ll a[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T--)
    {
        ll n, mx = 0;
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            mx = max(mx, a[i]);    //记录数组中出现的最大值，假设下标为 idx
        }
        //则选择 (1, idx) 和 (idx, n) 将除两个端点的数字变为最大值
        ll ans = mx * (n - 2) + a[1] + a[n];
        cout << ans << '\n';
    }

    return 0;
}

注意开 long long

E Block Game

有 $n$ 个小方块排成一排，其中第 $i$ 个小方块上的数字是 $a_i$，另外还有一个万能方块上面数字是 $k$。可以任意次把万能方块从方块序列的最左侧插入，其余方块后移，同时最后一个方块变成新的万能方块。

最大化：第一个方块上的数字 + 万能方块上的数字。

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int a[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T--)
    {
        int n, k;
        cin >> n >> k;
        a[1] = k;    //看作一个长度为 n + 1 的数组，其中把 k 排在第一位 
        for (int i = 2; i <= n + 1; i++) cin >> a[i];
        int ans = a[1] + a[n + 1];
        //两数之和即这个数和它前一个数的和
        for (int i = 2; i <= n + 1; i++) ans = max(ans, a[i] + a[i - 1]);
        cout << ans << '\n';
    }

    return 0;
}

B Card Game

题意：

一个长度为 $2 \times n$ 的排列被恰好分成了两行 $n$ 个数字（$a, b$ 两数组），现在不停进行比较操作：

每次比较 $a_1$ 和 $b_1$，将大的数字删除，同一行其余数字前移。如果是 $a_1$ 被删除则得一分。

直到 $a$ 或 $b$ 被删空停止。

游戏过程如上，现在你可以在游戏开始前任意重排 $a$ 以得到最大的得分，问有多少种重排的方式可以使得得分取到可能的最大值。

思路：

以 $b$ 中的最小值 $min_b$ 为界，$a$ 中小于 $min_b$ 数的一定无法被删除，可以把这堆数全排列。

再考虑大于 $min_b$ 的数，模拟几个例子可以发现它们一定可以被删除，同样可以把这堆数全排列，答案就是两部分阶乘的乘积。

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const int MOD = 998244353;
int a[N], b[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T--)
    {
        int n, minb = 4e5 + 5;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++)
        {
            cin >> b[i];
            minb = min(minb, b[i]);
        }
        sort(a + 1, a + n + 1);
        int small = upper_bound(a + 1, a + n + 1, minb) - (a + 1);
        int big = n - small;
        ll ans = 1;
        for (int i = 1; i <= big; i++)
        {
            ans = ans * i % MOD;
        }
        for (int i = 1;i <= small; i++)
        {
            ans = ans * a[i] % MOD;
        }
        cout << ans << '\n';
    }

    return 0;
}

A A+B Problem

题意：

有八个独立的数位显示器，每个显示器的每个二极管被点亮的概率为 $p_i$，管与管之间互相独立，显示器之间也相互独立。求分别显示出两个四位合法数字，且数字之和等于输入的常数 $C$ 的概率。

附：分数取模结论

以任意分数：$\frac{a}{b}$ 为例，根据费马小定理，在模数 $m$ 为质数，且 $b$ 不是 $m$ 的倍数的情况下有：

$\frac{a}{b}\bmod m=a\times (b^{m-2})\bmod m$

思路：

从 $A + B = C$ 入手，可以将其转化为 $B = C – A$，则对于 $A$ ($0 \le A \le C$) 都有对应的 $B$，得到 $C$ 的概率为 $P(\text{显示出 } A) \times P(\text{显示出 } B)$，枚举一遍然后将每种情况的答案概率相加即可。

$A$ 和 $B$ 都为四位数，显示出这样一个四位数的概率就是用它的四位数字的概率相乘，所以要先得到一个显示器显示出 $0 – 9$ 每个数字的概率，不嫌麻烦可以每个分别手写，简便一点可以使用二进制状态压缩。

具体各部分见代码注释。

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
//const int N = 2e5 + 5;
const int MOD = 998244353;
ll p[7], digit[10], S[10];

void init() //状态压缩，存入每个 digit 需要的段码编号
{
    S[0] = (1 << 0) | (1 << 1) | (1 << 2) | (1 << 4) | (1 << 5) | (1 << 6); //1110111
    S[1] = (1 << 2) | (1 << 5); //0100100
    S[2] = (1 << 0) | (1 << 2) | (1 << 3) | (1 << 4) | (1 << 6);    //1011101
    S[3] = (1 << 0) | (1 << 2) | (1 << 3) | (1 << 5) | (1 << 6);    //1011011
    S[4] = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 5);   //0111010
    S[5] = (1 << 0) | (1 << 1) | (1 << 3) | (1 << 5) | (1 << 6);    //1101011
    S[6] = (1 << 0) | (1 << 1) | (1 << 3) | (1 << 4) | (1 << 5) | (1 << 6); //1101111
    S[7] = (1 << 0) | (1 << 2) | (1 << 5);  //1010010
    S[8] = (1 << 0) | (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4) | (1 << 5) | (1 << 6);  //1111111
    S[9] = (1 << 0) | (1 << 1) | (1 << 2) | (1 << 3) | (1 << 5) | (1 << 6); //1111011
}

ll fastpower(ll base, ll pow)   //快速幂
{
    ll res = 1;
    while(pow > 0)
    {
        if (pow & 1)
        {
            res = res * base % MOD;
        }
        base = base * base % MOD;
        pow >>= 1;
    }
    return res;
}

ll probability(ll num)  //计算显示出某个四位数的概率
{
    ll ans = 1;
    for (int i = 0; i < 4; i++)
    {
        ans = ans * digit[num % 10] % MOD;
        num /= 10;
    }
    return ans;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    init();
    while (T--)
    {
        int C;
        cin >> C;
        fill(digit, digit + 10, 1);
        //读入，同时把概率从分数按要求转化为整数
        for (int i = 0; i < 7; i++)
        {
            cin >> p[i];
            p[i] = p[i] * fastpower(100, MOD - 2) % MOD;
        }
        //计算 0 到 9 每个数字出现的概率，存在 digit 数组里
        for (int i = 0; i < 10; i++)
        {
            for (int j = 0; j < 7; j++)
            {
                if (S[i] >> j & 1) digit[i] = digit[i] * p[j] % MOD;
                else digit[i] = digit[i] * (MOD + 1 - p[j]) % MOD;
            }
        }
        ll ans = 0;
        for (int A = 0; A <= C; A++)
        {
            int B = C - A;
            ans = (ans + (probability(A) * probability(B) % MOD)) % MOD;
        }
        cout << ans << '\n';
    }

    return 0;
}

G Digital Folding

题意：

给定区间 $[l, r], (1 \le l \le r \le 10^{15})$，定义 $f(x)$ 为把数字 $x$ 的十进制翻转后去除前导 $0$ 的值。

求区间中所有数字 $i (l \le i \le r)$ 的 $f(i)$ 最大值。

思路：

注意到从低位到高位填充尽可能多的 $9$ 可使结果最大化，考虑贪心。对于当前位 $i$，后缀均变为 $9$，第 $i$ 位数字需减一以构造出小于等于 $R$ 的最大后缀 $9$ 数值，前缀不变，从区间最大值 $R$ 的最后一位开始往前遍历，不断更新答案最大值。

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
//const int N = 2e5 + 5;

ll rev(ll x)
{
    string s = to_string(x);    //可去前导零
    reverse(s.begin(), s.end());
    return stoll(s);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T--)
    {
        string ls, rs;
        cin >> ls >> rs;
        ll l = stoll(ls), r = stoll(rs);
        ll ans = rev(r);    //初始化 ans 为右端点，处理末尾已有 9 或无需退位的情况
        for (int i = rs.size() - 1; i >= 0; i--)
        {
            string temp;
            if (rs[i] == '0') continue;
            for (int j = 0; j < i; j++) temp += rs[j]; //复制相同前缀
            temp += (char)(rs[i] - 1);  //当前位减一
            for (int j = i + 1; j < rs.size(); j++) temp += '9';    //后缀填充为 9
            ll temp_l = stoll(temp);
            if (temp_l >= l && temp_l <= r) ans = max(ans, rev(temp_l));
        }
        cout << ans << '\n';
    }

    return 0;
}

L Need Zero

K Constructive

C Array Covering

E Block Game

B Card Game

A A+B Problem

G Digital Folding

发送评论 编辑评论

发送评论编辑评论