week16模拟测试

A - TT数鸭子

题目要求

这一天，TT因为疫情在家憋得难受，在云吸猫一小时后，TT决定去附近自家的山头游玩。
TT来到一个小湖边，看到了许多在湖边嬉戏的鸭子，TT顿生羡慕。此时他发现每一只鸭子都不 一样，或羽毛不同，或性格不同。TT在脑子里开了一个map<鸭子，整数> tong，把鸭子变成了 一些数字。现在他好奇，有多少只鸭子映射成的数的数位中不同的数字个数小于k。 输入描述 输入第一行包含两个数n,k，表示鸭子的个数和题目要求的k。
接下来一行有n个数,$a_i$ai​，每个数表示鸭子被TT映射之后的值。 输出描述 输出一行，一个数，表示满足题目描述的鸭子的个数。
无行末空格
样例输入
6 5 123456789 9876543210 233 666 1 114514
样例输出
4
数据组成
数据点 n k $a_i$ai​
1 n<=1000 k=10 $10^6$106
2 n<=1000 k=1 $10^6$106
3,4,5 n<=$10^5$105 k<=100 $10^9$109
6,7,8,9,10 n<=$10^6$106 k<=$10^6$106 $10^{15}$1015

求解思路

将每个数读入，数的每一位对应的0~9中的一位，将num数组中这个数为下标的元素加一，num数组也就是用来记录数中所有出现的数字及其个数，num数组中个数不为0的数字的个数 即为 数的数位中不同的数字个数，判断是否小于K，并记录小于K的数字的个数
注意不要用stl，使用char数组存储而不是string，否则容易超时。

代码

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;

int num[10];
char arr[20];
int main()
{
	int n, k;
	cin >> n >> k;
	int p = 0;
	while (n--)
	{
		int con = 0;
		memset(num, 0, sizeof(int) * 10);
		for (int i = 0; i < 20; i++)
		{
			arr[i] = ',';
		}
		//string number;
		cin >> arr;
		for (int i = 0; i < 20; i++)
		{
			if (arr[i] == ',') break;
			 num[arr[i] - '0']++;
		}
		for (int i = 0; i < 10; i++)
		{
			if (num[i] != 0)
				con++;
		}
		if (con < k)
			p++;
	}
	cout << p;
}

B - ZJM要抵御宇宙射线

题目要求

题目描述 据传，2020年是宇宙射线集中爆发的一年，这和神秘的宇宙狗脱不了干系！但是瑞神和东东忙 于正面对决宇宙狗，宇宙射线的抵御工作就落到了ZJM的身上。假设宇宙射线的发射点位于一个 平面，ZJM已经通过特殊手段获取了所有宇宙射线的发射点，他们的坐标都是整数。而ZJM要构 造一个保护罩，这个保护罩是一个圆形，中心位于一个宇宙射线的发射点上。同时，因为大部分 经费都拨给了瑞神，所以ZJM要节省经费，做一个最小面积的保护罩。当ZJM决定好之后，东东 来找ZJM一起对抗宇宙狗去了，所以ZJM把问题扔给了你~ 输入描述 输入 第一行一个正整数N，表示宇宙射线发射点的个数
接下来N行，每行两个整数X,Y，表示宇宙射线发射点的位置 输出描述 输出包括两行
第一行输出保护罩的中心坐标x,y 用空格隔开
第二行输出保护罩半径的平方
（所有输出保留两位小数，如有多解，输出x较小的点，如扔有多解，输入y较小的点）
无行末空格 样例输入
5 0 0 0 1 1 0 0 -1 -1 0
样例输出
0.00 0.00
1.00
数据组成
数据点 n x y
1~5 n<=100 |x|<=10000 |y|<=10000
6~10 n<=1000 |x|<=100000 |y|<=100000

求解思路

以每个点作为保护罩的中心，找到离该点最远的点，距离的平方即为以这个点作为保护罩的中心需要的最小的半径平方。
所有点为保护罩的中心求得的保护罩的半径的平方取最小值，输出采用printf("%.2lf", conse.len)保留两位小数。

代码

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;


#define maxx 1e11
struct point
{
	double x, y;
	double len;
	bool operator<(const point& b)
	{
		if (len != b.len)
			return len < b.len;
		if (x != b.x)
			return x < b.x;
		if (y != b.y)
			return y < b.y;
	}
};
point p[1005];
int main()
{
	int n;
	cin >> n;
	for(int i=0;i<n;i++)
	{
		cin >> p[i].x >> p[i].y;
		p[i].len = 0;
	}
	for (int i = 0; i < n; i++)
	{
		double ma = 0; 
		for (int j = 0; j < n; j++)
		{
			double tmp = (p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y);
			if (tmp > ma)
			{
				ma = tmp; 
		    }
		}
		p[i].len = ma;
	}
	point conse;
	conse.len = maxx; conse.x = maxx; conse.y = maxx;
	for (int i = 0; i < n; i++)
	{
		if (p[i] < conse)
		{
			conse = p[i];
		}
	}
	printf("%.2lf ""%.2lf\n", conse.x, conse.y);
	printf("%.2lf", conse.len);
}

C - 宇宙狗的危机

题目要求

在瑞神大战宇宙射线中我们了解到了宇宙狗的厉害之处，虽然宇宙狗凶神恶煞，但是宇宙狗有一 个很可爱的女朋友。
最近，他的女朋友得到了一些数，同时，她还很喜欢树，所以她打算把得到的数拼成一颗树。
这一天，她快拼完了，同时她和好友相约假期出去玩。贪吃的宇宙狗不小心把树的树枝都吃掉 了。所以恐惧包围了宇宙狗，他现在要恢复整棵树，但是它只知道这棵树是一颗二叉搜索树，同 时任意树边相连的两个节点的gcd(greatest common divisor)都超过1。
但是宇宙狗只会发射宇宙射线，他来请求你的帮助，问你能否帮他解决这个问题。
补充知识：
GCD：最大公约数，两个或多个整数共有约数中最大的一个 ，例如8和6的最大公约数是2。
一个简短的用辗转相除法求gcd的例子：
int gcd(int a,int b){return b == 0 ? a : gcd(b,a%b);}
输入描述 输入第一行一个t，表示数据组数。
对于每组数据，第一行输入一个n，表示数的个数
接下来一行有n个数$a_i$ai​，输入保证是升序的。 输出描述 每组数据输出一行，如果能够造出来满足题目描述的树，输出Yes，否则输出No。
无行末空格。 样例输入1
1 6 3 6 9 18 36 108
样例输出1
Yes
样例输入2
2 2 7 17 9 4 8 10 12 15 18 33 44 81
样例输出2
No Yes
样例解释 样例1可构造如下图

数据组成 给出的数为上限。
数据点数
t n $a_i$ai​
1,2,3 5 15 $10^9$109
4,5,6 5 35 $10^9$109
7,8,9,10 5 700 $10^9$109

求解思路

这是一个区间dp问题，temp[i][j]表示第i个数和第j个数之间是否满足gcd超过1
lefta[l][k]==1 表示以k为根结点，l到k的范围内的结点满足要求
righta[k][r]==1 表示以k为根结点，k到r的范围内的结点满足要求
dp[l][r]==1 表示l到r的范围内的数满足要求
状态转移方程为：

if (lefta[l][k] == 1 && righta[k][r] == 1)
{
	dp[l][r] = 1;
    if (temp[k][l - 1]== 1)
		righta[l - 1][r] = 1;
	if (temp[k][r + 1] ==1)
		lefta[l][r + 1] = 1;
}

如果l到k 和 k到r满足要求，则l~r范围内就满足要求，判断k和l-1对应的数是否满足gcd超过1，满足则以l-1为根结点，l-1到r也满足要求，即向左扩展。判断k和r+1对应的数是否满足gcd超过1，满足则以l为根结点，l到r+1也满足要求，向右扩展。

最终结果只需要判断dp[1][n] == 1即可，dp[1][n] == 1表示1~n范围内满足要求。

代码

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;

int arr[705];

int gcd(int a, int b)
{
	return b == 0 ? a : gcd(b, a % b);
}
int t, n;
int dp[705][705];
int lefta[705][705];
int righta[705][705];
int temp[705][705];
void solve()
{
	memset(lefta, 0, sizeof(lefta));
	memset(righta, 0, sizeof(righta));
	memset(dp, 0, sizeof(dp));
	for (int i = 1; i <= n; i++)
	{
		lefta[i][i] = 1;
		righta[i][i] = 1;
	}
       for (int i = 1; i <= n; i++)
             for (int j = 1; j <= n; j++)
	{
               if(gcd(arr[i],arr[j])>1)
                   temp[i][j]=1;
               else
                   temp[i][j]=0;
    }
	for (int i = 1; i <= n; i++)
	{
		for (int l = 1; l <= n - i+1; l++)
		{
			int r = l - 1 + i;
			for (int k = l; k <= r; k++)
			{
				if (lefta[l][k] == 1 && righta[k][r] == 1)
				{
					dp[l][r] = 1;
					if (temp[k][l - 1]== 1)
						righta[l - 1][r] = 1;
					if (temp[k][r + 1] ==1)
						lefta[l][r + 1] = 1;
				}
			}
		}
	}
}
int main()
{
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		cin >> n;
		for (int j = 1; j <= n; j++)
		{
			cin >> arr[j];
		}
		solve();
		if (dp[1][n] == 1)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
}