新生赛(1)题解
A
简单的语法题,可以用循环写,当然也可以手写三次输出,下面是循环的写法
#include<stdio.h>
int main()
{
for(int i=0;i<3;i++)
printf("Welcome to ACM / ICPC!\n");
return 0;
}
B
依然是一道语法题,主要考察循环与二维数组知识的部分,将矩阵输入到二维数组中再利用数组自带的查找功能就行啦
#include<stdio.h>
int main()
{
int n,m,a[10][10];
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",a[i]+j);
int x,y;
scanf("%d%d",&x,&y);
printf("%d",a[x-1][y-1]);
return 0;
}
C
因为题目中5,2,0三个数不需要按照顺序也不需要连续出现,所以给出的数组中5,2,0三个数中出现次数最少的那个数一定可以找到另外两个数匹配,因此这个最少的次数就是答案
#include<stdio.h>
int main()
{
int n;
scanf("%d",&n);
int cnt5=0,cnt2=0,cnt0=0;
for(int i=0;i<n;i++)
{
int a;
scanf("%d",&a);
if(a==5) cnt5++;
if(a==2) cnt2++;
if(a==0) cnt0++;
}
int t=cnt5;
if(t>cnt2) t=cnt2;
if(t>cnt0) t=cnt0;
printf("%d",t);
return 0;
}
D
本题用到了双指针的思想,将两个数组扫描一遍,扫描的方式为:比较一下两个数组当前指针位置的数的大小,将较小的那个数放入答案数组c中,并将其对应指针后移一位,直到其中一个数组的指针指向其末尾了,结束扫描的过程。
这时由于另一个数组的指针可能还没有指向末尾(没有扫描到末尾的一部分数),所以要再把另一个数组后面的数也放进答案数组中。
#include<stdio.h>
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int a[1010],b[1010];
for(int i=0;i<n;i++) scanf("%d",a+i);
for(int i=0;i<m;i++) scanf("%d",b+i);
int c[2010],i=0,j=0,k=0;
while(i<n && j<m) //扫描两个数组
{
if(a[i]>b[j])
c[k++]=b[j++];
else
c[k++]=a[i++];
}
while(i<n) c[k++]=a[i++]; //将剩下没有被扫描到的数放进答案数组中
while(j<m) c[k++]=b[j++];
for(int i=0;i<k;i++)
printf("%d ",c[i]);
return 0;
}
E
这是一道思维题。
首先小姐姐走到小名那里最短的方案是min=|a|+|b|,n的值如果小于min肯定是不行的,n等于min肯定是可以的。
那n大于min的情况呢,哪些符合哪些不符合呢?
小姐姐只要在走最短路线的过程中,走到一个点再回来,步数就能+2。因此当n减min为偶数时,小姐姐总可以走出步数为n的方案。
那n-min为奇数呢?显然是不行的,因为不管怎么绕路,在横坐标或者纵坐标上总要走回头路,因此绕完以后只会多出偶数步。这种情况下就说明小姐姐在骗你啦
#include<stdio.h>
#include<math.h>
int main()
{
int a,b,n;
scanf("%d%d%d",&a,&b,&n);
int min=abs(a)+abs(b);
if(n<min || (n-min)%2)
printf("NO");
else printf("YES");
return 0;
}
F
这道题也是一道思维题,我们可以首先将n堆糖果的每一堆加到不能再加为止(再加一次就超过k个了),如果某堆糖果本身就大于k那当然就是加0次。完成这些操作后我们还可以最后再加一次,加完后uu就失去魔法,没办法继续增加了,最后算一下总共的糖果数就可以了。
还有一种需要特殊处理的情况:如果h也就是每次加的糖果数为0的话,那再怎么加,糖果也还是原来的数量,所以答案就是把所有糖果数加起来就行。
#include<stdio.h>
typedef long long LL;
int main()
{
int n,k,h;
scanf("%d%d%d",&n,&k,&h);
LL res;
for(int i=0;i<n;i++)
{
int a;
scanf("%d",&a);
if(a>=k || h==0) res+=a;
else res+=k-(k-a)%h; //k-(k-a)%h就是最多能加到的数量
}
res+=h;
printf("%lld",res);
return 0;
}
G
这道题有个比较坑的地方,就是需要对输入的字符串先处理一下,因为题目当中说,输入的字符串可能有前导零,也就是说也可能没有前导零,所以要加个循环判断一下,字符串中冒号前的表示小时,冒号后的是分钟。(真的很坑这里)
处理完之后,下面提供两个方法去写:
第一个方法是暴力去搜,将所给的时间点分别往前搜和往后搜,确保把每个可能的时刻都搜到,直到搜到回文时刻后停止,输出这个回文时刻就行啦。
放上代码
#include<stdio.h>
int main()
{
char t[7];
scanf("%s",t);
int hour=0,min=0,i=0;
while(t[i]!=':') //这里用两个循环分别找到输入时刻的时和分
{
hour*=10;
hour+=t[i]-'0';
i++;
}
i++;
while(t[i])
{
min*=10;
min+=t[i]-'0';
i++;
}
int m=min,h=hour; //暴力向前、向后搜每一个时刻(注意不要直接用min和hour++或--,会丢失原有数据)
while(1)
{
m--;
if(m==-1) m=59,h--;
if(h==-1) h=23;
if(m/10+m%10*10==h)
{
printf("%d:%d\n",h,m);
break;
}
}
m=min,h=hour;
while(1)
{
m++;
if(m==60) m=0,h++;
if(h==24) h=0;
if(m/10+m%10*10==h)
{
printf("%d:%d",h,m);
break;
}
}
return 0;
}
下面是第二个方法
由于回文的时刻很少,所以这道题可以直接打表,把所有回文的时刻列出来,然后判断一下输入的时刻在哪两个回文时刻之间就行。判断的时候可以把小时换成分钟,方便比较大小。
#include<stdio.h>
int main()
{
char hwtime[17][7]={"0:0","1:10","2:20","3:30","4:40","5:50", //把每一个回文时刻存一下
"10:1","11:11","12:21","13:31","14:41","15:51",
"20:2","21:12","22:22","23:32","0:0"};
int hw[17]={0,70,140,210,280,350,601,671,741,
811,881,951,1202,1272,1342,1412,1440};
char t[7];
scanf("%s",t);
int hour=0,min=0,i=0; //处理字符串
while(t[i]!=':')
{
hour*=10;
hour+=t[i]-'0';
i++;
}
i++;
while(t[i])
{
min*=10;
min+=t[i]-'0';
i++;
}
int time=hour*60+min;
if(time==0) //输入的时刻为0:0时,特判一下(可以思考一下为什么)
{
printf("%s\n%s",hwtime[15],hwtime[1]);
return 0;
}
for(int i=1;i<17;i++) //找到输入的时刻在哪两个回文时刻之间
{
if(time==hw[i])
{
printf("%s\n%s",hwtime[i-1],hwtime[i+1]);
break;
}
if(time<hw[i])
{
printf("%s\n%s",hwtime[i-1],hwtime[i]);
break;
}
}
return 0;
}
H
这道题主要考察了递推的思想
令填充前i个方块的情况数量为a(i),那么很显然,想填充前i个方块,可以在填充好前i-1个方块后,再放一个1 * 1的,或者是在填充好前i-2个方块后,再放一个2 * 1的。所有我们很容易能够得到,a(i)=a(i-1)+a(i-2)。
是不是有点像斐波那契数列了,没错,这就是斐波那契数列!
然后代码实现一下就行了,状态可以用数组存也可以直接递推,这里写用数组存的方法,大家可以想想不用数组存该怎么写
还有一点很重要的就是,因为n最大可以到80,众所周知,斐波那契数列到后面会很大,超过int范围,所以一定要开long long去存
#include<stdio.h>
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
long long a[80];
a[0]=a[1]=1;
for(int i=2;i<=n;i++)
a[i]=a[i-1]+a[i-2];
printf("%lld\n",a[n]);
}
return 0;
}
I
依然是一道思维题,我们会发现这道题的本质,就是在从l到r当中的数里面,找一个%n后能得到的最大的数。
显然,这个数最大是n-1,那什么时候能取到这种最大的情况呢?我们会发现,当整个区间的长度大于等于n时,区间一定跨越了某个k * n(k为任意整数),区间中一定有一个数a,a%n的值为n-1,所以当出现这种情况时,答案为n-1。
还有一种情况,就是当 l%n > r%n 时,也能取到n-1的情况。因为r一定不会在l的前面,但是取余后又有 l%n > r%n ,说明l到r的区间一定跨越了某个k * n(k为任意整数),因此区间中一定存在某个数a,a%n的值为n-1。
那剩下的情况,就是 l%n <= r%n 且区间长度小于n的情况,那么整个区间一定包含于某个k * n到(k+1) * n(k为任意整数)之间,因此最多只能取到r%n了。
#include<stdio.h>
int main()
{
int n,l,r;
scanf("%d%d%d",&n,&l,&r);
if(r-l+1>=n || l%n > r%n)
printf("%d",n-1);
else
printf("%d",r%n);
return 0;
}