2019zzulioj新生赛_zzulioj正方形

A建国与回文串

思路

符合要求的字符串一i是偶数。

将字符串分为两部分，先判断第一部分是否是完美回文串，在判断第二部分。

i从中间向前遍历，i的下标表示的是完美回文串的右边部分的第一个字符下标。例如abcddcba。i就是4.

 

#include<stdio.h>
#include<string.h>
int main()
{
	int T,t=1;
	scanf("%d",&T);
	while(T--)
	{
		char a[1005];
		scanf("%s",a);
		int i,len=strlen(a);
		if(len%2!=0)
		  printf("Case# %d: No\n",t++);
		else
		{
			int flag=0;
			for(i=len/2-1;i>=0;i--)
			{//判断第一部分是否是完美回文串 
				if(a[i]==a[i-1])//向两边遍历，看是否完全相等 
				{
					int j1=i-1,j2=i;
					while(j1!=0)
					{
						if(a[j1]!=a[j2])
							break;
						j1--;
						j2++;		
					}
					if(j1==0)//如果遍历到了边界，说明是完美回文串 
					{
						if(a[j1]==a[j2])
						{						
							int j1=2*i,j2=len-1;
							while(j1<j2)//判断第二部分是否是完美回文串 
							{
								if(a[j1]!=a[j2])
									break;	
								j1++;
								j2--;
							}
							if(j1>j2)
							{
								flag=1;
								printf("Case# %d: Yes\n",t++);
								break;
							}
						}						
					}			
				}				
			}
			if(flag==0)
				printf("Case# %d: No\n",t++);	
		}
	}
	return 0;	
} 

B建国的数学难题

#include<stdio.h>
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n,k;
		scanf("%d%d",&n,&k);
		long long i,a[1005],f[1005];
		a[1]=1;
		for(i=2;i<n;i++)
			a[i]=a[i-1]+i;
		f[1]=k;
		for(i=2;i<=n;i++)
			f[i]=f[i-1]+a[i-1];
		printf("%lld\n",f[n]);
	}
	return 0;
}

C建国与两个数组

思路

判断k的倍数-i（i<=n）是否小于等于m。

#include<stdio.h>
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n,m,k;
		scanf("%d%d%d",&n,&m,&k);
		int i,j;
		int ans=0;
		for(i=1;i<=n;i++)
		{
			int kk=k;
			for(j=0;j<=(n+m)/k+1;j++)
			{
				if(kk-i>0&&kk-i<=m)
					ans++;
				kk+=k;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
} 

D建国的签到活动一

思路

记录从0开始，中间都是1，从0结束的下标。

#include<stdio.h>
int main()
{
	int n;
	scanf("%d",&n);
	int a[205][205];
	int i,j;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			scanf("%d",&a[i][j]);
	int s[205]={0};//初始化为0，防止最终遍历t2的时候超限。
	for(i=0;i<n;i++)
		scanf("%d",&s[i]);
	int t1,t2,ans=0;//用t1，t2记录从0开始和从0结束的下标		
	for(i=0;i<n;i++)
	{
		while(s[i]!=1&&i<n)
			i++;
		t1=i;
		while(s[i]!=0&&i<n)
			i++;
		i--;//因为循环自带有一个i++，所以要i--
		t2=i;
		if(t1<=t2)
			ans+=a[t1][t2];			
	}
	printf("%d\n",ans);
	return 0;
}

E建国的签到活动二

思路

暴力找出所有情况，找最大值，和最大值的个数。

可以找出规律：如果你选了（0，0），那么你能得到的奖励只能在（2，。。。。）找，比如你又选了（2，4），那么你能得到的奖励只能在（6，.。。。。）找，以此类推，用递归（深度搜索）的方法找到所有的可能性。

ps：这道题对于没接触过算法的acer来说我觉得有很大的难度。

#include<stdio.h>
int a[205][205],n;
int ans[10000]={0};
int t=0;
void dfs(int sum,int x,int y)
{			
	sum+=a[x][y];
	if(y==n-1||y==n-2)
		ans[t++]=sum;	
	for(int j=y+2;j<n;j++)
	{				
		if(y+2<=j&&y+2<n)
			dfs(sum,y+2,j);
		if(y+3<=j&&y+3<n)
			dfs(sum,y+3,j);
	}				
}
int main()
{
	scanf("%d",&n);
	int i,j;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			scanf("%d",&a[i][j]);
	for(i=0;i<2&&i<n;i++)//如果n>2，那么最大值一定是第一天签到或第二天签到且第一天不签到这两种情况
		for(j=i;j<n;j++)
			dfs(0,i,j);
	int max=0,temp=0;
	for(i=0;i<t;i++)
		if(max<ans[i])
			max=ans[i];
	for(i=0;i<t;i++)
		if(max==ans[i])
			temp++;
	printf("%d %d\n",max,temp);
	return 0;
}

F建国的嘱咐

#include<stdio.h>
int main()
{
	printf("The problem of this contest is very easy.I can AK.\n");
	printf("The problem of this contest is very easy.I can AK.\n");
	printf("The problem of this contest is very easy.I can AK.\n");
}

G建勋的魔法学院

思路

两种情况：

1、每个人的b都一样，那么每个人都不走，就是最短的路程。

2、就是排除了1的情况剩下的情况。求出所有a的最小公倍数+b的最大值就是答案。

#include<stdio.h>
int gcd(int a,int b)
{
	if(a%b==0)
		return b;
	return gcd(b,a/b);
}
int main()
{
	int n,i;
	int a[105],b[105];
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	for(i=0;i<n;i++)
		scanf("%d",&b[i]);
	int ans=1,max=0;
	for(i=0;i<n;i++)
	{
		int m;
		if(ans<a[i])
			m=gcd(a[i],ans);
		else
			m=gcd(ans,a[i]);
		ans=ans*a[i]/m;
//		printf("%d %d %d\n",m,ans,max);
		if(max<b[i])
			max=b[i];
	}
	for(i=0;i<n;i++)
		if(max!=b[i])
			break;
	if(i!=n)//第2种情况
		printf("%d\n",max+ans);
	else//第1种情况
		printf("%d\n",max);
	return 0;
}

H建国的寻宝之旅

思路

两个难点，一个是字符变化问题，一个是旋转问题。

一共6个操作，其实算是三个操作，1和6对应，2和5对应，3和4对应。

字符变化问题：对于操作1和6来说，变化4次等于没有变化；对应操作2和5来说，变化两次等于没有变化；对于3和4来说，变化4次等于没有变化。

旋转问题：操作1和操作6是一个效果，操作2和5是一个效果，操作3和4是一个效果。如果假设1代表顺时针旋转90°，那么2就是旋转180°，以此类推。可以直接算出最终要旋转的度数。

#include<stdio.h>
#include<string.h>
#include<math.h>
char a[1005][1005];
char str[1005];
int n;
void change(int s1,int s2,int s3)
{	
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{//对每一个字符都进行三种操作的改变
			int ss1=s1,ss2=s2,ss3=s3;
			while(ss1--)
				if(a[i][j]=='M')
					a[i][j]='3';
				else if(a[i][j]=='W')
					a[i][j]='E';
				else if(a[i][j]=='3')
					a[i][j]='W';
				else if(a[i][j]=='E')
					a[i][j]='M';
				else if(a[i][j]=='|')
					a[i][j]='-';
				else if(a[i][j]=='-')
					a[i][j]='|';
			while(ss2--)
				if(a[i][j]=='M')
					a[i][j]='W';
				else if(a[i][j]=='W')
					a[i][j]='M';
				else if(a[i][j]=='3')
					a[i][j]='E';
				else if(a[i][j]=='E')
					a[i][j]='3';
			while(ss3--)
				if(a[i][j]=='M')
					a[i][j]='E';
				else if(a[i][j]=='W')
					a[i][j]='3';
				else if(a[i][j]=='3')
					a[i][j]='M';
				else if(a[i][j]=='E')
					a[i][j]='W';
				else if(a[i][j]=='|')
					a[i][j]='-';
				else if(a[i][j]=='-')
					a[i][j]='|';
		}						
} 
int main()
{
	int i,j;
	scanf("%d",&n);	
	for(i=0;i<n;i++)
		scanf("%s",a[i]);
	scanf("%s",str);
	int l=strlen(str);
	int s1=0,s2=0,s3=0;//记录操作1，2，3分别需要操作多少次
	for(i=0;i<l;i++)
		if(str[i]=='6'||str[i]=='1')
			s1++;
		else if(str[i]=='5'||str[i]=='2')
			s2++;
		else if(str[i]=='4'||str[i]=='3')
			s3++;
	s1%=4;
	s2%=2;
	s3%=4;
	change(s1,s2,s3);//改变字符数组
	int ans=0;//判断最终的旋转角度
	for(i=0;i<l;i++)
	{
		str[i]-='0';
		if(str[i]==4)
			str[i]=3;
		else if(str[i]==5)
			str[i]=2;
		else if(str[i]==6)
			str[i]=1;
		ans+=str[i];
		ans%=4;
	}
	if(ans==0)//旋转0°
	{
		for(i=0;i<n;i++)
			printf("%s\n",a[i]);
	}
	else if(ans==1)//旋转90°
	{
		for(i=0;i<n;i++)
		{
			for(j=n-1;j>=0;j--)
				printf("%c",a[j][i]);
			printf("\n");
		}
	}
	else if(ans==2)//旋转180°
	{
		for(i=n-1;i>=0;i--)
		{
			for(j=n-1;j>=0;j--)
				printf("%c",a[i][j]);
			printf("\n");
		}
			
	}
	else//旋转270°
	{
		for(i=n-1;i>=0;i--)
		{
			for(j=0;j<n;j++)
				printf("%c",a[j][i]);
			printf("\n");
		}
	}
	return 0;
}

I建国的回家之路

思路

初中物理题。

#include<stdio.h>
int main()
{
	double a,b,c,d;
	while(scanf("%lf%lf%lf%lf",&a,&b,&c,&d)!=EOF)
	{
		double v=(b+c)/d;
		double t=(a+c)/v;
		printf("%.2f %.2f\n",v,t);
	}
	return 0;
}

J建国的穿越

思路

建国能回家的可能有两种，自己和传送门要么都在魔法阵外面，要么都在魔法阵里面，而且是针对每一个魔法阵都要成立。

判断计算结果和r的关系的时候，因为double类型的1严格来说是不等于1的，double类型的1可能等于1.00000000000000000001，所以判断的时候要用减法，避免因为精度问题出错。

#include<stdio.h>
#include<math.h>
struct node{
	int x,y,r;
}a[1005];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n,i;
		int bx,by,ex,ey;
		scanf("%d%d%d%d%d",&n,&bx,&by,&ex,&ey);
		for(i=0;i<n;i++)
			scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].r);
		int flag=0;
		for(i=0;i<n;i++)
		{
			int xx=fabs(bx-a[i].x)*fabs(bx-a[i].x);
			int yy=fabs(by-a[i].y)*fabs(by-a[i].y);
			double dis=sqrt(xx*1.0+yy*1.0);
			if(a[i].r*1.0-dis>0.0000000001)
			{
				int xxx=fabs(ex-a[i].x)*fabs(ex-a[i].x);
				int yyy=fabs(ey-a[i].y)*fabs(ey-a[i].y);
				double R=sqrt(xxx*1.0+yyy*1.0);
				if(a[i].r*1.0-R>0.0000000001)
					flag++;
			}
			else
			{
				int xxx=fabs(ex-a[i].x)*fabs(ex-a[i].x);
				int yyy=fabs(ey-a[i].y)*fabs(ey-a[i].y);
				double R=sqrt(xxx*1.0+yyy*1.0);
				if(R-a[i].r*1.0>0.0000000001)
					flag++;
			}
		} 
		if(flag!=n) printf("No\n");
		else printf("Yes\n");
	}
	return 0;
}