软件开发教程 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试
游戏开发 网络协议 系统运维 HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程
C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
 
   -> 数据结构与算法 -> 2021.7.15 jzoj题解与反思 -> 正文阅读

[数据结构与算法]2021.7.15 jzoj题解与反思

【普及组】模拟赛C组

写在前面:

? ? ? ? 我没了啊

????????10分钟打完T1和T2(分数+200)

????????T3看完不会,跳过(所以火星人到底是怎么交换两个手指的啊!还有我TM怎么就成了宇航员?)

????????后面T4怒打900+行代码(time-3h)(分数+0,哭)

? ? ? ? 最后20分钟,无能狂怒(TM的,T4样例都过不了)

? ? ? ? 算了,不哭,失败是成功他娘,明天加油(日常灌鸡汤)

T1:

题目大意:

?????????鲁宾逊先生有一只宠物猴,名叫多多。这天,他们两个正沿着乡间小路散步,突然发现路边的告示牌上贴着一张小小的纸条:“欢迎免费品尝我种的花生!”。 鲁宾逊先生和多多都很开心,因为花生正是他们的最爱。在告示牌背后,路边真的有一块花生田,花生植株整齐地排列成矩形网格(如图1)。

有经验的多多一眼就能看出,每棵花生植株下的花生有多少。为了训练多多的算术,鲁宾逊先生说:“你先找出花生最多的植株,去采摘它的花生;然后再找出剩下的植株里花生最多的,去采摘它的花生;依此类推,不过你一定要在我限定的时间内回到路边。”
我们假定多多在每个单位时间内,可以做下列四件事情中的一件:

从路边跳到最靠近路边(即第一行)的某棵花生植株;
从一棵植株跳到前后左右与之相邻的另一棵植株;
采摘一棵植株下的花生;
从最靠近路边(即第一行)的某棵花生植株跳回路边。
现在给定一块花生田的大小和花生的分布,请问在限定时间内,多多最多可以采到多少个花生?注意可能只有部分植株下面长有花生,假设这些植株下的花生个数各不相同。 例如在图2所示的花生田里,只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生,个数分别为13, 7, 15, 9。沿着图示的路线,多多在21个单位时间内,最多可以采到37个花生。

正解:

看眼题目,这不就暴力吗

直接上,然后给有花生的草排个序就行(数据这么水,选择排序走起)

代码:

#include<bits/stdc++.h>
using namespace std;
int n,m,h,p[25][25],f,s;
struct abc{
	int q,p,x;
}a[500];
int main(){
	scanf("%d%d%d",&n,&m,&h);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			scanf("%d",&p[i][j]);
			if(p[i][j]){
				a[++f].p=i;
				a[f].q=j;
				a[f].x=p[i][j];
			}
		}
	for(int i=1;i<f;i++){
		for(int j=i+1;j<=f;j++){
			if(a[i].x<a[j].x){
				swap(a[i].x,a[j].x);
				swap(a[i].q,a[j].q);
				swap(a[i].p,a[j].p);
			}
		}
	}
	if(2*a[1].p+1>h){
		printf("0");
		return 0;
	}
	s+=a[1].x;
	h-=(a[1].p+1);
	for(int i=1;i<=f;i++){
		if(h>=a[i].p){
			s+=a[i+1].x;
			h-=(abs(a[i+1].p-a[i].p)+abs(a[i+1].q-a[i].q)+1);
		}
		else{
			printf("%d",s-a[i].x);
			return 0;
		}
	}
	printf("%d",s);
}

T2:

题目大意:

我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含“0”又含“1”的串则称为F串。

FBI树是一种二叉树[1],它的结点类型也包括F结点,B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T,递归的构造方法如下:

T的根结点为R,其类型与串S的类型相同;

若串S的长度大于1,将串S从中间分开,分为等长的左右子串S1和S2;由左子串S1构造R的左子树T1,由右子串S2构造R的右子树T2。

现在给定一个长度为2N的“01”串,请用上述构造方法构造出一棵FBI树,并输出它的后序遍历[2]序列。

[1] 二叉树:二叉树是结点的有限集合,这个集合或为空集,或由一个根结点和两棵不相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。

[2] 后序遍历:后序遍历是深度优先遍历二叉树的一种方法,它的递归定义是:先后序遍历左子树,再后序遍历右子树,最后访问根。

正解:

看眼题目,啊。。。这,老水题了,递归就能做(好像二重循环也行)

代码:

#include<bits/stdc++.h>
using namespace std;
int n,ans;
char c[2000];
int dg(int l,int r){
	if(l==r){
		if(c[l]=='0'){
			printf("B");
			return 2;
		}
		else{
			printf("I");
			return 3;
		}
	}
	int x=dg(l,(l+r)/2),y=dg((l+r)/2+1,r);
	if(x==1||y==1){
		printf("F");
		return 1;
	}
	if(x==y){
		if(x==2){
			printf("B");
			return 2;
		}
		else{
			printf("I");
			return 3;
		}
	}
	printf("F");
	return 1;
}
int main(){
	scanf("%d\n",&n);
	n=1<<n;
	for(int i=1;i<=n;i++)
		scanf("%c",&c[i]);
	dg(1,n);
}

T3:

题目大意:

人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言,但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的,首先,火星人把一个非常大的数字告诉人类科学家,科学家破解这个数字的含义后,再把一个很小的数字加到这个大数上面,把结果告诉火星人,作为人类的回答。 火星人用一种非常简单的方式来表示数字——掰手指。火星人只有一只手,但这只手上有成千上万的手指,这些手指排成一列,分别编号为1,2,3……。火星人的任意两根手指都能随意交换位置,他们就是通过这方法计数的。 一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指——拇指、食指、中指、无名指和小指分别编号为1,2,3,4和5,当它们按正常顺序排列时,形成了5位数12345,当你交换无名指和小指的位置时,会形成5位数12354,当你把五个手指的顺序完全颠倒时,会形成54321,在所有能够形成的120个5位数中,12345最小,它表示1;12354第二小,它表示2;54321最大,它表示120。下表展示了只有3根手指时能够形成的6个3位数和它们代表的数字: 三进制数 123 132 213 231 312 321 代表的数字 1 2 3 4 5 6 现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指,科学家会告诉你要加上去的很小的数。你的任务是,把火星人用手指表示的数与科学家告诉你的数相加,并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。

考试时:

第一眼:火星人?

第二眼:万根手指?

第三眼:妈,我上火星了!!!

正解:

改题后:什么鬼,就这就这就这?(考试的时候怎么没对)

类似于找规律吧(用next_premutation()的家伙们,提前毕业(鼓掌))

自己看代码理解,别抄(博主复制不易,请勿再次复制)

代码:

#include<bits/stdc++.h>
using namespace std;
int n,m,a[10010],b[10010];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int aa=1;aa<=m;aa++){
		if(a[n]>a[n-1]) swap(a[n],a[n-1]);
		else
		for(int i=n-2;i>=1;i--){
			int minn=1e9,x;
			for(int j=i+1;j<=n;j++)
				if(a[j]>a[i]&&minn>a[j]) minn=a[j],x=j;
			if(minn==1e9) continue;
			swap(a[i],a[x]);
			sort(a+i+1,a+n+1);
			break;
		}
	}
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
}

T4:

题目大意:

考试时:

10min打完高精度

然后看着(1000<P<3100000)陷入了沉思

接着放弃思考,怒打900+行优化(原地爆0,哭)

正解:

我们使用数学来求出位数后再用快速幂和高精度即可(考试的时候你怎么没想到)

不过我们今天不说这个(相信你们都会上面的)

我们讲yzn奆佬的方法

————————————华丽的分割线————————————————

我们知道long long可表示的范围是(-2^63~2^63-1)

所以我们可以不用跑普通高精度的for(1~n) x*=2(简写,相信你们可以看懂)

直接跑一个for(1~n/50) x*=1<<50 和一个for(1~n%50) x*=2

代码:

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
long long a[1005],n,m,w,t;
void nm(int x){
	if(x) t=1125899906842624;
	else t=2;
	w=0;
	for(int i=1;i<=500;i++){
		a[i]=a[i]*t+w;
		w=a[i]/10;
		a[i]%=10;
	}
}
int main(){
	scanf("%lld",&n);
	m=n/log2(10)+1;
	printf("%lld\n",m);
	a[1]=1;
	for(int i=1;i<=n/50;i++) nm(1);
	for(int i=1;i<=n%50;i++) nm(0);
	a[1]-=1;
	for(int i=500;i>=1;i--)
		printf("%lld",a[i]);
}

写在后面:

我最近的脑子好像有什么问题

那么多简单的题都能WA

算了明天继续加油(祝所有人明天考试rp++)

你们的三连就是对我最好的支持,谢谢(真心的感谢)

  数据结构与算法 最新文章
PTA (乙级)1035 插入与归并 (25 分)
动态规划学习
A. Find The Array
读《大话数据结构》记录Day 01
排序算法:希尔排序_代码
玩转算法(十二)——链表(删除链表)
西瓜书第四章拾遗
紫书第6章 数据结构基础 例题A~D
122 买卖股票的最佳时机-02
求二叉树最大深度
上一篇文章           查看所有文章
加:2021-07-17 12:12:08  更:2021-07-17 12:14:45 
 
360图书馆 购物 三丰科技 阅读网 日历 万年历 2021年7日历 -2021/7/27 4:04:23-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件开发教程