2026牛客寒假算法基础集训营1
赛时锐评
赛中AC顺序为L 、 C 、K 、E 、A
难度：A > E > C > K > L
赛后AC顺序：B 、G 、D 、H
总难度：H > D > A > G > E > B > C > K > L
L
题目链接：https://ac.nowcoder.com/acm/contest/120561/L
思路：
暴力枚举
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
template<class T>
void solve(){
int n;
std::cin >> n;
int cnt = n % 10, k = 0;
if(cnt == 0) k = 1;
else if(cnt == 1 || cnt == 3 || cnt == 7 || cnt == 9) k = 10;
else if(cnt == 2 || cnt == 4 || cnt == 6 || cnt == 8) k = 5;
else if(cnt == 5) k = 2;
std::cout << k << "\n";
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t=1;
// cin>>t;
while(t--)
solve<int>();
return 0;
}
K
题目链接：https://ac.nowcoder.com/acm/contest/120561/K
思路：
暴力枚举
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
template<class T>
void solve(){
int n;
std::cin >> n;
if(n == 1){
std::cout << "YES\n";
std::cout << "1\n";
}else if(n == 3){
std::cout << "YES\n";
std::cout << "1 2 3\n";
}else{
std::cout << "NO\n";
}
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t=1;
cin>>t;
while(t--)
solve<int>();
return 0;
}
C
题目链接：https://ac.nowcoder.com/acm/contest/120561/C
思路：
可以知道任选一个区间，他们的开区间的值都可以取最大，所以我们只需要知道首尾元素的值，因为两端必然不会改变，中间值可以通过改变变成最值。
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
template<class T>
void solve(){
int n;
std::cin >> n;
std::vector<int> a(n);
for(auto &x : a) std::cin >> x;
if(n == 1){
std::cout << a[0] << "\n";
return ;
}
int cnt = *max_element(a.begin(), a.end());
std::cout << 1LL * (n-2) * cnt + a[0] + a[n-1] << "\n";
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t=1;
cin>>t;
while(t--)
solve<int>();
return 0;
}
E
题目链接：https://ac.nowcoder.com/acm/contest/120561/E
思路：
循环遍历n便即可，没回算k和首元素是不是最大值，是就更新。
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
template<class T>
void solve(){
i64 n, k;
std::cin >> n >> k;
std::deque<i64> s;
for(int i = 1;i <= n; i++){
int x;
std::cin >> x;
s.push_back(x);
}
i64 cnt = 0, mx = -1E9;
while(!s.empty()){
cnt ++;
if(cnt > n+1) break;
i64 ans = s.back();
s.pop_back();
s.push_front(k);
mx = max(k+ans, mx);
k = ans;
}
std::cout << mx << "\n";
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t=1;
cin>>t;
while(t--)
solve<int>();
return 0;
}
A
题目链接：https://ac.nowcoder.com/acm/contest/120561/A
思路：
先算出每个数字的概率（0~9）
然后就是四位数重组选出合适的数相乘
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
i64 ksm(i64 x, i64 y){
i64 ans = 1;
while(y > 0){
if(y & 1){
ans = ans * x % INF;
}
y >>= 1;
x = x * x % INF;
}
return ans;
}
template<class T>
void solve(){
//先算好每个数字出现的概率
int c;
std::cin >> c;
std::vector<int> p(8);
for(int i = 1;i < 8; i++){
std::cin >> p[i];
}
std::vector<i64> a(10, 1);
for(int i = 1;i < 8; i++){
if(i == 4) a[0] = a[0] * (100 - p[i]) % INF * ksm(100, INF-2) % INF;
else a[0] = a[0] * p[i] % INF * ksm(100, INF-2) % INF;
}
for(int i = 1;i < 8; i++){
if(i != 3 && i != 6) a[1] = a[1] * (100 - p[i]) % INF * ksm(100, INF-2) % INF;
else a[1] = a[1] * p[i] % INF * ksm(100, INF-2) % INF;
}
for(int i = 1;i < 8; i++){
if(i == 2 || i == 6) a[2] = a[2] * (100 - p[i]) % INF * ksm(100, INF-2) % INF;
else a[2] = a[2] * p[i] % INF * ksm(100, INF-2) % INF;
}
for(int i = 1;i < 8; i++){
if(i == 2 || i == 5) a[3] = a[3] * (100 - p[i]) % INF * ksm(100, INF-2) % INF;
else a[3] = a[3] * p[i] % INF * ksm(100, INF-2) % INF;
}
for(int i = 1;i < 8; i++){
if(i == 1 || i == 5 || i == 7) a[4] = a[4] * (100 - p[i]) % INF * ksm(100, INF-2) % INF;
else a[4] = a[4] * p[i] % INF * ksm(100, INF-2) % INF;
}
for(int i = 1;i < 8; i++){
if(i == 3 || i == 5) a[5] = a[5] * (100 - p[i]) % INF * ksm(100, INF-2) % INF;
else a[5] = a[5] * p[i] % INF * ksm(100, INF-2) % INF;
}
for(int i = 1;i < 8; i++){
if(i == 3) a[6] = a[6] * (100 - p[i]) % INF * ksm(100, INF-2) % INF;
else a[6] = a[6] * p[i] % INF * ksm(100, INF-2) % INF;
}
for(int i = 1;i < 8; i++){
if(i == 2 || i == 4 || i == 5 || i == 7) a[7] = a[7] * (100 - p[i]) % INF * ksm(100, INF-2) % INF;
else a[7] = a[7] * p[i] % INF * ksm(100, INF-2) % INF;
}
for(int i = 1;i < 8; i++){
a[8] = a[8] * p[i] % INF * ksm(100, INF-2) % INF;
}
for(int i = 1;i < 8; i++){
if(i == 5) a[9] = a[9] * (100 - p[i]) % INF * ksm(100, INF-2) % INF;
else a[9] = a[9] * p[i] % INF * ksm(100, INF-2) % INF;
}
i64 cost = 0;
for(int i = 0;i < 10; i++){
for(int j = 0;j < 10; j++){
for(int k = 0;k < 10;k++){
for(int l = 0;l < 10; l++){
i64 ans = a[i] * a[j] % INF * a[k] % INF * a[l] % INF;
int num1 = i * 1000 + j * 100 + k * 10 + l;
if(num1 > c) continue;
i64 num2 = c - num1;
int x1,x2,x3,x4;
x4 = num2 % 10, num2 /= 10;
x3 = num2 % 10, num2 /= 10;
x2 = num2 % 10, num2 /= 10;
x1 = num2 % 10, num2 /= 10;
i64 chance = a[x1] * a[x2] % INF * a[x3] % INF * a[x4] % INF;
cost = (cost + ans * chance % INF) % INF;
}
}
}
}
std::cout << cost << "\n";
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t=1;
cin>>t;
while(t--)
solve<int>();
return 0;
}
B
题目链接：https://ac.nowcoder.com/acm/contest/120561/B
思路：
每次选择牌的时候大的牌删除，分数+1，小的牌保留，分数不变。
我们只需要找到b的最小值，a中比bmin的数要大的数我们都放在上面必然会全部删除，比bmin小的数必然不会被删除，我们就把他们放下面，最后上面的牌自由排序，下面的牌自由排序。结果就是上面的阶乘与下面阶乘的乘积。
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
i64 inv[1000009];
i64 f_inv[1000009];
i64 ksm(i64 x, i64 y){
i64 ans = 1;
while(y > 0){
if(y & 1){
ans = ans * x % INF;
}
y >>= 1;
x = x * x % INF;
}
return ans;
}
void inint(){
inv[0] = 1;
for(int i = 1;i <= 1000000; i++){
inv[i] = inv[i-1] * i % INF;
}
f_inv[1000000] = ksm(inv[1000000], INF-2);
for(int i = 999999; i >= 0; i--){
f_inv[i] = f_inv[i+1] * (i+1) % INF;
}
}
i64 C(int n, int m){
if(n < m || n < 0 || m < 0) return 0;
return inv[n] * f_inv[n-m] % INF * f_inv[m] % INF;
}
i64 A(i64 n, i64 m){
i64 ans = 1;
for(int i = n;i >= n - m + 1; i--) ans = ans * i % INF;
return ans;
}
template<class T>
void solve(){
int n;
std::cin >> n;
std::vector<int> a(n), b(n);
for(auto &x : a) std::cin >> x;
for(auto &x : b) std::cin >> x;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
i64 ans = 0, cnt = 0, l = 0, r = 0, k = 0;
//比minb小的放一边，大的放一边
for(int i = 0;i < n; i++){
if(a[i] > b[0]) ans ++;
else cnt ++;
}
std::cout << A(ans, ans) * A(cnt, cnt) % INF << "\n";
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t=1;
cin>>t;
inint();
while(t--)
solve<int>();
return 0;
}
G
题目链接：https://ac.nowcoder.com/acm/contest/120561/G
思路：
左右边界有两种情况，一种是左边界的长度与有边界的长度一样，另一种就是左边界长度比右边界小。
对于第二种情况我们把区间（xxx-yyyyy）-----（10000-yyyyy）并不会影响我们的最终结果，然后对比这两个边界从左往右找到第一个不同的位置不到最后一个位置将其记录下来
Eg:1243009~1245009,124相同我就保持不变，5就减一变为4，后面就全换为9，变成1244999，翻转9994421
为什么不能改变最后一个位置呢，因为要改变那最后一个位置必然要减1，而我们翻转的第一位就是未翻转的最后一位，减少必然对应值会变小。
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
template<class T>
void solve(){
string l, r, k;
std::cin >> l >> r;
k = r;
string t(1, '1');
int len = r.size();
if(len == 1){
std::cout << r << "\n";
return ;
}
for(int i = 2;i <= len;i++) t = t + '0';
if(l.size() < len && t == r){
for(int i = 1;i < len; i++) std::cout << '9';
std::cout << "\n";
return ;
}
if(l.size() < len){
l = t;//缩小区间范围。eg:xxxx~yyyyy------10000~yyyyy
}
int ans = len;//前几位相同保留找到不相同的第一个位置，保证r[i] > l[i],那r[i]一定是大于'0'的
//如果前面都没有改变的话，最后一个位置不能动
for(int i = 0;i < len-1; i++){
if(l[i] != r[i]){
r[i] --;
ans = i+1;
break;
}
}
//后面的r[i]全换为'9'
for(int i = ans; i < len; i++){
r[i] = '9';
}
reverse(r.begin(), r.end());
reverse(k.begin(), k.end());//防止出现有边界是999999的情况，根据上面来会翻成999998
while(k.front() == '0') k.erase(k.begin());
while(r.front() == '0') r.erase(r.begin());
if(k.size() > r.size()) r = k;
else if(k.size() == r.size()) r = max(k, r);
std::cout << r << "\n";
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t=1;
cin>>t;
while(t--)
solve<int>();
return 0;
}
D
题目链接：https://ac.nowcoder.com/acm/contest/120561#question
思路：经典的二分，不断划分时间，对于每个白球我们先对第一格球染红，然后赋予mid时间来通过蝶群效应把他们也染红，注意此次染色用掉的染红次数实际只有一次，过完之后开始第二次染色重复上面操作，当然也会遇见0的情况，跳过就行。
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
template<class T>
void solve(){
int n, k;
std::cin >> n >> k;
std::vector<i64> a(n), pre(n+10);
for(int i = 0;i < n; i++) std::cin >> a[i];
pre[0] = a[0];
for(int i = 1;i < n; i++) pre[i] = max(pre[i-1], i+a[i]);
int ans = 0;
for(int i = 0;i < n; i++) if(a[i] > 0) ans ++;
int l = 0, r = n, s = 0;
bool ko = false;
while(l < r){
i64 mid = (l + r) >> 1;
s = k;
i64 time = mid;
i64 mx = 0;//白球染红的范围
for(int i = 0;i < n; i++){
if(a[i] == 0) continue;
s --;
int j = i;
time = mid;
while(time > 0 && j < n){
mx = max(mx, pre[j]);
time --;
j = pre[j];
}
i = j;
}
if(s >= 0){
r = mid;
ko = true;
}else{
l = mid + 1;
}
}
if(!ko){
std::cout << "-1\n";
}else{
std::cout << l << "\n";
}
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t=1;
cin>>t;
while(t--)
solve<int>();
return 0;
}
H
题目链接：https://ac.nowcoder.com/acm/contest/120561/H
思路：想要将加号变为或，那加和与或和必须要相等，想到dp，把他分为几个板块，每个板块就以加或隔开。
xxxx|xxx|xxx|xx|xxx,我们可以来分析当前子问题是第i个数取|时，我们找到前面能与他或和等于加和的都能够满足，假设他能连续或到前面第j位[j, i]直接都可以用|隔开，dp[i] = dp[j] + dp[j+1] + dp[j+2] ... + dp[i]
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
template<class T>
void solve(){
int n;
std::cin >> n;
std::vector<int> a(n+1), pre(n+10);
for(int i = 1;i <= n; i++) std::cin >> a[i];
int st = 0;
for(int i = 1;i <= n; i++){
pre[i] = st;
if(a[i] != 0) st = i;
}
/*
****|*****|**|****
dp[j] + dp[j+1] + ... + dp[i]
*/
std::vector<i64> dp(n+10), s(n+10);
dp[1] = 1;
s[1] = 1;
for(int i = 1;i <= n; i++){
int val = 0;
int j = i;
while(j > 0 && (val & a[j]) == 0){
val |= a[j];
j = pre[j];
}
dp[i+1] = (s[i] - s[j] + INF) % INF;
s[i+1] = (s[i] + dp[i+1]) % INF;
}
std::cout << dp[n+1] << "\n";
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t=1;
cin>>t;
while(t--)
solve<int>();
return 0;
}
