2026牛客寒假算法基础集训营1
比赛链接
L. Need Zero
题目简介：
给定一个正整数 ，求最小的正整数
使得
的个位数为
。
思路：
无论 是多少，最大的
一定是
，因为任何数字乘以
个位数一定是
，因此，从
到
遍历
即可。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
for(int i=1;i<=10;i++)
{
int t=n*i;
if(t%10==0)
{
cout<<i;
return 0;
}
}
return 0;
}
K. Constructive
题目简介：
构造一个长度为 的数组
满足
- 数组中每个元素
都是正整数；
- 所有元素的乘积等于所有元素的和；
- 数组中的元素互不相同。
若存在，按字典序输出数组，否则输出
思路：
当 时，易得
成立。
当 时，则有
即
得
不符合题意。
当 时，易得
成立。
当 时，易得，无解。
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;cin>>n;
if(n==1) cout<<"YES"<<endl<<"1"<<endl;
else if(n==3) cout<<"YES"<<endl<<"1 2 3"<<endl;
else cout<<"NO"<<endl;
return;
}
int main()
{
int T;cin>>T;
while(T--) {
solve();
}
return 0;
}
C. Array Covering
题目简介：
给定一个长度为 的数组
，其中第
个数值为
。
以下操作可以进行任意次
- 选取两个下标
，使得区间
中的数字全部变为两下标中的最大值。
求出数组总和的最大值。
思路：
若原数组最大值为左端点或者右端点，则选取的下标为 ，区间
中的数字全部变为两下标中的最大值。
若原数组最大值下标为 ，则第一次选取的下标为
，区间
中的数字全部变为
，第二次选取的下标为
，区间
中的数字全部变为
。
无论哪一种情况，最终的结果均为两端点值不变，其余的值变为数组最大值。
#include<bits/stdc++.h>
#define int long long
#define N 500010
using namespace std;
int a[N];
void solve()
{
int n;cin>>n;
int mmax=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
mmax=max(mmax,a[i]);
}
cout<<a[1]+a[n]+mmax*(n-2)<<endl;
return;
}
signed main()
{
int T;cin>>T;
while(T--) {
solve();
}
return 0;
}
E. Block Game
题目简介：
将万能方块插入队尾，然后计算相邻两个方块的最大值即可。
思路：
从第一个开始遍历，计算相邻两个方块的最大值，首和尾特殊处理。
#include<bits/stdc++.h>
#define int long long
#define N 200010
using namespace std;
void solve()
{
int n,k;cin>>n>>k;
int a[N],ans=INT_MIN;
a[0]=k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
ans=max(ans,a[i]+a[i-1]);
}
cout<<max(ans,a[0]+a[n])<<endl;
return;
}
signed main()
{
int T;cin>>T;
while(T--) {
solve();
}
return 0;
}
B. Card Game
题目简介：
共有 张牌，恰好为长度
的排列，小苯和小红每人
张，第
张牌分别为
和
，具体的游戏过程如下：
- 如果两人之中有一人已经没有牌了，则游戏结束。
- 比较两人当前手牌中的最前一张，对应数字大的那一方得一分并将该张牌从自己手牌移除；另一方不得分，手牌也不变。随后进入下一轮。
而现在小苯希望自己的得分尽可能多，为此他在游戏开始前可以任意地重新排列自己的牌，以得到更高的游戏分数。
现在你的任务则是求出，有多少种重新排列（选择不进行重排也是一种方案）的方式，能使得小苯得到他能得到的最高分。由于答案可能很大，请将答案对 取模后输出。
思路：
我们只需要考虑小苯得到最高的分数即可，对于小红的分数不用考虑，由题意得，只要数字较大，就移除该牌且得一分，数字较小的不变，因此，只要小苯手中有比小红最小的手牌大的牌，就可以用这张牌和小红最小的手牌比较得一分，而为了避免因为和小苯手中比小红最小的手牌还要小的手牌比较导致小红最小的手牌被丢弃，我们需要将小苯手中比小红最小的手牌大的手牌优先比较，将小苯手中比小红手中最小的手牌小的手牌最后比较，若小苯手中比小红最小的手牌大的手牌的数量是 ，则小的手牌数量是
，则排列的方式共有
#include<bits/stdc++.h>
#define mod 998244353
#define int long long
#define N 200010
using namespace std;
int a[N],b[N];
bool cmp(int a,int b)
{
return a<b;
}
int calc(int k)
{
int ans=1;
for(int i=1;i<=k;i++)
ans=(ans*i)%mod;
return ans%mod;
}
void solve()
{
int n;cin>>n;
int cnt=0;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
sort(a+1,a+n+1,cmp);
sort(b+1,b+n+1,cmp);
for(int i=1;i<=n;i++)
{
if(a[i]>b[1])
{
cnt=i-1;
break;
}
}
cout<<((calc(cnt)%mod)*(calc(n-cnt)%mod)%mod)<<endl;
return;
}
signed main()
{
int T;cin>>T;
while(T--) {
solve();
}
return 0;
}