程序设计思维与实践CSP-M4补题

程序设计思维与实践CSP-M4补题

A - TT数鸭子

问题分析

遍历数字，输出不重复的数字的个数。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <set>
using namespace std;
char num[20];
bool flag[15]; 
int n,k;
int main() {
	scanf("%d%d",&n,&k);
	int ans=0;
	for(int i=0;i<n;i++)
	{
		scanf("%s",num);
		//set<char> ss;
		int tmp=0;
		memset(flag,false,sizeof(flag));
		for(int j=0;j<strlen(num);j++)
		{
			if(!flag[num[j]-'0'])
			{
				flag[num[j]-'0']=true;tmp++;
			}
		}
		if(tmp<k)ans++;
	}
	printf("%d
",ans);
	return 0;
}

B - ZJM要抵御宇宙射线

问题分析

对每个点，找它到其他点的最长距离，然后再从所有的最长距离中求取最小值。

#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;
const int size=1005;
double x[size];
double y[size];
double length[size];
int main() {
   int n;
   scanf("%d",&n);
   for(int i=0;i<n;i++)
   	scanf("%lf%lf",&x[i],&y[i]);
   for(int i=0;i<n;i++)
   {
   	length[i]=0;
   	for(int j=0;j<n;j++)
   	{
   		double dx=x[i]-x[j];
   		double dy=y[i]-y[j];
   		double tmp=dx*dx+dy*dy;
   		if(tmp>length[i])
   			length[i]=tmp;
   	}
   }
   int ans=0;
   double ll=length[0];
   for(int i=1;i<n;i++)
   {
   	if(ll>length[i])
   	{
   		ans=i;
   		ll=length[i];
   	}
   	else if(ll==length[i])
   	{
   		if(x[i]<x[ans])
   		{
   			ans=i;
   		}
   		else if(x[i]==x[ans]&&y[i]<y[ans])
   		{
   			ans=i;
   		}	
   	}
   }
   printf("%.2lf %.2lf
",x[ans],y[ans]);
   printf("%.2lf",ll);
   return 0;
}

C - 宇宙狗的危机

问题分析

对数据进行排序，然后若数据中存在某一个数，以它为根节点，它前面区间中的节点为它的左子树，它右面区间中的节点为它的右子树则满足题意，否则不满足。

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
const int size=710;
int n;
int num[size];
bool flag[size][size];
bool R[size][size],L[size][size]; 
int gcd(int a,int b)
{
   return b==0?a:gcd(b,a%b);
} 
bool solve()
{
   for(int l=n;l>=1;l--)
   {
   	for(int r=l;r<=n;r++)
   	{
   		for(int k=l;k<=r;k++)
   		{
   			if(L[k][l]&&R[k][r])
   			{
   				if(flag[l-1][k])
   					R[l-1][r]=true;
   				if(flag[r+1][k])
   					L[r+1][l]=true;
   			}
   		}
   	}
   }
   bool ans=false;
   for(int i=1;i<=n;i++)
   {
   	if(L[i][1]&&R[i][n])
   	{
   		ans=true;
   		break;
   	}
   }
   return ans;
}
int main() {
   int T;
   scanf("%d",&T);
   memset(flag,false,sizeof(flag));
   while(T--)
   {
   	scanf("%d",&n);
   	memset(R,false,sizeof(R));
   	memset(L,false,sizeof(L));
   	for(int i=1;i<=n;i++)
   	{
   		scanf("%d",&num[i]);
   		L[i][i]=R[i][i]=true;		
   	}
   	for(int i=1;i<=n;i++)
   	{
   		for(int j=i;j<=n;j++)
   		{
   			if(gcd(num[i],num[j])>1)
   				flag[i][j]=flag[j][i]=true;
   			else
   				flag[i][j]=flag[j][i]=false;
   		}
   	}
   	bool ans=solve();
   	if(ans)
   		printf("Yes
");
   	else
   		printf("No
");
   }
   return 0;
}