苦中作乐 ---竞赛刷题冲刺篇（25分）

news/2024/7/15 18:03:49 标签: c++, 图论, 算法

（一）目录

L2-001 紧急救援 

L2-002 链表去重

L2-003 月饼 

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

L2-005 集合相似度

 

（二） 题目

L2-001 紧急救援 

        作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

输入格式:

输入第一行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0 ~ (N−1)；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。

第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。

输出格式:

第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。

输入样例:

4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2

输出样例:

2 60
0 1 3

 分析：

代码：

 #include<iostream>
#include<stack>
using namespace std;
#define max 501
#define inf 0xffffff
int edges[max][max];//图
int visited[max];//节点是否访问
int citysaver[max];//该城市的救援队数量
int savercount[max];//总的救援队数量
int path[max];//城市的路径
int pathcount[max];//最短路径的数量
int dist[max];
void Dijkstra(int s,int n)
{
	dist[s] = 0;	path[s] = -1;	pathcount[s] = 1;	savercount[s] = citysaver[s];
	//开始循环之前的各个数组的初始化
	for (int i = 0; i < n; i++)	{
        if(i!=s)
		dist[i] = edges[s][i];
	} 
	for (int i = 0; i < n; i++)
	{
		int u=-1, min = inf;
		for (int j = 0; j < n; j++)
		{
			if (/*dist[j] != 0 &&*/ dist[j] != inf&&visited[j] == 0)
			{
				if (visited[j] == 0&&dist[j] < min) { min = dist[j]; u = j; }
		}	}
		if (u == -1)return;
		visited[u] = 1;
		for (int j = 0; j < n; j++)	{
			if (dist[u] + edges[u][j] < dist[j]&&visited[j]==0&&edges[u][j]!=inf){
				dist[j] = dist[u] + edges[u][j];
				pathcount[j] = pathcount[u];
				savercount[j] = savercount[u] + citysaver[j];
				path[j] = u;}
			else if (dist[u] + edges[u][j] == dist[j] && visited[j] == 0 && edges[u][j] != inf)
			{
				pathcount[j] += pathcount[u];
				if (savercount[u] + citysaver[j] > savercount[j])		{
					savercount[j] = savercount[u] + citysaver[j];
					path[j] = u;
				}
			}
		}
	}
 
}
 
int main()
{
	int n, m, s, d;
	cin >> n >> m >> s >> d;
	for (int i = 0; i < max; i++)
		for (int j = 0; j < max; j++)
			//if (i != j)
				edges[i][j] = inf;
			//else edges[i][j] = 0;
 
			for (int i = 0; i < n; i++)
				cin >> citysaver[i];
			for (int i = 0; i < m; i++)
			{
				int a, b, c;
				cin >> a >> b >> c;
				edges[a][b] = edges[b][a] = c;
			}
			Dijkstra(s,n);
			cout << pathcount[d] << " " << savercount[d] << endl;
			stack<int>ss;
			ss.push(d);
			while (path[d] != 0)
			{
				ss.push(path[d]);
				d = path[d];
			}
			cout << s;
			while (!ss.empty())
			{
				cout << " " << ss.top(); ss.pop();
			}
			cout << endl;
}

L2-002 链表去重

       给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。

输入格式：

输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤105，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 −1 来表示。

随后 N 行，每行按以下格式描述一个结点：

地址 键值 下一个结点

其中地址是该结点的地址，键值是绝对值不超过104的整数，下一个结点是下个结点的地址。

输出格式：

首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。

输入样例：

00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854

输出样例：

00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1

代码： 

L2-003 月饼

     月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。

注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有 3 种月饼，其库存量分别为 18、15、10 万吨，总售价分别为 75、72、45 亿元。如果市场的最大需求量只有 20 万吨，那么我们最大收益策略应该是卖出全部 15 万吨第 2 种月饼、以及 5 万吨第 3 种月饼，获得 72 + 45/2 = 94.5（亿元）。

输入格式：

每个输入包含一个测试用例。每个测试用例先给出一个不超过 1000 的正整数 N 表示月饼的种类数、以及不超过 500（以万吨为单位）的正整数 D 表示市场最大需求量。随后一行给出 N 个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出 N 个正数表示每种月饼的总售价（以亿元为单位）。数字间以空格分隔。

输出格式：

对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后 2 位。

输入样例：

3 20
18 15 10
75 72 45

输出样例：

94.50

 

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

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，

  • 其左子树中所有结点的键值小于该结点的键值；
  • 其右子树中所有结点的键值大于等于该结点的键值；
  • 其左右子树都是二叉搜索树。

所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入格式：

输入的第一行给出正整数 N（≤1000）。随后一行给出 N 个整数键值，其间以空格分隔。

输出格式：

如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出 YES ，然后在下一行输出该树后序遍历的结果。数字间有 1 个空格，一行的首尾不得有多余空格。若答案是否，则输出 NO。

输入样例 1：

7
8 6 5 7 10 8 11

输出样例 1：

YES
5 7 6 8 11 10 8

输入样例 2：

7
8 10 11 8 6 7 5

输出样例 2：

YES
11 8 10 7 5 6 8

输入样例 3：

7
8 6 8 5 10 9 11

输出样例 3：

NO

 分析：我的理解是对于一样的数，都进行镜象处理，都把其放在A数组中（方便比较前序）一棵是正常的，一棵是镜像的，怎么处理呢？正常分为两棵树进行数据插入，然后再来个前序遍历（两者相同的可以共用），对于正常树进行前序遍历，并把数据存进B数组里，对比A,B数组，如果相同，直接得出，如果不同，再拿镜像树来重复上述过程。

16分代码：

#include <stdlib.h>			//system头文件
#include <stdio.h>
 #include <iostream>
#include <vector>

using namespace std;
//处理二叉搜索树的数据
typedef struct dataPair
{
	int first;			//比较准备
	char second[20];	//字符串数据位例
}DATa, * LPDATA;

typedef int DATA ;
vector<int> it1, it2;
//二叉树的节点
typedef struct treeNode
{
	DATA data;
	struct treeNode* LChild;
	struct treeNode* RChild;
}NODE, * LPNODE;

LPNODE createNode(DATA data)
{
	LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
	newNode->data = data;
	newNode->LChild = NULL;
	newNode->RChild = NULL;
	return newNode;
}

//二叉搜索树  BST bianry search Tree
typedef struct binarySearchTree
{
	LPNODE root;			//根节点
	int treeSize;
}BST, * LPBST;
//创建树就是描述树的最初状态,从无到有
LPBST createBST()
{
	LPBST tree = (LPBST)malloc(sizeof(BST));
	tree->root = NULL;
	tree->treeSize = 0;
	return tree;
}
 
void insertNode(LPBST tree, DATA data)
{
	LPNODE newNode = createNode(data);		//插入数据变成一个节点
	//找合适的位置
	LPNODE pMove = tree->root;
	LPNODE pMoveParent = NULL;
	while (pMove != NULL)
	{
		pMoveParent = pMove;
		//怎么走?
		if (data < pMove->data)
		{
			pMove = pMove->LChild;
		}
		else if (data >= pMove->data)
		{
			pMove = pMove->RChild;
		}
	 
	}
	//分析查找结果
	if (tree->root == NULL)
	{
		tree->root = newNode;
	}
	else
	{
		//如果不为NULL 考虑插在parent左边还是右边
		if (pMoveParent->data > data)
		{
			pMoveParent->LChild = newNode;
		}
		else
		{
			pMoveParent->RChild = newNode;
		}
	}
	tree->treeSize++;
}
void insertNode1(LPBST tree, DATA data)
{
	LPNODE newNode = createNode(data);		//插入数据变成一个节点
	//找合适的位置
	LPNODE pMove = tree->root;
	LPNODE pMoveParent = NULL;
	while (pMove != NULL)
	{
		pMoveParent = pMove;
		//怎么走?
		if (data > pMove->data)
		{
			pMove = pMove->LChild;
		}
		else if (data <=  pMove->data)
		{
			pMove = pMove->RChild;
		}

	}
	//分析查找结果
	if (tree->root == NULL)
	{
		tree->root = newNode;
	}
	else
	{
		//如果不为NULL 考虑插在parent左边还是右边
		if (pMoveParent->data <  data)
		{
			pMoveParent->LChild = newNode;
		}
		else
		{
			pMoveParent->RChild = newNode;
		}
	}
	tree->treeSize++;
}
 
void printNode(LPNODE curNode)
{
	printf("%d ", curNode->data );
}
//2.二叉搜索中序遍历 结果是有序的
void  Back_Order(LPNODE tree)
{
	if (tree != NULL)
	{
		Back_Order(tree->LChild);
		Back_Order(tree->RChild);
		 
		it2.push_back(tree->data);
	}
}
 
void  Head_Order(LPNODE tree)
{
	if (tree != NULL)
	{	 
		it1.push_back(tree->data); 
		Head_Order(tree->LChild);
		Head_Order(tree->RChild);	
	}
}
int main()
{
	LPBST tree = createBST(); LPBST tree1 = createBST();
	int data,n;
	cin >> n;	 
	for (int i = 0; i < n; i++)
	{
		cin >> data;
		insertNode(tree, data);
		insertNode1(tree1, data);
		it2.push_back(data);
	}
	bool flag = true;
	Head_Order(tree->root);
	for (int i = 0; i < it1.size()&& i < it2.size(); i++)
	{
		if (it1[i] != it2[i])
		{
			flag = false;
			it1.clear();//把存放正常树的数组清空
			Head_Order(tree1->root);		 
			for (int i = 0; i < it1.size() && i < it2.size(); i++)
			{
				if (it1[i] != it2[i])
				{
					flag = false;
				}
				else
				{
					flag = true;
				}
			}
		}
	}
	 
	it2.clear();//清除数组it2
	if (!flag) {
		printf("NO");
	}
	else {
		 Back_Order(tree->root);
		 printf("YES\n%d",it2[0]);
		 for (int  i = 1; i < it2.size(); i++)
		 {
			 printf(" %d", it2[i]);
		 }
		     
	}
	
  
	return 0;
}

满分代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef pair<int,int>P;
const int INF=0x3f3f3f3f;
const int N=1015,mod=32767;
bool isMirror=false;
vector<int>pre;
vector<int>post;
void getpost(int root,int tail){
    if(root>tail)return ;
    int i=root+1,j=tail;
    if(!isMirror){
        while(i<=tail&&pre[root]>pre[i])i++;
        while(j>root&&pre[root]<=pre[j])j--;
    }
    else{
        while(i<=tail&&pre[root]<=pre[i])i++;
        while(j>root&&pre[root]>pre[j])j--;
    }
    if(i-j!=1)return ;
    getpost(root+1,j);
    getpost(i,tail);
    post.push_back(pre[root]);
}
int main(){
    int n;
    scanf("%d",&n);
    pre.resize(n);
    for(int i=0;i<n;i++)scanf("%d",&pre[i]);
    getpost(0,n-1);
    if(post.size()!=n){
        isMirror=true;
        post.clear();
        getpost(0,n-1);
    }
    if(post.size()==n){
        printf("YES\n%d",post[0]);
        for(int i=1;i<n;i++){
            printf(" %d",post[i]);
        }
        printf("\n");
    }
    else printf("NO\n");
}

L2-005 集合相似度

       给定两个整数集合，它们的相似度定义为：Nc​/Nt​×100%。其中Nc​是两个集合都有的不相等整数的个数，Nt​是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。

输入格式：

输入第一行给出一个正整数N（≤50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（≤104），是集合中元素的个数；然后跟M个[0,109]区间内的整数。

之后一行给出一个正整数K（≤2000），随后K行，每行对应一对需要计算相似度的集合的编号（集合从1到N编号）。数字间以空格分隔。

输出格式：

对每一对需要计算的集合，在一行中输出它们的相似度，为保留小数点后2位的百分比数字。

输入样例：

3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3

输出样例：

50.00%
33.33%

 分析：

代码：


 
#include <iostream>
#include <algorithm>
#include <string>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <set>
#define ll long long
 
using namespace std;
 
int main()
{
    int n, m, k;
    while(cin >> n)
    {
        // 使用 set， 可以进行去重
        set<int >s[55];
        for (int i = 0;i < n;i ++)
        {
            cin >> k;
            for (int j = 0;j < k;j ++)
            {
                cin >> m;
                s[i].insert(m);
            }
        }
        cin >> m;
        int x, y;
        set<int> :: iterator it;
        for (int i = 0;i < m;i ++)
        {
            cin >> x >> y;
            x --;
            y --;
            int num = 0;
            for (it = s[x].begin(); it != s[x].end(); it ++)
            {
                // 判断当前元素是否在 s[y] 中出现过
                if (s[y].count(*it))
                    num ++;
            }
            // 判断最后一个元素是否在 s[y] 集合中出现过
            if (s[y].count(*(s[x].end())))
                num ++;
//            cout << num << endl;
            printf("%.2f%%\n", (double)(num) / ((double)(s[x].size() + s[y].size() - num)) * 100.0);
        }
    }
    return 0;
}


http://www.niftyadmin.cn/n/240672.html

相关文章

Nvidia Jetson Orin: SPE/AON Cortex-R5 固件开发

Nvidia Jetson Orin: SPE/AON Cortex-R5 固件开发

Nvidia Jetson Orin: SPE/AON Cortex-R5 固件开发 写在最前边开发/下载 SPE 固件关于修改DTS 写在最前边 SPE 只能控制 AON GPIO 最多32个PIN 开发/下载 SPE 固件 S1&#xff1a;打开 https://developer.nvidia.com/embedded/jetson-linux S2&#xff1a;这里下载 S3&#x…
阅读更多...
微前端框架qiankun剖析

微前端框架qiankun剖析

一、single-spa简介 要了解qiankun的实现机制&#xff0c;那我们不得不从其底层依赖的single-spa说起。随着微前端的发展&#xff0c;我们看到在这个领域之中出现了各式各样的工具包和框架来帮助我们方便快捷的实现自己的微前端应用。在发展早期&#xff0c;single-spa可以说是…
阅读更多...
分类预测 | MATLAB实现BO-CNN-GRU贝叶斯优化卷积门控循环单元多输入分类预测

分类预测 | MATLAB实现BO-CNN-GRU贝叶斯优化卷积门控循环单元多输入分类预测

分类预测 | MATLAB实现BO-CNN-GRU贝叶斯优化卷积门控循环单元多输入分类预测 目录 分类预测 | MATLAB实现BO-CNN-GRU贝叶斯优化卷积门控循环单元多输入分类预测效果一览基本介绍模型描述程序设计参考资料 效果一览 基本介绍 基于贝叶斯(bayes)优化卷积神经网络-门控循环单元(CN…
阅读更多...
高压放大器应用之无损检测

高压放大器应用之无损检测

在高压放大器的应用中&#xff0c;很多电子工程师经常会进行无损检测实验&#xff0c;那么无损检测是什么&#xff0c;无损检测的知识又有哪些呢&#xff0c;就让安泰电子带大家来看看。 无损检测是什么&#xff1a; 无损检测是指不损害物品的情况下对产品进行检测的方法&#…
阅读更多...
【微信小程序】生命周期，插槽和组件间通信

【微信小程序】生命周期，插槽和组件间通信

一、组件的生命周期 1.1 组件全部的生命周期函数 小程序组件可用的全部生命周期如下表所示 生命周期函数参数描述说明created无在组件实例刚刚被创建时执行attached无在组件实例进入页面节点树时执行ready无在组件在视图层布局完成后执行moved无在组件实例被移动到节点树另一…
阅读更多...
家庭智能吸顶灯一Homekit智能

家庭智能吸顶灯一Homekit智能

买灯要看什么因素 好灯具的灯光可以说是家居的“魔术师”&#xff0c;除了实用的照明功能外&#xff0c;对细节的把控也非常到位。那么该如何选到一款各方面合适的灯呢&#xff1f; 照度 可以简单理解为清晰度&#xff0c;复杂点套公式来说照度光通量&#xff08;亮度&#x…
阅读更多...
RflySim平台使用篇 | Coptersim系列教程（三）

RflySim平台使用篇 | Coptersim系列教程（三）

# 导读 # CopterSim作为RflySim平台核心仿真软件&#xff0c;其主要实现两部分功能&#xff1a;模型和通信&#xff0c;掌握CopterSim使用方法即可轻松运行多旋翼运动动态模型&#xff0c;并连同其他软件构成软/硬件在环仿真。本篇教程将详细介绍coptersim仿真log数据获取。 Co…
阅读更多...
Mysql不同服务器跨库查询解决方案

Mysql不同服务器跨库查询解决方案

项目场景&#xff1a; Mysql在不同服务器实现跨库查询&#xff0c;类似dblink。 解决方案&#xff1a; 在两台不同服务器&#xff0c;实现跨库查询&#xff0c;其实现原理类似一个虚拟映射,需要用到mysql的另一个存储引擎Federated&#xff0c;FEDERATED存储引擎访问在远程数据…
阅读更多...
最新文章

Copyright @ 2022~2023