ACM2023第一次考核题解

ACM2023第一次考核题解

题目难度及知识点

题目序号	难度	题目编号	题目名称	考察知识点	出题人
1	容易	J	我爱季学姐	简单输入输出
2	容易	I	自动大写	简单字符串
3	容易	D	小齐算数O。O	简单输入输出
4	一般	F	唐学姐爱黄金	思维
5	一般	G	祖传的挑战	打印沙漏
6	一般	B	X进制星球	进制转换
7	一般	C	欢欢的特别素数	质数筛
8	困难	A	knight的自制谱	差分
9	困难	H	GCD	GCD
10	困难	E	我要子矩阵！	前缀和

A knight的自制谱

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int pu[N];
int d[N];
int dis[N];
int scores[3]={100,90,80};//记录分数
int cnt[N];
void solve()
{int n,m;long long ans=0;cin >> n >> m;for(int i=0;i<n;i++){cin >> pu[i];//记录每个note到达的时间cnt[pu[i]]++;//将每个时间到达的note计算 方便后续计算奖励分}d[0]=pu[0];for(int i=0;i<m;i++){int l,r,t;cin>>l>>r>>t;l--,r--;dis[l]+=t;dis[r+1]-=t;//构造差分数组}for(int i=1;i<n;i++){dis[i]=dis[i]+dis[i-1];//通过差分计算每个note的得分}for(int i=0;i<n;i++){if(cnt[pu[i]]>1)//有奖励分数的ans+=scores[dis[i]]*(1+(cnt[pu[i]]-1)*0.05);else//没有奖励分数的ans+=scores[dis[i]];}cout<<ans<<endl;
}
int main()
{solve();return 0;
}

B X进制星球

//整体思路：将二进制转换为十进制，再将十进制转换为X进制
#include<stdio.h>
const int N=100;
int main()
{long long n; scanf("%lld",&n);//15位数，若采用整型数据读入需使用long long防止爆范围int res=0,p=1;//res表示十进制结果，p表示二进制指数权重。while(n){int r=n%10;//对10取余取得最后一位n/=10;//丢去最后一位r*=p;//每一位对应的数乘以相应位数权重p*=2;//每次循环权重都要对应更改res+=r;//求结果}int x;scanf("%d",&x);//x表示进制数int num[N];int cnt=0;while(res)//除x取余的方法{int t;t=res%x;//取得余数res/=x;num[++cnt]=t;//余数存入数组}for(int i=cnt;i>=1;i--)//倒序输出答案{switch (num[i]) {//十进制以上数对应的字母转换case 10:printf("A");break;case 11:printf("B");break;case 12:printf("C");break;case 13:printf("D");break;case 14:printf("E");break;case 15:printf("F");break;default:printf("%d",num[i]);break;}}
}

C 欢欢的特别素数

在判断素数的基础上加一个判断，判断尾数是否为1就可以了

#include<stdio.h>int su(int n){if (n<11 || n%10 != 1) return 0;for (int i=2;i*i<=n;i++)if (n%i==0) return 0;return 1;
}int main(){int l,r,flag=1;scanf("%d %d",&l,&r);for (int i=l;i<=r;i++){if (su(i)){printf("%d ",i);flag=0;}}if (flag) printf("-1");return 0;
}

D 小齐算数O。O

#include<stdio.h>int main()
{double c,d;scanf("%lf%lf",&c,&d);printf("%.2f",((c-d)*9)/5+32);return 0;
}

E 我要子矩阵！

两种做法 可以用一维前缀或者二维前缀和

#include <stdio.h>
#define ll long long
ll sum[3005][3005];//前缀和数组sum[i][j]表示矩阵第i行1到j的前缀和 
ll n,m;
ll ans;
int main()
{scanf("%d%d",&n,&m);//输入矩阵的行列数 for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){ll x;scanf("%lld",&x);//输入矩阵的第i行第j列的元素 sum[i][j]=sum[i][j-1]+x;//计算第i行的前缀和 }}int t;scanf("%d",&t);//输入询问次数 int x1,x2,y1,y2;while(t--){scanf("%d%d%d%d",&x1,&y1,&x2,&y2);//输入左上角和右下角的坐标 ans=0;//ans记录答案，每一次要归零 for(int i=x1;i<=x2;i++){//遍历x1到x2行，ans+=(sum[i][y2]-sum[i][y1-1]);//并根据前缀和求出每一行y1到y2的和，进行累加 }printf("%lld\n",ans);//输出答案，记得换行 }return 0;}

//二维前缀和做法看不懂的可以问出题人或者学长或者参考门槛题B3的提示里的链接 
#include <stdio.h>
#define ll long long
ll sum[2005][2005];
int n,m,t;
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){ll x;scanf("%lld",&x);sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x;}}scanf("%d",&t);int x1,x2,y1,y2;while(t--){scanf("%d%d%d%d",&x1,&y1,&x2,&y2);printf("%lld\n",sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]);}return 0;
}

F 唐学姐爱黄金

利用贪心的思想，遍历每一天的价格，将当前黄金的最小价格记录出来，然后将ans赋值为当前最大的利益。

#include<stdio.h>
int a[1000010];
int max(int a,int b)
{if(a >= b) return a;else return b;
}
int min(int a,int b)
{if(a <= b) return a;else return b;
}
int main()
{int n;scanf("%d",&n);int t = 1e9, ans = 0;for(int i = 1 ; i <= n ; i ++){scanf("%d",&a[i]);if(i > 1 ) ans = max(ans,a[i] - t);t = min(t,a[i]);}printf("%d",ans);return 0;
} 

G 祖传的挑战

和学姐PPT里的问题升级了一下，计算一下层数问题就一样啦。

#include<stdio.h>
int main()
{int i,j=1,x=0,y=0,rest,N;char C;scanf("%d %c",&N,&C);while(2*j*j-1<=N)//计算层数{j++;}j--;y=2*j-1;	rest=N-2*j*j+1;//剩下字符的数量while(y>0)//输出沙漏上半部分{for(i=0;i<x;i++)printf(" ");for(i=0;i<y;i++)printf("%c",C);printf("\n");x++;y-=2;}x--;y+=2;while(x>0)//输出沙漏下半部分{x--;y+=2;for(i=0;i<x;i++)printf(" ");for(i=0;i<y;i++)printf("%c",C);printf("\n");	}printf("%d",rest);return 0;
}

H GCD

题意：初始时集合$S$内有两个数$x，y，$一次操作中可以选取两个数$a，b$将$a—b$或$gcd（|a|，|b|）$插入集合。问最后能否使得元素$z$在集合中。$0\le x，y，z\le 10^9$

解法：不难注意到这个操作就是辗转相减，因而可以得到$gcd（a，b）$。这时所有$gcd（a，b）$的倍数（因为可以产生负数）就都可以得到了。注意特判$z＝0$的情况。

#include <bits/stdc++.h>
using namespace std;
int gcd(int x, int y)
{	if (y)			return gcd(y, x%y);		else			return x;
}int main() {int t = 1;scanf("%d", &t);while (t--){int a, b, c;scanf("%d%d%d", &a, &b, &c);if((c == 0 && (a == 0 || b == 0 )) || (c != 0 && c%__gcd(a,b) == 0) ) printf("YES\n");else printf("NO\n");}return 0;
}

I 自动大写

读入字符串后，检查每个字符，将大写转换成小写字母之后输出

#include<stdio.h>int main()
{char str[110];scanf("%s",str);for(int i = 0 ; i < strlen(str) ; i ++)if(str[i] >= 'A' && str[i] <= 'Z') printf("%c",'a' + str[i]-'A');else  printf("%c",str[i]);return ;
}

J 我爱季学姐

#include <stdio.h>
int main()
{printf("printf(\"我爱季'学姐'\\n\");");return 0;
}