【Week 16】CSP-M4

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(int argc, char** argv) {
	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\n",ans);
	return 0;
}

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 argc, char** argv) {
	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\n",x[ans],y[ans]);
	printf("%.2lf",ll);
	return 0;
}

宇宙狗的危机

题目描述

输入输出描述

样例

思路

因为是一颗二叉搜索树，可以知道，对于根节点而言，其左子树节点必定比它小，而右子树节点必定比它大。

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

接下来就是如何判断某个数为根节点时上述左子树和右子树是否存在：
这里设状态
R[k][r]为以数据中以第k个数为根节点，数据区间k+1~r为右子树是否成立；
L[k][l]为以k为根节点，区间l~k-1为左子树是否成立。(其中r>=k,l<=k)。
对于数据中的每个区间范围l~r（其中l、r表示数据位置），若该区间中存在一个数k，使得L[k][l]与R[k][r]同时成立，则这个区间中可由k为根建立一颗二叉搜索树
这时我们可以扩大区间范围，若l-1与k之间可连接一条边即最大公约数大于1，则R[l-1][r]必然成立，同理若r+1与k之间可连接一条边，则L[r+1][l]也成立。
通过上述过程，便可由小区间一直扩大直到考虑完整个数据区间即数据1~n，此时，若存在一个k使得L[k][1]与R[k][n]同时成立，则表明可以在整个数据区间内建立一颗以k为根的二叉搜索树。

由于我们考虑的数据范围是从小区间到大区间的，且对大区间数据进行判断时，该数据区间中的小区间必然已经考虑过了，所以区间左端点由n到1进行遍历。

代码

#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 argc, char** argv) {
	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\n");
		else
			printf("No\n");
	}
	return 0;
}