A题
题目描述
思路
签到题，模拟+暴力枚举区间内所有数，判断是否满足条件
注意
这题不能直接枚举区间a-b中的所有数再判断是否满足要求,因为a,b的数据范围为1-1018,最坏情况下区间可能会有1018个数，暴力枚举的话会TLE。但是我们可以枚举1~106的所有数x,判断x3是否满足要求，若满足要求则计数+1，因为106*3等于1018，因此可以包含所有可能满足条件的数，并且时间复杂度为O(106)
参考代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10;
typedef long long LL;
LL l,r,x;
int ans;
// 判断val^3构成的数temp是否满足条件
// 即temp是否在[l,r]中，并且是x的倍数
bool check(int val)
{
LL temp=val*val*val;
if(temp>=l && temp<=r && temp%x==0) return true;
return false;
}
int main()
{
// 注意l,r一定要开long long
scanf("%lld%lld%lld",&l,&r,&x);
for(int i=1;i<=N;i++)
{
if(check(i)) ans++;
}
printf("%d",ans);
return 0;
}
B题
题目描述
思路
记录第i次之前出现过的所有数，依次枚举第i次读入的数的幂运数，如果出现过就计数并且累加求和，时间复杂度O(nlogn)，具体细节见下方参考代码
参考代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10;
const int MOD=99999;
int visit[N]; //记录每个数是否出现过，以及其出现的次数
int T;
int main()
{
scanf("%d",&T);
int maxx=0; // 记录当前输入的数的最大值，确定后续查找幂运数的范围
while(T--)
{
int x;
int cntt=0; // 记录当前幂运数出现的次数
int sum=0; // 记录所有幂运数的和
scanf("%d",&x);
int temp=x*x;
while(temp<=maxx) // 所有前面的幂运数一定小于等于当前出现过的数的最大值
{
cntt+=visit[temp];
// 这里同一个幂运数可能出现多次，所以temp已经乘上visit中的出现次数
sum=(sum+temp*visit[temp])%MOD;
temp*=x;
}
printf("%d %d\n",cntt,sum);
visit[x]++; // 记录当前的数
maxx=max(maxx,x);
}
return 0;
}
C题
题目描述
思路1(最小生成树)
该题可以将题中的每个厂房看成一个点，由当前点与其他点构成的点对为一条边，边的权值为当前两点之前的长度，由此可以构建出共C2条边。我需要在这些边中选择S-K条边，使得构成的联通块总权值和最小，游戏很容易可以联想到最小生成树算法。在克鲁斯卡尔算法中，每合并一条边，用并查集维护的图中的连通块就会-1。每一个连通分量都是一段连续的钢板，连通分量内权值之和就是当前钢板所需的总长度。当我们合并C-M条边之后，图中只剩下C个连通分量，刚好每个联通分量可以对应一个钢板，每个连通分量对应的总权值之和就是所需的最小长度。
参考代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=55,M=210;
struct edge
{
int l,r,w;
}edges[M*M]; // 边集数组，一共会有M*M条边
int a[M];
int fa[M]; // 并查集的祖先数组
int n,m,k; // k表示可以用的钢板数，n表示总厂房数量，m表示有物品的厂房数量
int cnt;
bool cmp(struct edge a,struct edge b)
{
return a.w<b.w;
}
int find(int x) // 并查集查找函数
{
if(x==fa[x]) return fa[x];
return fa[x]=find(fa[x]);
}
int kruscal() // 克鲁斯卡尔算法
{
sort(edges+1,edges+1+cnt,cmp);
int res=0;
int count=0; //总联通分量的个数
for(int i=1;i<=cnt;i++)
{
int x=edges[i].l;
int y=edges[i].r;
int w=edges[i].w;
int xx=find(x);
int yy=find(y);
if(xx!=yy)
{
fa[xx]=yy;
res+=w;
count++;
}
if(count==m-k) break;
}
return res;
}
int main()
{
scanf("%d%d%d",&k,&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d",&a[i]);
// 创建每个点对之间的边，因为是枚举的点对，所以j每次只需要枚举1~i-1即可
for(int j=1;j<i;j++) edges[++cnt]={i,j,abs(a[i]-a[j])};
}
// 初始化每个节点的祖先
for(int i=1;i<=m;i++) fa[i]=i;
// 在计算边权时，只加了一个点到另一个点的距离，没有加另一个端点的1
printf("%d",kruscal()+k);
return 0;
}
思路二(贪心)
我们可以对厂房的位置降序排序，从最小值到最大值之间的距离就是只有1块钢板的总长度。若可以用K块钢板，就相当于我们可以在最小值到最大值的这一段之间放K-1个隔板，假如我们在2号点和3号点之间放一块隔板，那我相当于2号点与其相连的一段用一块独立的钢板，3号点与其相连的其他点用另一块独立的钢板，那么2和3之前的边就会消失。所以问题就变成了，我们如何选择放置这k-1个隔板，使得k-1条边消失后，分成的K段内每段的总和最小。我们最小值到最大值之间的总长度是确定的，我们要想让最后留下的最小，当然删去的长度就要最大，我们可以计算出每两个点之间的距离，让一开始计算出的最小值到最大值之间的距离减去前K-1大的线段，留下的值就是最小的钢板总长度。详见下方图示
参考代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=210;
int a[N];
int b[N]; // 存储a[i]-a[i-1]的值，即每两个点之间的长度
int k,n,m; // k为最多可用的钢板数量，n为总厂房数，m为有物品的厂房数
int ans=0;
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
scanf("%d%d%d",&k,&n,&m);
for(int i=1;i<=m;i++) scanf("%d",&a[i]);
sort(a+1,a+1+m);
ans=a[m]-a[1]+1;
for(int i=2;i<=m;i++) b[i-1]=a[i]-a[i-1]; // 记录每个线段的长度
sort(b+1,b+m,cmp);
// 总长度减去前k-1大的线段的长度之后，还需要加1，因为多减了一个端点的值
for(int i=1;i<k;i++) ans=ans-(b[i]-1);
printf("%d",ans);
return 0;
}
D题
题目描述
思路
模拟
进行两次循环，第一次变量从1开始，每次+a,判断该位置是否已经被挖过洞，如果没有被挖过则计数+1
第二次循环，变量从最右侧的n开始，每次-b，重复第一次循环的操作计数
注意
一定要判断当前的位置是否已经被挖过洞，不然会重复计算
参考代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e4+10;
bool visit[N]; // 记录当前位置是否已经被挖过洞
int n,a,b;
int ans; // 总共挖的洞的个数
int main()
{
scanf("%d%d%d",&n,&a,&b);
// 题目中的长度为n表示之间的距离为n，实际的左右端点为1和n+1
for(int i=1;i<=n+1;i+=a)
{
if(!visit[i])
{
ans++;
visit[i]=true;
}
}
for(int i=n+1;i>=1;i-=b)
{
if(!visit[i])
{
ans++;
visit[i]=true;
}
}
printf("%d",ans);
return 0;
}
E题
题目描述
思路
线性DP
对于长度为2行1列的木槽，一共有5中情况，如下图
对于长度为2行2列的木槽，一共有8中情况，如下图
Dp分析如下
参考代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N];
int f[N];
int T;
int main()
{
scanf("%d",&T);
int maxx=0;
for(int i=1;i<=T;i++)
{
scanf("%d",&a[i]);
maxx=max(maxx,a[i]);
}
f[1]=5;
f[2]=33; //5*f[1]+8
for(int i=3;i<=maxx;i++) f[i]=5*f[i-1]+8*f[i-2];
for(int i=1;i<=T;i++) printf("%d\n",f[a[i]]);
return 0;
}
总结
总体来说这次的挑战赛难度中等，有难题也有简单题，有些比的时候没想出了，结束之后突然就想明白了。第一次写题解，不喜勿喷。希望此次的题解能帮助到需要的人。
版权声明：本文为博主作者：沃特艾文儿菲特原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/qq_68734252/article/details/128680868
