week16-csp模测4

在这里插入图片描述

思路:

利用大小为10数组来记录0-9是否被标记,利用string存储数字,然后用每个字符-'0’转化为ascII码来标记并计数,每位数比较完后如果标记的个数如果小于K,则符合要求。
注意:这道题要使用ios::sync_with_stdio(false),否则会超时。

#include<iostream>
#include<algorithm>
#include<cstring>	
#include<vector>
#include<cmath>
#include<string>
#include<cstdio>
using namespace std;
int n, k;
int v[10];
int main()
{
	ios::sync_with_stdio(false);
	int ans = 0;
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		int cnt = 0;
		string a;
		cin >> a;
		memset(v, 0, sizeof(v));
		for (int j = 0; j < a.size(); j++)
		{
			if (v[(a[j] - '0')] == 0)
			{
				v[(a[j] - '0')] = 1;
				cnt++;
			}
		}
		if (cnt < k)
		{
			ans++;
		}
		
	}
	cout << ans << endl;
	return 0;
}

在这里插入图片描述

思路:

这道题可以暴力搜索,用struct存储每个点,然后按照x从小到大进行排序。然后利用两层循环,相同的点跳过。对于不相同的点,对于每层遍历,都记录(x2-x1)^2 + (y2-y1)^2并记录这层遍历的最大值,并记录半径平方和原点,再对上层遍历找出最小值并记录半径平方和原点,最后输出即可。

#include<iostream>
#include<algorithm>
#include<cstring>	
#include<vector>
#include<cmath>
#include<string>
#include<cstdio>
#include<queue>
#include<stack>
#include<map>
#include<iomanip>

using namespace std;
double minh = 100000000000000;
int n;
int a, b, ans;
double  maxr;
struct node
{
	double x;
	double y;
	node() {}
	node(double x1, double y1)
	{
		x = x1;
		y = y1;
	}
	bool operator <(const node& n1)const
	{
		if (x == n1.x)
			return y < n1.y;
		return x < n1.x;
	}
}no[1000000];
int main()
{
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a >> b;
		no[i]=node(a, b);
	}
	sort(no, no + n);
	for (int i = 0; i < n; i++)
	{
		double maxr2=0;
		for (int j = 0; j < n; j++)
		{
			if (j == i)
				continue;
			else
			{
				double r2 = pow(no[j].x - no[i].x, 2) + pow(no[j].y - no[i].y, 2);
				maxr2 = max(maxr2,r2);
			}
		}
		if (maxr2 < minh)
		{
			minh=maxr2;
			ans = i;
		}

	}
	cout << setiosflags(ios::fixed) << setprecision(2);
	cout << no[ans].x <<" "<< no[ans].y << endl;
	cout << minh <<endl;
	
}

请添加图片描述
请添加图片描述

思路:

二叉搜搜索树(Binary Search Tree),它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值。
dp思想:
c[i][j]表示区间[i,j-1]作为j的左孩子是否合法
d[i][j]表示区间[i+1,j]作为j的右孩子是否合法
设k为区间[l,r]的根,
如果c[l][k]=1且d[k][r]=1,则该状态合法,可以转移;
同时l1且rn则说明存在一颗以K为根的bst。
如果k可以与l-1相连,说明以l-1为根,[l,r]为右孩子的状态合法。
如果k可以与r+1相连,说明以r+1为根,[l,r]为左孩子的状态合法。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<iomanip>
#include<cstdio>
using namespace std;
const int maxn = 1000;
int gcd(int a, int b) 
{
	return b == 0 ? a : gcd(b, a % b);
}
int T, n;
int a[maxn];
int b[maxn][maxn], c[maxn][maxn], d[maxn][maxn], e[maxn][maxn];
int main()
{
	ios::sync_with_stdio(false);
	cin >> T;
	for (int k = 0; k < T; k++)
	{
		cin >> n;
		memset(b, 0, sizeof(b));
		memset(d, 0, sizeof(d));
		memset(e, 0, sizeof(e));
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
			b[i][i] = 1;
			d[i][i] = e[i][i] = 1;
		}
		for (int i = 1; i <= n; i++)
		{
			for (int j = i + 1; j <= n; j++)
			{
				c[i][j] = gcd(a[i], a[j]) > 1;
			}
		}
		for (int i = 1; i <= n; i++)
		{
			for (int l = 1, r = l + i - 1; r <= n; l++, r++)
			{
				for (int j = l; j <= r; j++)
				{
					if (d[l][j] && e[j][r])
					{
						b[l][r] = 1;
						if (c[l - 1][j])
							d[l - 1][r] = 1;
						if (c[j][r + 1])
							e[l][r + 1] = 1;
					}
				}
			}
		}
		if (b[1][n])
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	return 0;
}
版权声明:本文为weixin_44465341原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44465341/article/details/106682276

智能推荐

1264页面推荐(中等 union all )稍微的难点在于找1的朋友

![在这里插入图片描述](https://img-blog.csdnimg.cn/20200904233840843.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTMxNTk0,size_16,color_FFFFFF,t...

单链表+单链表代码(链表最基础)

链表 链表是有顺序的表,在内存中存储: 链表是以节点的方式存储的 每个节点包括data域,next域:指向下一个节点 如图:发现链表的各个节点不一定是连续存放的,有跳跃的,不是连续存储 链表分为带头节点的链表和没有头结点的链表 添加: 1.先创建一个head头结点,作用就是单链表的头 2.后面每添加一个节点,就直接加入到链表最后 遍历: 代码 添加节点到链表里: 这里借助于temp节点,通过循环找...

Rtthread学习笔记(十三)RT-Thread Studio开启硬件看门狗Watchdog

一、开启硬件看门狗Watchdog 1、配置RT-Thread Settings 2、开启stm32f1xx_hal_conf.h中的宏定义 3.使用RT接口函数初始化硬件看门狗...

TYVJ 4864 天天去哪吃 || 清北学堂金秋杯大奖赛

题目描述: 记录一下i这个值上次出现的位置在哪里,就是pre...

java反编译

jvm 把Boolean类型的值flag当做int类型处理。​​​ Foo.java: 由 class 文件生成 jasm 文件:java -jar asmtools.jar jdis Foo.class > Foo.jasm  修改jasm文件: 执行反编译: java -jar jd-gui-1.6.6.jar File 打开Foo.class文件:b修改为2 重新执行java...

猜你喜欢

【学习笔记】03-v-html的学习和示例

v-html的认识和使用 示例: 显示结果: 注意:v-html是有复制的...

Java实现在线考试系统(系统介绍)

1.和现在有的考试系统有以下几种优势: a.和现在有的系统比较起来,本系统有科目、章节、老师、学生、班级等信息的管理,还有批阅试卷查看已批阅试卷等。传统的考试系统划分并不细,业务功能简单。 b.和学校的考试系统还有外面的考试系统比较起来,本系统是B/S结构,学校的考试系统一般为C/S结构,性能方面不如B/S结构,并且C/S接口需要安装客户端,客户端压力很大,我的系统只需要电脑具有浏览器,在同一局域...

计算机视觉--多视几何初步尝试

基础矩阵的原理 K和K’分别是两个相机的参数矩阵。p和p’是X在平面π的坐标表示。所以可以得出 具体计算过程 代码: #!/usr/bin/env python coding: utf-8 from PIL import Image from numpy import * from pylab import * import numpy as np from imp ...

java初学者怎么学习才可以快速入门

java初学者怎么学习才可以快速入门 一、了解JAVA 我们要知道:Java是由Sun Microsystems公司于1995年5月推出的Java面向对象程序设计语言。 Java之父:詹姆斯·高斯林 1.1 java的三个体系 Java SE(Java Platform Standard Edition)。Java SE 以前称为 J2SE。它允许开发和部署在桌面、服务器、嵌入式环境...

字段属性之主键&增删改查&自增长&唯一键约束

字段属性之主键&自增长&唯一键约束 主键 主键:primary key 主要的键 一张表中只有一个字段可以使用对应的键,用来唯一的约束该字段里面的数据,不能重复,这种称之为主键 一张表只能最多一个主键 增加主键 SQL操作中有多种方式增加主键大体分为三种 1.在创建表的时候直接在字段之后跟primary key关键字(主键本身不允许为空) 优点:非常直接:缺点:只能使用一个字段作为...