【作业向】程序设计思维与实践 CSP-M4

♔A TT数鸭子

一道简单的模拟题，读入一个数后记录在不同位上出现的不同数字的个数即可。以及k大于10的时候已经没有意义了，因此不用在意。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<utility>
#include<map>
#include<string>
#define ll long long
using namespace std;
ll n,k,cnt,ans;
ll visit[10];

int main()
{
	ll i,j;
	scanf("%lld%lld",&n,&k);
	for(i=1;i<=n;i++)
	{
		cnt=0;
		for(j=0;j<10;j++) visit[j]=0;
		scanf("%lld",&j);
		while(j)
		{
			if(!visit[j%10]) 
			{
				visit[j%10]=1;
				cnt++;
			}
			j/=10;
		}
		if(cnt<k) ans++;
	}	
	printf("%lld",ans);
	return 0;
}

♔B ZJM要抵御宇宙射线

这一题是要找以某点为中心到其他各点的距离的最大值的最小值，因为数据量不是很大，直接n^2 的复杂度枚举就可以。有一个坑点在于最小值的初始值要足够大，如果是用double类型最好使用使用LDBL_MAX作为最大值。（我用INT_MAX得了90分orz

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<utility>
#include<map>
#include<string>
#include<float.h> 
#define ll long long
using namespace std;
struct data
{
	double x,y;
}zb[1005];
int n,zx;
double minm=LDBL_MAX,maxm,tp;

int wly(data a,data b)
{
	if(a.x<b.x) return 1;
	if(a.x==b.x && a.y<b.y) return 1;
	return 0; 
}

int main()
{
	int i,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%lf%lf",&zb[i].x,&zb[i].y);
	sort(zb+1,zb+1+n,wly);
	for(i=1;i<=n;i++)
	{
		maxm=0.0;
		for(j=1;j<=n;j++)
		{
			tp=(zb[i].x-zb[j].x)*(zb[i].x-zb[j].x)+(zb[i].y-zb[j].y)*(zb[i].y-zb[j].y);
			maxm=max(maxm,tp);
		}
		if(maxm<minm)
		{
			minm=maxm;
			zx=i;
		}
	}
	printf("%.2lf %.2lf\n%.2lf",zb[zx].x,zb[zx].y,minm);
	return 0;
}

♔C 宇宙狗的危机

一道区间dp的题目，由于是一颗二叉搜索树，所以其中序遍历必然是不下降的。所以，可以将序列中连续的某一段当做一颗子树来处理。

dp数组的状态可以定义为

• dp(i,j,0)表示区间[l,r]构成的子树是否可以以al−1为根
• dp(i,j,1)表示区间[l,r]构成的子树是否可以以ar+1为根

转移时

• 如果dp[l] [k−1]=1且dp[k+1] [r]=1且gcdx(ak,al−1)大于1，则dp[l] [r] [0]=1;
• 如果dp[l] [k−1]=1且dp[k+1] [r]=1且gcdx(ak,ar+1)大于1，则dp[l] [r] [1]=1.

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<utility>
#include<map>
#include<string>
#define ll long long
using namespace std;
int n,T;
int a[705],gcdx[705][705],dp[705][705][2];

int gcd(int a,int b){return b == 0 ? a : gcd(b,a%b);}

int main()
{
	int i,j,k;
	scanf("%d",&T);
	while(T--)
	{
		memset(dp,0,sizeof(dp));
		memset(gcdx,0,sizeof(gcdx));
		scanf("%d",&n);
		for(i=1;i<=n;i++) 
			scanf("%d",&a[i]);
		for(i=1;i<=n;i++)
			for(j=i+1;j<=n;j++)
				gcdx[i][j]=gcdx[j][i]=gcd(a[i],a[j]);
		for(i=1;i<=n;i++)
		{
			gcdx[0][i]=gcdx[i][0]=gcdx[i][n+1]=gcdx[n+1][i]=2;
			if(gcdx[i][i-1]>1) dp[i][i][0]=1;
			if(gcdx[i][i+1]>1) dp[i][i][1]=1;
		}
		for(int t=1;t<=n;t++)
		{
			for(i=1;i+t<=n;i++)
			{
				j=i+t;
				for(k=i;k<=j;k++)
				{
					if((i==k || dp[i][k-1][1]) && (j==k || dp[k+1][j][0]))
					{
						if(gcdx[k][i-1]>1) dp[i][j][0]=1;
						if(gcdx[k][j+1]>1) dp[i][j][1]=1;
					}
				}
			}
		}
		if(dp[1][n][0] || dp[1][n][1])
			printf("Yes");
		else printf("No");
		if(T) printf("\n");
	}
	return 0;
}