AtCoder Beginner Contest 112题解

AtCoder Beginner Contest 112

比赛链接

前言

这场ABC我用了一个小时AK （虽然我晚到了5分钟）（虽然这是我第一次AK）。

所以我写下这篇博客作为纪念。

A.Programming Education

题外话

这个名字起得真好：编程教育。但其实是道水题。。。

题目大意

给定一个数$N$，若$N=1$则输出Hello World；若$N=2$则继续读入两个数$A,B$，并输出$A+B$的结果。

正解代码

不用说了，水题，直接粘代码。

#include<cstdio> #include<algorithm> using namespace std;int main() {
     #ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifint N;scanf("%d",&N);if(N==1) {
     puts("Hello World");} else {
     int a,b;scanf("%d %d",&a,&b);printf("%d\n",a+b);}return 0; } 

B.Time Limit Exceeded

题目大意

给定$T$和$N$组有序点对$(c_i,t_i)$，要求找到一个点对，使得它的$t<=T$且$c$尽可能的小。

思路

emmm…没什么可讲的，按照题目意思暴力模拟就行了。。。

正解代码

#include<cstdio> #include<algorithm> using namespace std;int main() {
     #ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifint N,T;int ans=1e9;scanf("%d %d",&N,&T);for(int i=1;i<=N;i++) {
     int cos,t;scanf("%d %d",&cos,&t);if(t<=T)ans=min(ans,cos);}if(ans==1e9)puts("TLE");else printf("%d\n",ans);return 0; } 

C - Pyramid

题目大意

有一座金字塔，其中心为$(C_x,C_y)$，高度为$H$，它周围的点$(x,y)$的高度为$\max (0,H?|C_x?x|?|C_y?y|)$。现给定$N$个平面上的点$(x_i,y_i)$及它们的高度$h_i$，求这个金字塔的$H$。

思路

由于题目给定$0\le C_x,C_y,x_i,y_i\le 100$，所以直接暴力枚举$(C_x,C_y)$，并与给定信息比对一下即可。

正解代码

#include<cstdio> #include<algorithm> using namespace std;typedef long long ll; const int Maxn=100;int N; int cx,cy; ll h; struct Node {
     int X,Y;ll H;bool operator < (const Node &rhs) const {
     return H>rhs.H;} }A[Maxn+5];inline ll abs(ll a) {
     if(a<0)return -a;return a; }int main() {
     #ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d",&N);for(int i=1;i<=N;i++)scanf("%d %d %lld",&A[i].X,&A[i].Y,&A[i].H);sort(A+1,A+N+1);for(cx=0;cx<=100;cx++) {
     bool flag=false;for(cy=0;cy<=100;cy++) {
     ll th=max(0LL,abs(A[1].X-cx)+abs(A[1].Y-cy)+A[1].H);if(th<1)break;for(int i=2;i<=N;i++)if(max(0LL,th-abs(A[i].X-cx)-abs(A[i].Y-cy))!=A[i].H) {
     th=-1;break;}if(th!=-1) {
     h=th;flag=true;break;}}if(flag)break;}printf("%d %d %lld",cx,cy,h);return 0; } 

D - Partition

题目大意

将$M$拆成$N$个数，求这$N$个数的最大公因数最大的方案。

思路

我们设$M$拆分后的$N$个数中最大公约数为$k$，第$i$个数除以$k$的商为$k_i$，则不难得出以下关系式：$$M=k{k}_1+k{k}_2+?+k{k}_N$$

整理一下：$$M=k\times \sum _{i=1}^N{k}_i$$

则不难看出$k$是$M$的因数。

所以我们只需枚举$M$的因数，再判断一下$M$除以该因数再除以$N$的结果是否大于0即可（因为不能够有0出现）。

正解代码

#include<cstdio> #include<cmath> #include<algorithm> using namespace std;int N,M;int main() {
     #ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d %d",&N,&M);if(N==1) {
     printf("%d\n",M);return 0;}int ans=1;for(int i=2;i*i<=M;i++)if(M%i==0) {
     int tmp=M/i;if(tmp/N>0)ans=max(ans,i);if(i/N>0)ans=max(ans,tmp);}printf("%d\n",ans);return 0; }