挑战赛#32 全题解
2026-06-12 21:49:42
发布于：浙江
59阅读
0回复
0点赞
纪念。
我没拿到奖。
拿奖你配吗？
道普及- 道入门挑战赛正向欢乐赛靠拢。
T1 项目计划
这道题我们先求出总共的时间（以秒为单位），再将时间平分到条线上，用时最长的就是答案。
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, h, mm, s;
int main()
{
cin>>n>>m;
scanf("%d:%d:%d",&h,&mm,&s);
long long ms=1LL*h*3600+mm*60+s;//统一单位
long long sum=(n+m-1)/m;//取上整
long long hs=1LL*sum*ms;
cout<<hs/3600<<":"<<(hs%3600)/60<<":"<<hs%60;
}
关于取上整的公式，你可以参考这篇帖子里我给出的回复。
T2 千载难逢的良缘
模拟。我们只需要一次遍历数组的元素并加以判断即可，由小到大的遍历也天然满足了输出最小的分数。注意遍历前要确保数组是有序的，所以我们要用 进行对数组的排序。
#include <iostream>
#include <algorithm>
using namespace std;
int n, a[1000005], minn=1e9, mini, mini1;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i = 1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
for(int i = 1;i<n;i++)
{
if(abs(a[i+1]-a[i])<minn)//绝对值可以不加
{
mini=a[i];
mini1=a[i+1];
minn=abs(a[i+1]-a[i]);//更新各项内容
}
}
cout<<minn<<"\n"<<mini<<" "<<mini1;//输出
}
T3 保险金
还是模拟。这道题判断即可，但要注意只有发了才会被输出，所以需要用int类型的标记(也就是数组的长度)来判断发了没有。
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
struct node
{
string id;
int m;
long long je[1005];
}p[1005];
int main()
{
long long t, total=0;
int n, cnt=0;
cin>>t;
cin>>n;
for(int i = 1;i<=n;i++)
{
cin>>p[i].id>>p[i].m;
for(int j = 1;j<=p[i].m;j++)
{
cin>>p[i].je[j];
}
sort(p[i].je+1,p[i].je+p[i].m+1);//按钱数排序
}
long long h=t;//代替总钱数
for(int i = 1;i<=n&&h>0;i++)
{
if(p[i].je[1]>h) break;
bool f=false;
long long s[1005];
int len=0;
for(int j = 1;j<=p[i].m;j++)
{
if(p[i].je[j]<=h)//能发
{
cnt++;
total+=p[i].je[j];
h-=p[i].je[j];
s[len++]=p[i].je[j]; //更新各项
}
else
{
f=true;
break;//不能发就结束
}
}
if(len>0)//发了
{
cout<<p[i].id;
for(int j = 0;j<len;j++)
{
cout<<" "<<s[j];
}
cout<<"\n";
}
if(f) break;
}
cout<<cnt<<" "<<total;
}
T4 晋级赛
二分。我们只要用 lower_bound函数找到第一个的地址，再减去，也就是起始地址，就可以得出前面所有的元素个数。
#include <iostream>
#include <algorithm>
using namespace std;
long long n, a[1000005], m;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i = 1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
while(m--)
{
long long x;
cin>>x;
cout<<lower_bound(a+1,a+n+1,x)-(a+1)<<"\n";
}
}
T5 科技展示
双倍经验的，A139.组合的输出改下输出格式就能过。
简单的 dfs ，感谢月恶补了广深搜。对于 dfs 函数先判断能否输出，可以就输出一组答案，不能就用比大的数再去尝试。
#include <iostream>
using namespace std;
int n, m, a[30];
void dfs(int x, int y)
{
if(x>m)
{
for(int i = 1;i<=m;i++)//一组输出
{
cout<<a[i]<<" ";
}
cout<<"\n";
return;
}
else
{
for(int i = y;i<=n;i++)//当前选的数
{
a[x]=i;
dfs(x+1,i+1);//下个比i大
}
}
}
int main()
{
cin>>n>>m;
dfs(1,1);
}
T6 活动筹备计划
基础的 dp 。我们使用滚动数组来解决，因为选了不能选和，那我们只需要去存前一天能到的最大值（也就是出去今天选项的其他选项的最大值），再加上今天的即可。
#include <iostream>
#include <algorithm>
using namespace std;
long long p[4], w[4][4];//滚动数组省空间
long long a[200005][4], ans;
int main()
{
int n;
cin>>n;
for(int i = 1;i<=3;i++)
{
for(int j = 1;j<=3;j++)
{
cin>>w[i][j];
}
}
for(int i = 1;i<=n;i++)
{
cin>>a[i][1]>>a[i][2]>>a[i][3];
}
p[1]=a[1][1];
p[2]=a[1][2];
p[3]=a[1][3];
for(int i = 2;i<=n;i++)
{
long long s[4]={};//临时数组存此刻三种选择
s[1]=max(p[2]+w[2][1], p[3]+w[3][1]) +a[i][1];//选择1
s[2]=max(p[1]+w[1][2], p[3]+w[3][2]) +a[i][2];//选择2
s[3]=max(p[1]+w[1][3], p[2]+w[2][3]) +a[i][3];//选择3
p[1]=s[1],p[2]=s[2],p[3]=s[3]; //更新数组
}
ans=max({p[1],p[2],p[3]});//取三种最大值
cout<<ans;
}
总结
挑战赛最人性的一次。希望以后还是多出点黄/绿，但是这种的不要停。
有帮助，赞一个