天梯赛题目1_Aime1007的博客-程序员秘密

技术标签: 算法  笔记  数据结构  

L1-019 谁先倒

链接
甲、乙两人的酒量(最多能喝多少杯不倒),没注意到是喝多少杯不倒。。。
a、b来表示甲乙,1、2来来表述属性,以免混乱。

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    
    int maxa, maxb;
    int n;
    scanf("%d%d%d", &maxa, &maxb, &n);
    int nowa = 0, nowb = 0;
    for(int i = 1; i <= n; i++) {
    
    	int a1, a2, b1, b2;
    	scanf("%d%d%d%d", &a1, &a2, &b1, &b2);
    	int ans = a1 + b1;
    	if(a2 == ans && b2 != ans) {
    
    		nowa++;
		}
		else if(b2 == ans && a2 != ans) {
    
			nowb++;
		}
		if(nowa > maxa) {
    
			printf("A\n");
			printf("%d", nowb);
			break;
		}
		else if(nowb > maxb) {
    
			printf("B\n");
			printf("%d", nowa);
			break;
		}
	}
}

L2-006 树的遍历

链接
后序数组中最后一个元素即为根,找到对应中序数组中的位置,确定左右子树节点个数,递归即可。在这里插入图片描述
在这里插入图片描述

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int b[35];
int c[35];
int tLeft[35];
int tRight[35];
int n;
int build(int lb, int rb, int lc, int rc) {
    
	if(lb > rb) return 0;
	int root = c[rc];
	int index = 0;
	//找到根节点在中序数组中的位置 
	while(b[index] != root) index++;
	int count = index - lb;
	tLeft[root] = build(lb, index-1, lc, lc+count-1);
	tRight[root] = build(index+1, rb, lc+count, rc-1);
	return root;
}
void print(int root) {
    
	queue<int> q;
	q.push(root);
	int count = 1;
	while(!q.empty()) {
    
		int now = q.front();
		printf("%d", now);
		if(count != n) printf(" ");
		count++;
		q.pop();
		if(tLeft[now] != 0) q.push(tLeft[now]);
		if(tRight[now] != 0) q.push(tRight[now]);
	}
}
int main() {
    
	scanf("%d", &n);
	for(int i = 0; i < n; i++) scanf("%d", &c[i]);
	for(int i = 0; i < n; i++) scanf("%d", &b[i]);
	int root = build(0, n-1, 0, n-1);
	print(root);
}

L2-004 这是二叉搜索树吗?

链接
数组存储前序遍历序列,第一个元素为根。sl从左往右扫描,看是否都小于根,sr从右往左扫描,看是否都大于根。递归左右子树,最后将根添加到ans中,ans保存的即为后序序列。
注意:其右子树中所有结点的键值大于等于该结点的键值。

#include <iostream>
#include <cstdio>
#include <vector> 
using namespace std;
int a[1005];
int flag;
vector<int> ans;
void judge(int l, int r) {
    
	if(l > r) return;
	int sl = l + 1;
	int sr = r;
	//非镜像 
	if(flag == 0) {
    
		while(sl <= r && a[sl] < a[l]) sl++;
		//a[l]为根 
		while(sr > l && a[sr] >= a[l]) sr--;
	}
	//镜像 
	else {
    
		while(sl <= r && a[sl] >= a[l]) sl++;
		while(sr > l && a[sr] < a[l]) sr--;
	}
	if(sl - sr != 1) return;
	judge(l+1, sr);
	judge(sl, r);
	ans.push_back(a[l]);
}
int main() {
    
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
    
		scanf("%d", &a[i]);
	}
	judge(0, n-1);
	if(ans.size() != n) {
    
		flag = 1;
		ans.clear();
		judge(0, n-1);
	}
	if(ans.size() != n) printf("NO\n");
	else {
    
		printf("YES\n");
		for(int i = 0; i < n; i++) {
    
			printf("%d", ans[i]);
			if(i != n-1) printf(" ");
		}
	}
}

L2-019 悄悄关注

链接
使用map,输入被其关注的用户的ID时,映射value为1。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring> 
#include <map>
using namespace std;
map<string, int> mp;
struct node {
    
	char id[5];
	int num;
} b[10005];
int flag[10005];
bool cmp(node a, node b) {
    
	return strcmp(a.id, b.id) < 0;
}
int main() {
    
	int n, m, sum = 0;
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
    
		char s[10];
		scanf("%s", s);
		mp[s] = 1;
	}
	scanf("%d", &m);
	for(int i = 0; i < m; i++) {
    
		scanf("%s%d", b[i].id, &b[i].num);
		sum += b[i].num;
	}
	sort(b, b+m, cmp);
	float avg = 1.0 * sum / m;	
	for(int i = 0; i < m; i++) {
    
		if(mp[b[i].id] == 0) flag[i] = 1; 
	}
	int mark = 0;
	for(int i = 0; i < m; i++) {
    
		if(flag[i] == 1 && b[i].num > avg) {
    
			printf("%s\n", b[i].id);
			mark = 1;
		}
	}
	if(mark == 0) printf("Bing Mei You");
}

L2-032 彩虹瓶

链接
简单堆栈模拟

#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
stack<int> s;
int main() {
    
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= k; i++) {
    
		int now = 1;
		int flag = 0;
		while(!s.empty()) s.pop();
		for(int j = 1; j <= n; j++) {
    
			int next;
			scanf("%d", &next);
			if(next == now) {
    
				now++;
				while(!s.empty()) {
    
					if(s.top() == now) {
    
						s.pop();
						now++;
					}
					else break;
				}
			}
			else {
    
				s.push(next);
				if(s.size() > m) {
    
					flag = 1;
					//break;
				}
			}
		}
		if(s.size() == 0 && flag == 0) printf("YES\n");
		else printf("NO\n");
	}
}

L2-024 部落

链接
使用set容器统计社区的总人数。因为所有人的编号从1开始连续编号,所以扫描set集合时,下标i即对应每个人的编号。也可以用迭代器。

//直接扫描
for(int i = 1; i <= s.size(); i++) {
    
	if(fa[i] == i) {
    
		ans++;
	}
}
//迭代器
for(set<int>::iterator it = s.begin(); it != s.end(); it++) {
    
	if(fa[*it] == *it) {
    
		ans++;
	}
}
#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
int fa[10005];
set<int> s;
void init() {
    
	for(int i = 1; i <= 10000; i++) {
    
		fa[i] = i;
	}
}
int get(int x) {
    
	if(x == fa[x]) return x;
	return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
    
	x = get(x);
	y = get(y);
	if(x != y) {
    
		fa[x] = y;
	}
}
bool judge(int x, int y) {
    
	if(get(x) == get(y)) return true;
	return false;
}
int main() {
    
	int n;
	scanf("%d", &n);
	init();
	for(int i = 1; i <= n; i++) {
    
		int k, a, last;
		scanf("%d", &k);
		for(int j = 1; j <= k; j++) {
    
			scanf("%d", &a);
			if(j != 1) {
    
				merge(last, a);				
			}
			last = a;
			s.insert(a);
		}
	}
	int ans = 0;
//	for(int i = 1; i <= s.size(); i++) {
    
//		if(fa[i] == i) {
    
//			ans++;
//		}
//	}
	for(set<int>::iterator it = s.begin(); it != s.end(); it++) {
    
		if(fa[*it] == *it) {
    
			ans++;
		}
	} 
	printf("%d %d\n", s.size(), ans);
	int q;
	scanf("%d", &q);
	for(int i = 1; i <= q; i++) {
    
		int x, y;
		scanf("%d%d", &x, &y);
		if(judge(x, y)) printf("Y\n");
		else printf("N\n");
	}
}

L3-003 社交集群

链接
创建一个habit数组,存储每个爱好的祖先。当输入某个人的这个爱好时,就与这个爱好的祖先合并。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int fa[1005];
int habit[1005];
int isRoot[1005];
int n;
int cmp(int a, int b) {
    
	return a > b;
}
void init() {
    
	for(int i = 1; i <= n; i++) {
    
		fa[i] = i;
	}
}
int get(int x) {
    
	if(x == fa[x]) return x;
	return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
    
	x = get(x);
	y = get(y);
	if(x != y) {
    
		fa[x] = y;
	}
}
int main() {
    
	scanf("%d", &n);
	//每个人有k个爱好,每个爱好为h
	int k, h; 
	init(); 
	for(int i = 1; i <= n; i++) {
    
		scanf("%d:", &k);
		for(int j = 1; j <= k; j++) {
    
			scanf("%d", &h);
			if(habit[h] == 0) {
    
				//这个爱好的根节点为第i人 
				habit[h] = i;
			}
			//将i与有相同爱好的人合并
			merge(i, habit[h]);
		}
	}
	int ans = 0; 
	for(int i = 1; i <= n; i++) {
    
		isRoot[get(i)]++ ; 
	}
	for(int i = 1; i <= n; i++) {
    
		if(isRoot[i] != 0) {
    
			ans++;
		}
	}
	printf("%d\n", ans);
	sort(isRoot+1, isRoot+1+n, cmp);
	for(int i = 1; i <= ans; i++) {
    
		printf("%d", isRoot[i]);
		if(i != ans) printf(" ");
	}
	printf("\n");
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_44817002/article/details/108092695

智能推荐

产品经理看哪吒之魔童降世_weixin_30820077的博客-程序员秘密

前戏哪吒在这个暑假,一下子变成了红人。本来他人是红色的,这个也许是他能红的原因吧,一个小朋友这样说到。其实,对于整天对着电脑和媒体的程序员来说,哪吒的出现概率太高了,博客有介绍的,朋友圈内推荐的,同事饭后八卦的。都红成西红柿了,不想看都难。其实,每年出来那么多电影,能让大家广泛讨论并且有那么大群众基础的作品并不多。无论从什么角度,我都要去看一下。 看看这个新出的作品为什么火的一塌糊度...

库函数和系统调用的区别_CC_YXK的博客-程序员秘密

系统调用:操作系统为用户提供了一系列接口,这些接口提供了对硬件设备的操作。举个例子我们用printf想终端打印hello world,程序中调用printf,而printf实际上调用的是write,从而打印信息到终端。库函数:库函数是对系统调用的封装。系统调用作为内核提供给用户的接口,它执行的效率是比较高效和精简的,但有时候我们需要对获取的信息进行一些处理,我们把这些处理过程封装起来提供给程序...

1034 有理数四则运算 Python实现_猫猫虫(——)的博客-程序员秘密

1034 有理数四则运算(20)(20 分)本题要求编写程序,计算2个有理数的和、差、积、商。输入格式:输入在一行中按照“a1/b1 a2/b2”的格式给出两个分数形式的有理数,其中分子和分母全是整型范围内的整数,负号只可能出现在分子前,分母不为0。输出格式:分别在4行中按照“有理数1 运算符 有理数2 = 结果”的格式顺序输出2个有理数的和、差、积、商。注意输出的每个有理数必...

软件项目管理 1.2.PMBOK与软件项目管理知识体系_项目管理事业的爱好者的博客-程序员秘密_软件项目管理体系

软件项目管理 ——1.2.PMBOK与软件项目管理知识体系 归档于软件项目管理初级学习路线第一章 软件项目管理基本概念软件项目管理 ——1.1.基本概念文章目录软件项目管理 ——1.2.PMBOK与软件项目管理知识体系前言一、PMBOK起源和发展二、项目管理五大过程组三、项目管理十大知识领域四、软件项目管理知识体系软件开发过程的作用软件项目知识体系图总结前言大家好,这节我们学习软件项目管理 ——1.2.PMBOK与软件项目管理知识体系,采用图文的形式加深学习者的记忆说到项目管理一定要知道P

北邮OJ 299 分数加法-网研14_兄台来瓶冰阔落!的博客-程序员秘密

北邮OJ 分数加法#include &lt;bits/stdc++.h&gt;using namespace std;int main(){ int T; scanf("%d",&amp;T); while(T--){ int a,b,fenmu,fenzi; scanf("%d%d",&amp;a,&amp;b); if(a&gt;b){ fenmu=pow(2,...

随便推点

华东理工大学计算机组成原理试题,华中科技大学计算机组成原理1999年考研真题考研试题硕士研究生入学考试试题(原华东理工大学)..._Z-JO的博客-程序员秘密

华中理工大学1999硕士入学计算机组成原理真题一.填空(每空1分,共20分)1.计算机中数值数据表示长采用的格式有 和 两种。2.已知十进制数,则相应的二进制数X= ,[X]补= 。3.若X=-0.X1X2……Xn,则[X]原= ,[-X]补= 。4.主机与外部设备之间以软件方式控制信息交换的方式有 ...

python try catch finally_Java try catch finally异常处理(Exception)_金雪锋的博客-程序员秘密

1、Java Exceptions执行Java代码时,可能会发生不同的错误异常:程序员编写的编码错误,由于输入错误引起的错误或其他不可预见的情况。发生错误时,Java通常会停止并生成错误消息。 技术术语是:Java将引发异常(引发错误)。2、Java try catchtry语句允许定义要执行的错误代码块。如果在try块中发生错误,则catch语句允许定义要执行的代码块。try和catch关键字...

java异常处理_weixin_34228387的博客-程序员秘密

可直接看这篇文章即可:http://www.importnew.com/26613.htmljava异常类图非检查异常(unckecked exception):Error 和 RuntimeException 以及他们的子类。javac在编译时,不会提示和发现这样的异常,不要求在程序处理这些异常。所以如果愿意,我们可以编写代码处理(使用try…catch…finally)这样的异常,...

MySQL check the manual that corresponds to your MySQL server version for the right syntax错误_samile6899的博客-程序员秘密

最近在做一个Web项目的时候,SSH框架实体映射生成表的时候,其中一个实体无法生成相应的数据表,在仔细分析了日志的情况下,找到了相关的错误信息,错误信息显示“  You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right synt

Ubuntu刚使用时的问题_mingtianwendy的博客-程序员秘密

一、刚安装好的Linux系统设置root密码: 二、Linux安装vmwareTools.tar文件时报:无法mkdir, 只读文件系统 一般要将vmwareTools.tar拷贝到/tmp文件夹下解压并安装 安装完成后可以从Windows系统中复制内容到Ubuntu系统三、网络设置:要让Ubuntu与Windows主机处于同一个网段在虚拟机的编辑——虚拟网络编辑器——虚拟机网络采用桥接模式

什么是项目管理,如何做好项目管理?_[虚幻私塾】的博客-程序员秘密_项目管理

Python微信订餐小程序课程视频https://edu.csdn.net/course/detail/36074Python实战量化交易理财系统https://edu.csdn.net/course/detail/35475原创不易,求分享、求一键三连两个故事防疫这个项目近来,离大家最近的大项目应该是防疫,之前西安防疫事件引起了不小的波动:比如紧急人员因为没有核酸证明不能入院导致不好的结果;比如小区隔离人员没有很好的物资补给,而导致生活困难旁生枝节…这些都是Bad Case

推荐文章

热门文章

相关标签