2022年第四届全国高校计算机能力挑战赛c++组决赛
小丽好朋友的生日快到了，她打算做一些折纸放在幸运罐中作为生日礼物。小丽计划总共 需要a颗星星以及b只纸鹤。现在市场上卖的到的星星纸(折小星星的专用纸)一张可以折c颗小星星，一张纸鹤纸(折纸鹤的专用纸)可以折d只小纸鹤。她准备一共买k张折纸，要优先满足星星纸的需求，剩余的再去买纸鹤纸，请你帮忙计算一下，买来的k张折纸能否满足小丽的折纸需求，能满足的话分别给出需要购买的星星纸和纸鹤纸的数量，不能的话则输出-1。若有满足条件的折纸方案，星星优先折叠，剩下的折纸都属于纸鹤。
输入格式第一行输入一个整数T，表示共有T组情况需要判断。 接下来T行,每行包含5个整数a,b,c,d,k。 其中1<=T,a,b,c,d,k<=100
输出格式输出T行，如果可以满足要求，输出两个整数x，y以空格分隔，分别表示需要采购的星星纸数量和纸鹤纸数量。 如果不存在合理方案，输出-1。
输入输出样列输入样例1： 1 10 6 3 4 6 输出样例1： 4 2 输入样例2： 3 7 5 4 5 8 7 5 4 5 2 20 53 45 26 4 输出样例2： 2 6 -1 1 3
思路签到成功！
AC代码 #include<iostream> using namespace std; int main() { //freopen("D:\\test.txt","r",stdin); int T; int a,b,c,d,k; int ans1=0,ans2=0; cin>>T; while(T--) { ans1=0; ans2=0; cin>>a>>b>>c>>d>>k; ans1+=a/c; if(a%c!=0) ans1++; ans2+=b/d; if(b%d!=0) ans2++; if(ans1+ans2>k) cout<<"-1"<<endl; else cout<<ans1<<" "<<k-ans1<<endl; } return 0; } B 题目描述小李计划编写一个关于幂运数的自动答题机器人程序。机器人运行的规则是这样的：每当用户输入一个数 A_i时，机器人就会自动回答下面2个问题： 1)用户所输入的前i-1个数中有多少个数是A_i的幂运数； 2)这些幂运数的累加和是多少。 你能帮助小李完成这个自动答题机器人程序吗? 说明： 如果一个整数x可以表示成另一个整数y的多次幂，即： x=y∗y∗y⋯∗y(y的个数至少为2)，那么我们就说x是y的幂运数。
输入格式第1行：一个整数N，表示用户会进行N次数据输入。 1<=N<=10∧6. 第2到N+1行：每行一个正整数，其中第i+1行的正整数是用户第i次输入的数A 。 A−i,2<=A−i<=10∧6。
输出格式N行：每行两个空格分隔的整数，其中第i行表示机器人对用户第i次输入数据的回答(A_i的幂运数个数，以及它们的累加和除以99999的余数).
输入输出样列输入样例1： 3 81 9 3 输出样例1： 0 0 1 81 2 90
思路每次读入一个数时，计算他是哪些数的多次幂，给这些数做标记。查询时 输出这个数的被标记次数以及每次标记的数的和。 这个题曾经也想暴力来着，但看数据范围并不是很小，所以这样稍微复杂化了一下（好像也不太快）
AC代码 #include<iostream> #include<vector> #include<cmath> using namespace std; typedef long long ll; const int MAXN = 1000005; const int MOD = 99999; vector<int>v[MAXN]; ll n; ll a[MAXN]; ll num,temp; ll sum=0,cnt=0; int main() { //freopen("D:\\test.txt","r",stdin); cin>>n; for(int i=1;i<=n;++i) { cin>>num; temp=num; sum=0,cnt=0; for(vector<int>::iterator it=v[num].begin();it!=v[num].end();it++) { sum=(sum+(*it))%MOD; } for(int i=2;i<=sqrt(temp);i++) { ll t_n=i; bool yn=false; while(true) { if(t_n==num) { yn=true; break; } else if(t_n>num) break; t_n*=i; } if(yn) { v[i].push_back(num); } } cout<<v[temp].size()<<" "<<sum<<endl; } return 0; } C 题目描述小张的工厂里的厂房受到台风的袭击，导致部分厂房的顶棚遭到了破坏，急需修理。厂房是由一间间的相同宽度的隔间组成，这些隔间都是连在一起的，连成了一条直线，隔间采用塑钢板作为顶棚，多个隔间可以共用一块长的塑钢板。这些隔间里有的有货物，有的没有货物，因为考虑到最近可能还会有台风，所以必须把有货物的隔间的顶棚修理好。 目前塑钢板的供应商能提供的板材的数量有限制，但长度没有限制，所以小张只能尽量的减少板材的数量。请你帮助小张计算需要采购塑钢板的最小长度。
输入格式第1行：M，S和C(用空格分开)。M为能买到的板材的最大数目(1<=M<=50)，S为厂房总的隔间的数量,1<=S<=200,C为有货物的隔间的数量。 第2到C+1行：每行包含一个整数，表示有货物的隔间的编号。编号从1开始，1<=C<=S
输出格式输出一行，采购的塑钢板的总长度。
输入输出样列输入样例1： 1 10 4 2 5 7 8 输出样例1： 7
思路这标准的最小生成树啊，M是连通分量数，C是结点数，唯一注意就是注意结点编号。 基本同这篇文章：洛谷P1991 无线通讯网（最小生成树）
AC代码 #include<iostream> #include<algorithm> using namespace std; const int MAXN=205; const int MAXM=40010; int M,S,C; int cnt=0; int num=0; int ans=0; int f[MAXN]; int a[MAXN]; struct Edge { int u,v,w; bool operator<(const Edge a)const{ return w<a.w; } }e[MAXM]; int Find(int x) { if(x==f[x]) return x; return f[x]=Find(f[x]); } void Merge(int x,int y) { f[Find(x)]=Find(y); } int main() { //freopen("D:\\test.txt","r",stdin); cin>>M>>S>>C; for(int i=0;i<=S;++i) { f[i]=i; } for(int i=1;i<=C;++i) { cin>>a[i]; for(int j=1;j<i;++j) { e[++cnt].u=a[i]; e[cnt].v=a[j]; e[cnt].w=max(a[i]-a[j],a[j]-a[i]); } } sort(e+1,e+cnt+1); for(int i=1;i<=cnt;++i) { if(Find(e[i].u)!=Find(e[i].v)) { num++; Merge(e[i].u,e[i].v); ans+=e[i].w; if(num==C-M) { break; } } } cout<<ans+M<<endl; return 0; } D 题目描述小花和小草正在沙滩上玩挖沙洞的游戏。他们划了一条长度为n米的线作为挖沙洞的参考线路，小花和小草分别从两头开始沿着划好的线开始挖洞，小花每隔a米挖一个洞，小草每隔b米挖一个洞，碰到已经挖过洞的就不需要再挖了。那么，你能帮小花和小草算算，他们全部挖到头之后，一共挖了多少个洞吗?(两头端点位置都要挖洞)
输入格式第1行:一个正整数n,代表线路的长度。(3<=n<=10000) 第2行:用空格分隔的两个正整数,代表a和b的值。(1<=a,b<=50)
输出格式输出1行：1个整数，表示最终挖出来的沙洞的个数。
输入输出样列输入样例1： 6 23 输出样例1： 5 输入样例2： 100 5 10 输出样例2： 21
思路数据不大，直接暴力。如果ka=n-qb（0<=k,q），那么这个洞就重复了。计算两个人在路上应该挖的洞减去重复挖的洞。
AC代码 #include<iostream> using namespace std; typedef long long ll; int main() { ll n,a,b; int cnt_a=0; int cnt_b=0; ll ans=0; cin>>n>>a>>b; cnt_a=n/a; cnt_b=n/b; ans+=cnt_a+cnt_b+2; if(a==1||b==1) cout<<n+1<<endl; else for(int i=0;i<=cnt_a;i++) { for(int j=0;j<=cnt_b;j++) { if(i*a+j*b==n) { ans--; } else if(i*a+j*b>n) { //怕超时，剪枝 break; } } } cout<<ans<<endl; return 0; } E 题目描述现在有3种积木：黄色和红色的积木，大小均为1*1，还有一种大小为1∗2的蓝色积木，小明打算使用这3种积木把一个宽为2长度为L的木槽铺满，你能算出小明最多能摆出多少种花样吗?
注意： 1、摆放过程中积木不能重叠 2、摆放时以颜色为区分，颜色相同情况算作一种，比如2块蓝色的竖摆和横摆整体的颜色都是蓝色，只能算一种摆法。 3、摆放时不考虑两块蓝色积木错开的情况，即2块蓝色积木横向摆放时不能上下错开1格进行摆放。 注：错开，比如第一块蓝色积木放在 1∗1,1∗2(行号列号)的方框内，第二块蓝色积木放在2∗2,2∗3(行号列号)的方框内
输入格式：第1行一个整数T,表示测试数据组数(1<=T<=100000) 接下来T行,每行一个整数L表示木槽长度(1<=L<=100000)
输出格式：.输出T行，输出每组数据L对应的摆放方案数，由于答案可能很大，输出答案模99999的结果
输入输出样例输入样例1： 1 1 输出样例1： 5 输入样例2： 2 2 4 输出样例2： 33 1289
思路简单dp 长度为L的方框的方法，可以看成先放好长度为L-1的方框，再铺一条，这一条有5种方法；但显然，这种放法不可以将蓝色积木竖着摆，所以要想将蓝色积木竖着摆，应先放满L-2的方框，然后再摆2*2的方框，这个小方框必须有蓝色积木竖着摆，且不能都摆蓝色积木，会跟上面那种方法有重复。因此共有（5-1）+（5-1）=8种情况。 得到转移方程： dp[x]=dp[x-1]*5+dp[x-2]*8;
AC代码 #include<iostream> using namespace std; const int MAXN= 100005; const int MOD = 99999; typedef long long ll; ll dp[MAXN]={0,5,33}; ll a[MAXN]; ll max_num=0; int main() { int n; cin>>n; for(int i=1;i<=n;++i) { cin>>a[i]; max_num=max(max_num,a[i]); } for(int i=3;i<=max_num;i++) { dp[i]=(dp[i-1]*5+dp[i-2]*8)%MOD; } for(int i=1;i<=n;++i) { cout<<dp[a[i]]<<endl; } return 0; } 开奖所以上述答案应该差不多正确，如有问题，欢迎斧正。