苦中作乐 ---竞赛刷题冲刺篇（25分）
（一）目录
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();//清除数组it2if (!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 longusing 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;
}