2026 牛客寒假集训营-1

1. L-Need Zero

题目描述

小苯拿到了一个正整数 ，现在他希望 的个位数是 ，为此他 必须 执行下述操作恰好一次：

• 选择一个正整数 ，并执行 （其中 表示赋值操作）。

你的任务就是帮助小苯找出 最小 的 。我们可以证明，一定存在合法的答案。

输入描述

输入一个正整数 ，表示小苯拿到的数字。

输入描述

输出一个正整数，表示最小的合法解 （可以证明在题目的限定范围内一定有解）。

解题思路

我们需要找到一个 ，使得运算结果 的个位数为 。

1. 观察个位数规律： 的个位结果仅由 的个位数字和 的个位数字相乘决定。因此，我们只需要考虑 的值。

2. 确定 的范围： 我们要匹配一个 最小 且乘积运算后个位为 的数字作为 。

   • 由于 和任何数相乘，其结果的个位都是 。
   • 因此可以*** 一定满足 。
   • 例如：当 的个位是 5 时，2、4、6 都能满足条件，但 2 最小，所以会选择 2 作为输出 的最终答案。

3. 算法实现： 代码选择 从小到大（从 1 到 10）遍历 ，将其与 的个位数进行乘法运算。第一个符合 (n * x) % 10 == 0 的数字即为结果。

AC 代码

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n;
    cin >> n;
    // 取出 n 的个位数字
    int temp = n % 10;
    // 从小到大枚举 x，范围只需到 10 即可
    for (int i = 1; i <= 10; i++) {
        // 判断乘积的个位是否为 0
        if ((i * temp) % 10 == 0) {
            cout << i << "\n";
            break; // 找到最小的 x 后立即退出
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T; // 如果有多组数据请取消注释
    while (T--) {
        solve();
    }
    return 0;
}

2. K-Constructive

题目描述

给定一个正整数 ，你需要构造一个长度为 的数组 ，满足以下条件：

• 数组中的每个元素 都是正整数；
• 所有元素的乘积等于所有元素的和；
• 数组中的元素 互不相同。

小苯想知道，对于给定的 ，是否存在这样的数组。如果存在，请构造 字典序最小 的解；如果不存在报告无解。

【名词解释】 数组的字典序比较：从左到右逐个比较两个数组的元素。如果在某个位置上元素不同，比较这两个元素的大小，元素小的数组字典序也小。如果一直比较到其中一个数组结束，则长度较短的数组字典序更小。 例如： 的字典序小于 ，也小于 。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数。 每组测试数据输入一个整数 ，表示数组的长度。 保证单个测试文件中所有 之和不超过 。

输出描述

对于每组测试数据，如果不存在满足条件的数组，直接输出 NO，否则：

• 第一行输出 YES；
• 第二行输出 个正整数，表示字典序最小的满足条件的数组，元素间用单个空格分隔。

解题思路

题目要求寻找字典序最小的满足条件的数组（元素互不相同，且 ）。

1. 贪心策略与增长率分析： 为了保证字典序最小，我们需要把小的数字放在前面（如 ）。 然而，一旦我们观察数据的增长趋势，会发现差异巨大：

   • 乘积（Product）：即使是最小的排列 ，其乘积也是呈阶乘级增长的。
   • 和（Sum）：元素的和则是呈算术级数增长的。

2. 具体案例分析：

   • 当 时，最小排列为 。此时 ，而 。乘积已经远大于和，且随着 增大，两者的差距会越来越大。
   • 因此，我们可以推测绝大多数情况是无解的。

3. 枚举特例：

   • ：，。（可行）
   • ：，。（不可行）
   • ：，。（可行）
   • ：如前所述，乘积增长过快，均无解。

   结论：仅当 和 时有特定解，其他情况均输出 NO。

PS：

本人在开始时漏掉了数组元素各不相同的要求，根据很抽象的公式勾史推导，萌发出构造出形式于 1,1,1...,1,2,x 的数组的想法，发现这个要求后，脑袋依旧抽象地修改了公式的一个参数，然后根据莫名其妙的公式，对数组的最后两个数开始遍历查询，思路错了，公式错了，结果代码AC了

AC 代码

#include <bits/stdc++.h>
using namespace std;
int n;
void solve() {
    cin >> n;
    // 仅 n=1 和 n=3 时存在满足 数列互不相同 且 和等于积 的情况
    if (n == 1 || n == 3) {
        cout << "YES\n";
        // 字典序最小即为 1 到 n 的自然数序列
        for (int i = 1; i <= n; i++) cout << i << " ";
        cout << "\n";
        return;
    }
    // 其他情况乘积增长过快，无法等于和
    cout << "NO\n";
    return;
}
signed main() {
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}

3. E-Block Game

题目描述

小苯正在玩方块小游戏，游戏中有一排 个方块，每个方块上都有一个数字，此外，他还有一个写着数字 的万能方块，游戏过程如下。

小苯可以进行任意次（可以为 次）以下操作：

• 将万能方块从方块序列的 最左侧插入，同时 最右侧 的第 个方块会被挤出这一行，成为新的万能方块。

形式化地： 记开始时的序列为 （初始时 ），万能方块值为 （初始时 ）； 操作完成后序列变为 ，万能方块上的数字变为 ，其他方块保持相对顺序整体右移一位。

你的任务是计算出，按照最优方式经过若干次操作后，从左往右数 第一个 方块上的数字加上最终的 万能方块 上的数字的总和的最大值。

输入描述

每个测试文件包含多组测试数据。第一行输入一个整数 代表数据组数。 每组测试数据输入两个整数 ，表示方块个数、初始的万能方块上的数字。 第二行输入 个整数 ，表示从左往右数第 个方块上写的数字。 保证单个测试文件的 之和不超过 。

输出描述

对于每一组测试数据，新起一行输出一个整数，表示最终：从左往右数第一个方块上的数字 万能方块上的数字之和的最大值。

解题思路

只有一行数字，万能方块 也只能从数组左边插入，右边踢出一个新的数字，这种顺序是按照数组的顺序进行推进的。

1. 观察操作规律： 每一次操作都是 和 进行交换推进。

   • 初始状态：和为 。
   • 如果只看 “第一个方块 + 万能方块” 的组合，实际上除却 参与的边界情况（ 和 ），其他轮次的结果本质上都是数组中 相邻元素 的和，即 。

2. 模拟过程： 取代 ， 取代 ，可以理解为整个序列在流动。 我们要做的就是遍历一遍数组：

   • 计算每一个位置相邻元素的和 。
   • 同时考虑 参与的特殊情况： 和 。

3. 结论： 取上述所有情况的最大值即可。

PS：

一眼以为是会形成一个环形，然后把数组最后加上K，数组长度+1，然后复制一遍，变成长度为2*（n+1）的数组，从n遍历n*2+1 ，每次进行相邻两个位置和的最大值维护，最后也过了，差不多的过程，但仔细推导发现，结果一致，但整个循环的过程是相反的。

AC 代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
const int inf = 1e18;
vector<int> v;
int n, k;

void solve() {
    cin >> n >> k;
    v.assign(n + 1, 0); 
    for (int i = 1; i <= n; i++) cin >> v[i];
    int ans = -inf;
    for (int i = 1; i < n; i++) {
        ans = max(ans, v[i] + v[i + 1]);
    }
    ans = max({ans, k + v[1], k + v[n]});
    cout << ans << "\n";
}
signed main() {
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}

4. C-Array Covering

题目描述

给定长度为 的数组 ，其中第 个数的值为 。

小苯希望数组中所有数字的总和尽可能大，为此他可以做任意次如下操作：

• 选择一对下标 ，接着将 区间（注意是 开区间）内的所有数都变为区间端点值的较大者。

形式化地： 对所有 ，均执行：（其中 表示赋值操作）。

你的任务就是求出数组总和的最大值。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数。 每组测试数据的第一行输入一个正整数 ，表示数组 的长度。 第二行输入 个正整数 ，表示最初时所有数字的值。 保证单个测试文件的 之和不超过 。

输出描述

对于每一组测试数据，新起一行输出一个正整数，表示在可以进行任意次操作的情况下，所有数字之和的最大值。

解题思路

题目允许选择一个区间，把区间内（不包含两端点）的所有元素都赋值为两端中的较大值。

1. 策略选择： 我们可以利用数组中的 最大值 来覆盖其他较小的值。假设 是数组中的最大值，我们可以分别通过操作区间 和 ，利用 向左和向右覆盖。

2. 边界分析： 由于题目明确要求是 开区间 操作 ，即只修改 的元素。 这意味着数组的第一个元素 （作为最左端点 ）和最后一个元素 （作为最右端点 ）永远无法被包含在开区间内部，因此它们的值 无法改变。

3. 计算结果： 除了 和 这两个固定点外，中间的 个位置理论上都可以被替换为数组中的最大值 。

   因此，最终数组元素和的最大值为：

   

AC 代码

void solve() {
    inpu();
    int maxx = -inf;
    for (int i = 1; i <= n; i++) maxx = max(maxx, v[i]);
    cout << maxx * (n - 2) + v[1] + v[n] << "\n";
}

5. B-Card Game

题目描述

小苯正在和小红玩卡牌游戏。游戏中有 张牌，每张牌上都有一个数字，所有牌的数字恰好构成了一个长度为 的排列。

游戏最初时， 张卡牌被恰好平均分成了两组 张牌，并分别发给了两人，小苯第 张牌上的数字是 ，而小红第 张牌上的数字是 ，具体的游戏过程如下：

• 如果两人之中有一人已经没有牌了，则游戏结束。
• 比较两人当前手牌中的最前一张，对应数字大的那一方得一分并将该张牌从自己手牌移除；另一方不得分，手牌也不变。随后进入下一轮。

而现在小苯希望自己的得分尽可能多，为此他在游戏开始前可以 任意地 重新排列自己的牌，以得到更高的游戏分数。

现在你的任务则是求出，有多少种重新排列（选择不进行重排也是一种方案）的方式，能使得小苯得到他能得到的最高分。由于答案可能很大，请将答案对 取模后输出。

【名词解释】 长度为 的排列：由 这 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数。 每组测试数据的第一行输入一个正整数 ，表示两人的卡牌数量。 第二行输入 个正整数 ，表示小苯的卡牌上的数字。 第三行输入 个正整数 ，表示小红的卡牌上的数字。 保证 数组和 数组共同构成一个长度为 的排列，且单个测试文件的 之和不超过 。

输出描述

对于每一组测试数据，新起一行输出一个整数，表示小苯重新排列自己卡牌，使得他能得到的最高分的方案数对 取模后的值。

解题思路

已知的卡牌规则： 如果当前小苯的牌 小于小红任意牌的最小值，那么小苯此刻只能看着小红出完所有的牌，以至于自己手中更大的牌都无法得分。我们称这种牌为 死牌，反之比小红手中某张卡牌更大的牌即为可以得分的 活牌。

即小苯想获得最大得分，则 活牌 必须放在 死牌 前面。

1. 统计活牌和死牌的数量。
2. 活牌和死牌各自内部的排序是不影响得分的。
3. 计算两部分的排列数然后相乘即可，记得取模 。

AC 代码

void solve() {
    inpu();
    int minn = inf;
    // 找到小红手中最小的牌
    for (int i = 1; i <= n; i++) minn = min(b[i], minn);
    int c1 = 0, c2 = 0;
    // 统计活牌(c1)和死牌(c2)
    for (int i = 1; i <= n; i++) {
        if (a[i] > minn) c1++;
        else c2++;
    }
    // 排列组合：活牌全排列 * 死牌全排列
    int ans = f[c1];
    ans = ans * f[c2] % mod;
    cout << ans << "\n";
}

6. A-Card Game

题目描述

小苯正在学习 A+B Problem，为此他从家中翻出了 恰好八个 "七段码数位显示器"（以下简称显示器）。

如下图所示，显示器共有 个灯管，图中已标明编号。点亮其中的一些灯管就可以形成合法的数字， 的对应的点亮结果如下图二，其中红色灯管是被点亮的，灰色则是未被点亮（其余的结果均是不合法的数字）。

图1: 灯管编号              图2: 数字 $0\sim9$ 对应的状态

遗憾的是，放置时间太久导致所有的显示器都发生了 相同 的故障，具体来说，在点亮他们的编号为 的灯管时，灯管都是仅有 的概率会被点亮，而还会有 的概率不会被点亮（各根灯管的点亮尝试相互独立；不同显示器之间、同一显示器内不同编号灯管之间的点亮结果均互不影响）。

但小苯的学习还得进行下去，现在他会让小红指定一个整数 ，接着小苯会将其中的 四个 排成一排，另外 四个 排成另一排，并对其 根灯管（共 根）均各 尝试一次点亮操作。（由于所有显示器参数相同，具体选哪 台放在第一排与第二排均等价，可视为任意固定分配）。

现在请你计算出如下事件的概率（需全部满足）：

• 最终所有显示器均有灯管被点亮（也就是说显示器的灯管不能全灭）。
• 最终所有显示器显示的结果均为合法数字。
• 第一排的显示器前后拼接形成的四位十进制数记作 ，第二排的显示器前后拼接形成的四位十进制数记作 的话，满足：。（两排显示器从左到右依次作为千位、百位、十位、个位进行拼接，可以存在前导 ）。

如果您不了解分数取模，可以查看下方的备注。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数。 每组测试数据的第一行输入一个整数 ，表示目标和。 接下来 7 行，每行输入两个整数，分别表示第 到第 根灯管的点亮概率 。 注意：输入通常给出的是概率的分子（分母为100），或者直接给出 。

输出描述

对于每一组测试数据，新起一行输出一个整数，表示最终的概率（对 取模）。 可以证明答案可以表示为一个不可约分数 ，请直接输出整数 作为答案。

解题思路

每一个显示器都是独立且完全相同的（每一个数字或不合法状态在不同的显示器上出现的概率都是相同且独立的）。

1. 分解问题： 解决这个题目只需要计算出合法的 的情况。我们需要计算每一对满足条件的 和 出现的概率，然后将这些概率累加即可。

2. 单一数字概率计算： 对于出现的四位数字 ，我们可以独立地计算每一位数字的概率，然后将四个位置的数字概率相乘。 每一位数字（0-9）的概率可以通过 7 根晶体管的发光概率或不发光概率进行提前预处理计算。

   • 例如：数字 0 出现的概率 = (1,2,5,6,7号管发光的概率) (4号管不发光的概率)。

3. 组合统计： 遍历 从 到 （因为 ），则 确定为 。 每次计算 并累加到答案中。

4. 注意事项： 取模中的除法运算，需要使用乘法逆元转化为乘法操作。

AC 代码

const int N = 2e5 + 5;
const int mod = 998244353;
// 7段数码管对应 0-9 的亮灭状态表 (1亮, 0灭)
// 顺序对应题目图1的编号
int p[10][7] = {
    {1, 1, 1, 0, 1, 1, 1}, // 0
    {0, 0, 1, 0, 0, 1, 0}, // 1
    {1, 0, 1, 1, 1, 0, 1}, // 2
    {1, 0, 1, 1, 0, 1, 1}, // 3
    {0, 1, 1, 1, 0, 1, 0}, // 4
    {1, 1, 0, 1, 0, 1, 1}, // 5
    {1, 1, 0, 1, 1, 1, 1}, // 6
    {1, 0, 1, 0, 0, 1, 0}, // 7
    {1, 1, 1, 1, 1, 1, 1}, // 8
    {1, 1, 1, 1, 0, 1, 1}  // 9
};

int n; // 题目中的 C
int gl[10]; // 预处理每个数字出现的概率
int pp[7][2]; // 存储每个灯管亮(1)和灭(0)的概率

int qmi(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res % mod;
}
int inv(int x) {
    return qmi(x, mod - 2) % mod;
}
// 预处理 0-9 每个数字生成的概率
void cal() {
    for (int i = 0; i <= 9; i++) gl[i] = 1;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 7; j++) {
            // 如果该数字需要第j根管亮，乘亮概率；否则乘灭概率
            gl[i] *= pp[j][p[i][j]];
            gl[i] %= mod;
        }
    }
}
// 计算某一个四位数 i 出现的概率
int cl(int i) {
    int res = 1;
    // 强制按四位处理（补前导0）
    for (int k = 1; k <= 4; k++) {
        int tmp = i % 10;
        i = i / 10;
        res = res * gl[tmp] % mod;
        res = (res + mod) % mod;
    }
    return res % mod;
}
// 计算 A=i, B=j 这种情况的联合概率
int check(int i, int j) {
    int res = cl(i) * cl(j) % mod;
    res = (res + mod) % mod;
    return res;
}
void inpu() {
    cin >> n;
    // 读取7根管的概率，pp[i][1]是给出的概率，pp[i][0]是100-p
    for (int i = 0; i < 7; i++) {
        cin >> pp[i][1];
        pp[i][0] = 100 - pp[i][1];
    }
}
void solve() {
    inpu();
    // 将百分比一般化为模意义下的分数
    for (int i = 0; i < 7; i++) {
        pp[i][0] = pp[i][0] * inv(100) % mod;
        pp[i][1] = pp[i][1] * inv(100) % mod;
    }
    cal(); // 预处理单数字概率
    int ans = 0;
    // 遍历所有可能的 A，算出对应的 B=C-A
    for (int i = 0; i <= n; i++) {
        int j = n - i;
        ans = ans + check(i, j) % mod;
        ans = (ans % mod + mod) % mod;
    }
    cout << ans << "\n";
}

7. G-Digital Folding

题目描述

小苯发现了一种特殊的数字运算，称为 "数字折叠"。对于一个正整数 ，定义其 "折叠数" 为：

• 将 的十进制数位翻转并去除前导 ， 的值更改为翻转后得到的新数。
• 例如， 操作后会变为 ，而 会变为 。

现在小苯拿到了一个区间 ，他想知道如果将区间中所有的整数 的折叠数都求出，那么其中的最大值是多少。你的任务就是求出这个最大值。

输入描述

每个测试文件包含多组测试数据。第一行输入一个整数 代表数据组数。 每组测试数据在一行上输入两个整数 ，表示询问的区间。

输出描述

对于每一组测试数据，新起一行输出一个整数，表示区间中所有数的 "折叠数" 的最大值。

解题思路

数据范围不超过 ，无法遍历得到最终答案，需要使用更高效的方法去查找，或者找到某种规律或性质直接去构造最优的结果作为答案。

1. 观察长度规律： 若 为 的长度，则最大的折叠数的长度一般为 或者 。

2. 特殊情况（ 为 的幂次）： 当 时，如果选择 作为折叠数，去除前导 后结果为 ，这显然很小。 此时如果 ，我们可以选择 （即 ），其折叠数也是 ，长度为 ，这通常是最优解。

3. 构造贪心策略： 另一种情况，折叠数的长度一定为 ，即和 的长度一致。如果 的长度小于 ，可以直接取长度为 的最小的数（即 ），使 和 的长度对齐。 在以上的铺垫下，我们只需要从高位到低位，枚举每一位的选择：

   • 比较 和 。
   • 如果相同，该位只能固定。
   • 如果不同，说明在这一位上区间有跨度。我们可以尝试选 并将后续位全部填 。如果构造出的数超过了 ，则该位减 变为 ，后续仍全填 （这一定能保证小于 且大于 ）。

4. 去前导零： 构造出的数字需要反转，并去掉反转后可能产生的首位 。

PS

赛时用数位 DP 写的，没有考虑到这道题的良好性质，会更麻烦，但用这题练一下数位 DP 也不错的。

AC 代码

void check(int l, int r) {
    string ans = "";
    string temp = "1";
    string sl = to_string(l), sr = to_string(r);
    // 如果区间只有这一个数，直接输出
    if (sl == sr) {
        ans = sl;
        goto part;
    }
    // 构造 10^k
    for (int i = 1; i < sr.size(); i++) temp += '0';
    // 特判 r 是 10^k 的情况，此时的最优解通常是 r-1 (即全9)
    if (temp == sr) {
        for (int i = 1; i < sr.size(); i++) cout << '9';
        cout << "\n";
        return;
    }
    // 如果位数不同，将 l 补齐为同位数的最小值 (10...0)，方便统一处理
    if (sl.size() != sr.size()) sl = temp;
    for (int i = 0; i < sl.size(); i++) {
        if (sl[i] == sr[i]) {
            ans += sl[i];
        } else {
            // 贪心：尝试取上限 sr[i]，后面全填 9
            ans += sr[i];
            for (int j = i + 1; j < sl.size(); j++) ans += '9';
            // 如果构造结果超过 r，则当前位退 1，后面依然全 9
            if (ans > sr) ans[i] = sr[i] - 1;
            goto part;
        }
    }
    part:
    // 反转得到折叠数
    reverse(ans.begin(), ans.end());
    // 去除前导零输出
    bool f = false;
    temp = "";
    for (auto &c : ans) {
        if (f || c != '0') {
            f = true;
            temp += c;
        }
    }
    cout << temp << '\n';
    return;
}

8. H-Blackboard

题目描述

小红在黑板上写了一个计算式，具体来讲是 个数字 ，其中间由 个加号（+）连接组成：。

现在小苯想去擦去黑板上的一些 + 运算符，但他擦得很不干净，只擦去了加号中的横线（-），剩下的部分就是一个竖线（|）了。巧合的是， 恰好也是一个运算符：按位或 。

小苯想知道，有多少种不同的擦黑板方式，能使得按照新算式进行计算，结果和擦黑板前的算式计算结果相同，请你帮他算一算。注意，不擦黑板也是一种方案。由于答案可能很大，请将答案对 取模后输出。

【注】

• 特别的，在本题中我们认为 运算符的优先级大于加法运算 +。
• 两种擦黑板方式不同当且仅当存在至少一个运算符位置，其在其中一个方式中为 +，而在另一个方式中为 |（即按位或 ）。

【名词解释】 or：指位运算中的按位或（Bitwise OR），对两个整数的二进制表示按位进行或运算。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下： 第一行输入一个整数 ，表示黑板上的数字个数。 第二行输入 个整数 ，表示黑板上的数字。 保证单个测试文件的 之和不超过 。

输出描述

对于每一组测试数据，新起一行输出一个整数，表示不同的擦黑板方案个数对 取模后的答案。

解题思路

1. 动态规划状态定义： 可以理解到合法的 | 的插入是没有后效性的，不影响后面运算的结果。 我们定义 为以第 个数字结尾的合法运算序列的方案数。最终答案为 （这里为了方便处理边界，通常在原数组后将计算推至末尾）。

2. 转移条件的等价转换： 第 个位置的方案可以转移到第 个位置，等价于区间 内的元素先进行 | 运算后再相加，结果等于直接相加的结果。即： 由于 or 运算优先级高，这个条件等价于任意两个参与运算的数在二进制位上没有重合，即： 更简单地说，随着区间左端点 向左扩展，区间按位或的值 val 必须满足 (val & a[j]) == 0。

   举例说明： 当 。 可以由 转移得到。 但是当从 往前推到 时，累积的或值为 ，此时 (0011) 有重合位，不符合条件，因此 也无法转移。

3. 两个关键问题的优化：

   • 问题 1：如何高效地往前查找最远的 j？ 每一次从i往前找，遍历的找的话，估算来说还是n^2的不可接受，考虑到a[i]|a[j] == a[i]+a[j]这个公式等价于a[i]&a[j]==0,即二进制位没有重合的位置，如果按照二进制位去理解，最多只能去找31个正整数，完全不怕TLE，但是每一个0都符合a[i]&a[j]==0，会形成每一个i的位置往前查找了最多31个正整数和极多的0的情况，故我们需要跳过没有意义的0的位置，每次查找到一个符合条件的正整数x，就往前跳到x前面最近的正整数y，再从y往前跳，最多跳31次（logn级别）完全可以接受。
     

   • 问题 2：如何高效地计算区间 DP 和？ 每一次找到了最远的j，dp[i]=dp[j]+..+dp[i-1]，每一次都需要遍历一遍去计算的话，由于上一个问题中提及到[j,i-1]的区间中会存在极多的0的情况，遍历计算的复杂度也会趋近于n^2的复杂度，无法接受。由于计算过的dp[1]...dp[i-1]都是不会改变的，为了高效地查找一个区间值，选择使用前缀和思想，维护一个dp的前缀和数组pre，即 pre[j]=dp[1]+dp[2]+..+dp[j],则dp[j]+dp[j+1]+...+dp[i-1] 等价于 pre[i-1]-pre[j-1]. 再计算dp[i]之后,维护第i个位置前缀和值：pre[i]=pre[i-1]+dp[i].
     

现在已经解决了所有问题，编写你自己的代码吧，你一定能写出来优美的C++代码，你说你要写python吗，你说你要写python吗，你说你要写python吗！！！咕咕嘎嘎！！

PS

是一个非常好的前缀和优化DP的入门题，赛时想到了线性DP就下机了，在查找j的过程中使用ST表我也能理解，使用双指针的话，目前没有比较成熟的实现想法。

AC 代码

void inpu() {
    cin >> n;
    int temp = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        idx[i] = temp; // 记录当前位置左边最近的非0元素的下标
        if (a[i]) temp = i;
    }
}
void solve() {
    inpu();
    // dp[1] 代表第 0 个缝隙（起始）只有一种方案
    dp[1] = pre[1] = 1;
    for(int i=1,j;i<=n;i++){
        int val=0;
        for(j=i;j>=0&&((val&a[j])==0);j=idx[j]){
            val|=a[j];
        }
        dp[i]+=(pre[i-1]-pre[j-1]+mod)%mod;
        pre[i]=(pre[i-1]+dp[i])%mod;
    }
    cout << dp[n + 1] << "\n";
    return;
}

9. D-Sequence Coloring

题目描述

给定一个长度为 的数字序列 ，每一个元素都有一个颜色，且初始时要么为白色，要么为黑色，使用其值的大小表示其颜色：若 ，则第 个元素为白色；否则为黑色。

小苯可以在第 秒时选择其中至多 个 白色 元素染红，随后，从第 秒开始，每秒都会发生如下事件：

• 对于第 个元素 ，如果它是 红色 的，那么将其右侧 个元素中的 白色 元素也染红。
• 形式化地，对于所有红色元素所在的位置 ，将第 到第 个元素中的 白色 元素也染红；
• 所有的红色元素同步进行这一操作（即每一秒开始时已经是红色的元素，会在该秒内尝试染红其它元素）；
• 黑色元素并不会、也无需被染红。

请你帮助小苯以最优策略染色最初的数字，使得所有的白色元素都被染红的时间尽可能短（可以为 秒）。求出这个最短时间，或报告无论如何都无法将所有的白色元素都染红。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数。 每组测试数据的第一行输入两个整数 ，表示数字序列的长度、最开始可以染红的元素个数。 第二行输入 个整数 ，表示序列中的元素。其中 表示白色， 表示黑色。 保证单个测试文件的 之和不超过 。

输出描述

对于每一组测试数据，新起一行。如果可以将所有的白色元素都染红，输出一个整数表示最短的全染红时间；否则输出 。

解题思路

红色点的扩展只允许向右边，因此我们需要采取贪心策略结合二分答案来解决。

1. 贪心策略： 我们选择的点，要从左向右贪心地选择。

   • 没有被覆盖的白色点一定要被选择。
   • 被选择的白色点一定要扩展到最后一秒（除非扩展后右边没有白点了）。

2. 二分答案： 按照以上的贪心思路，每一次二分答案（假设时间为 ）：

   • 每一个选择的白点扩展到时间上界（ 秒）后，就寻找下一个未被覆盖的白点。
   • 如果在遍历过程中没有白点了就直接结束。
   • 统计过程中使用的初始白点数量，如果超过 就直接 return false。

PS

难度不高，求最小时间，一个标准的贪心+二分题。

AC 代码

void inpu() {
    cin >> n >> k;
    c1 = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] > 0) c1++;
    }
    // 预处理每个点向右覆盖的范围
    idx[1] = 1 + a[1];
    for (int i = 2; i <= n; i++)
        idx[i] = min(max(idx[i - 1], i + a[i]), n);
}
bool check(int x) {
    int cur = 1, tmp = 0, num = 1;
    // 找到第一个白色点的位置
    for (cur = 1; cur <= n; cur++) if (a[cur] > 0) break;
    if (cur > n) return false;
    
    while (cur < n) {
        if (tmp == x) {
            // 时间耗尽，需要开启新的染色源
            int next = cur + 1;
            while (next <= n && a[next] == 0) next++;
            if (next > n) return true;
            num++;
            if (num > k) return false;
            cur = next, tmp = 0;
        } else {
            // 继续利用当前的染色源扩展
            tmp++;
            cur = idx[cur];
            if (cur >= n) return num <= k;
        }
    }
    return num <= k;
}

void solve() {
    inpu();
    // 如果 k 足够覆盖所有白点（每个白点都选），直接输出 0
    if (k >= c1) {
        cout << 0 << "\n";
        return;
    }
    int ans = inf;
    int l = 1, r = n, mid;
    while (l <= r) {
        mid = l + ((r - l) >> 1);
        if (check(mid)) {
            ans = min(ans, mid);
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    if (ans == inf) ans = -1;
    cout << ans << "\n";
}

10. I-AND vs MEX

题目描述

小苯有一个可重整数集合 ，初始为空。现在他可以进行任意次以下操作，给 中加入一些元素，具体的：
他可以从区间 中选择若干个（至少一个）不同的整数，将这些整数的 （按位与）加入集合 。
他可以做任意次上述操作，请问 的 最大可以达到多少。

【名词解释】
AND：指位运算中的按位与（Bitwise AND），对两个整数的二进制表示按位进行与运算。如果您需要更多位运算相关的知识，可以参考 OI-Wiki的相关章节。
MEX：整数集合的 定义为没有出现在集合中的最小非负整数。例如，、。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：

在一行上输入两个整数 ，表示区间。

输出描述

对于每一组测试数据，新起一行输出一个整数，表示最大的 。

解题思路

若 l==0,结果一定是r+1
若 l和r的最高位相同。无法消除最高位1.结果一定是0
若 higtbit(r)>highbit(l)+1: 因为r极大，掩码M和偏移量P+k都在，直接通过复制粘贴低位，填满[0, l]，答案依旧是r+1。
若 higtbit(r)=highbit(l)+1: l 可以构造一个下界[ll,l]，[l,r]可以填满[0,rr(r-1ll<<highbit(r))]，如果rr+1>=ll，则全部填满，答案是r+1，否则答案是rr+1

PS

位运算好难
你说我写不出来
现在就退役

AC 代码

int check(int l){
    int res=0;
    bool flag=0;
    for(int i=32;i>=0;i--){
        if(l>>i&1)res+=1ll<<i,flag=1;
        else {
            if(flag==1)return res;
            else continue;
        }
    }
    return res;
}
int highbit(int x){
    for(int i=32;i>=0;i--){
        if(x>>i&1)return i;
    }
    return -1;
}
void check(int l,int r){
    if(l==0){
        cout<<r+1<<"\n";return;
    }
    int ll=highbit(l),rr=highbit(r);
    if(ll==rr){
        cout<<0<<"\n";return ;
    }
    if(rr>=ll+2){
        cout<<r+1<<"\n";return ;
    }
    int LL=check(l);
    int RR=r-(1ll<<rr);
    if(RR+1>=LL){
        cout<<r+1<<"\n";
        return ;
    }
    else{
        cout<<RR+1<<"\n";
        return ;
    }
}

11. J-MST Problem

题目描述

小苯拿到了一个由 个点、 条边组成的无向完全图，没有重边和自环，其中第 个点的点权为 。 两点之间的边权为 。

而调皮的小红删除掉了其中一些边，导致图不再是一个完全图，具体来讲有 条删除记录，第 条记录由一个点对 组成，表示小红删除了这条边。注意，记录可能有重复，即可能存在两条记录删除的边是一样的。

现在你的任务就是求出这张图的最小生成树的权重（树中所有边的权重之和最小）。如果此时图不存在最小生成树，则输出 。

【名词解释】
最小生成树：对于一张由 个节点构成的连通图，选出 条边将所有节点连通，且使得这 条边的权重之和最小，这样的结构称为最小生成树。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：

第一行输入两个整数 ，表示图的节点个数、小红删除边的记录条数。
第二行输入 个整数 ，表示每个节点的点权。
接下来 行，第 行输入两个正整数 ，描述第 条删除记录。

除此之外，保证单个测试文件的 之和、 之和均不超过 。

输出描述

对于每一组测试数据，新起一行输出一个整数，如果此时图存在最小生成树，则输出整张图的最小生成树的权重；否则直接输出 。

PS

完全图求最小生成树
似乎已经把boruvka完全忘记了，也把网络赛C题的数据结构优化也忘记了，很想写一下J题，一定会排上日程的