JLU数据结构荣誉课——第六次上机实验
7-1 高精度数加法 (100 分)
高精度数是指大大超出了标准数据类型能表示的范围的数，例如10000位整数。很多计算问题的结果都很大，因此，高精度数极其重要。
一般使用一个数组来存储高精度数的所有数位，数组中的每个元素存储该高精度数的1位数字或多位数字。 请尝试计算：N个高精度数的加和。这个任务对于在学习数据结构的你来说应该是小菜一碟。 。
输入格式:
第1行，1个整数N，表示高精度整数的个数，(1≤N≤10000)。
第2至N+1行，每行1个高精度整数x, x最多100位。
输出格式:
1行,1个高精度整数，表示输入的N个高精度数的加和。
输入样例:
在这里给出一组输入。例如
3
12345678910
12345678910
12345678910
输出样例: 在这里给出相应的输出。例如
37037036730
思路：高精度加法，通过字符数组形式输入，将数组倒置遍历相加，存入整型数组中，最后倒着输出结果。(本题目没有负数，可以放心按照正数处理。)我的代码为负数与正数均可处理。
代码如下：
//#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
char num1[101];
char num2[101];
int num[1000100];
int numm[1000100];
int len1 = 0;
int len2 = 0;
bool flag = true;
void Plus1(char*n)//对正数的相加
{
int j = 1;
int ans = 0;
for (int i = strlen(n) - 1; i >= 0; i--, j++)
{
int d = num[j] + (n[i] - '0') + ans;
if (d >= 10)
{
ans = 1;
num[j] = d % 10;
}
else
{
num[j] = d;
ans = 0;
}
}
num[j] += ans;
while (num[j]>= 10)
{
num[j] -= 10;
num[++j]++;
}
len1 = max(len1, j);
}
void Plus2(char*n)//对负数的相加
{
int j = 1;
int ans = 0;
for (int i = strlen(n) - 1; i >=1; i--, j++)
{
int d = numm[j] + (n[i] - '0') + ans;
if (d >= 10)
{
ans = 1;
numm[j] = d % 10;
}
else
{
numm[j] = d;
ans = 0;
}
}
numm[j] += ans;
while (numm[j] >= 10)
{
numm[j]-= 10;
numm[++j]++;
}
len2 = max(len2, j);
}
void Minus(int*n1,int*n2,int len1,int len2)//大和减小和函数
{
int ans = 0;
for (int i = 1; i <= len1; i++)
{
int d = n1[i] - n2[i] + ans;
if (d < 0)
{
ans = -1;
n1[i] = d + 10;
}
else
{
ans = 0;
n1[i] = d;
}
}
int j = len1;
while (n1[j] == 0)
j--;
if (!flag)printf("-");
for (int i = j; i >= 1; i--)
{
printf("%d", n1[i]);
}
}
int main()
{
int m;
scanf("%d", &m);
scanf("%s", num2);
if (num2[0] == '-')
{
Plus2(num2);
}
else Plus1(num2);
for (int i = 1; i <= m-1; i++)
{
memset(num1, 0, sizeof(num1));
scanf("%s", num1);
if (num1[0] == '-')//判断用哪个加和
{
Plus2(num1);
}
else
{
Plus1(num1);
}
}
if (len1 > len2)
{
Minus(num, numm, len1, len2);
}//判断和的大小，来确定被加数和加数
else if (len1 < len2)
{
flag = false;
Minus(numm, num, len2, len1);
}
else
{
int f = 0;
for (int i = 1; i <= len1; i++)
{
if (num[i] > numm[i]) { Minus(num, numm, len1, len2); return 0; }
else if (num[i] < numm[i]) { flag = false; Minus(numm, num, len2, len1); return 0; }
}
}
return 0;
}
反思：C++作业封装的不好，QAQ。
7-2 二叉树加权距离 (100 分)
二叉树结点间的一种加权距离定义为：上行方向的变数×3 +下行方向的边数×2 。上行方向是指由结点向根的方向，下行方向是指与由根向叶结点方向。 给定一棵二叉树T及两个结点u和v，试求u到v的加权距离。
输入格式:
第1行，1个整数N，表示二叉树的结点数，(1≤N≤100000)。
随后若干行，每行两个整数a和b，用空格分隔，表示结点a到结点b有一条边，a、b是结点的编号，1≤a、b≤N；根结点编号为1，边从根向叶结点方向。
最后1行，两个整数u和v，用空格分隔，表示所查询的两个结点的编号，1≤u、v≤N。
输出格式:
1行,1个整数，表示查询的加权距离。
输入样例:
在这里给出一组输入。例如：
5
1 2
2 3
1 4
4 5
3 4
输出样例: 在这里给出相应的输出。例如：
8
思路：lca问题，lca问题的解决方法有很多，适应树，图的方法有各自的特色，本题由于是二叉树，因此题目简化，两者lca在树的寻根过程中，不会出现多个pre结点，因此采用lca最简单的方法：先DFS遍历求取深度，然后根据选取两点的深度来进行：当两者深度不一样时，需要让深度大的一点向上寻根，直到两者深度一样，然后开始同时向上寻找father结点，直到father节点相同，输出答案。
代码如下：
//#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
vector<int>mp[100001];
int visited[100001];
int father[100001];
int num = 0;
void DFS(int p, int top)
{
if (visited[p] == 0)
{
visited[p] = top;//DFS过程中标记每一点的数组
for (int i = 0; i < mp[p].size(); i++)
{
DFS(mp[p][i], top + 1);
}
}
}
int main()
{
int m;
scanf("%d", &m);
for (int i = 1; i <= m - 1; i++)
{
int from, to;
scanf("%d%d", &from, &to);
mp[from].push_back(to);
father[to] = from;
}
DFS(1, 0);
int a, b;
scanf("%d%d", &a, &b);
int a1 = a; int b1 = b;
if (visited[b1] > visited[a1])
{
int r = a1;
a1 = b1;
b1 = r;
}
while (visited[a1] > visited[b1])
{
a1 = father[a1];
}
while (a1 != b1)
{
a1 = father[a1];
b1 = father[b1];
}
printf("%d", (visited[b] - visited[a1]) * 2+ (visited[a] - visited[a1]) * 3);
return 0;
}
反思：题目理解有问题，当时看到的时候，以为直接到达1(根节点)，还混了80分(就离谱)。
7-3 修轻轨 (100 分)
长春市有n个交通枢纽，计划在1号枢纽到n号枢纽之间修建一条轻轨。轻轨由多段隧道组成，候选隧道有m段。每段候选隧道只能由一个公司施工，施工天数对各家公司一致。有n家施工公司，每家公司同时最多只能修建一条候选隧道。所有公司可以同时开始施工。请评估：修建这条轻轨最少要多少天。。
输入格式:
第1行，两个整数n和m，用空格分隔，分别表示交通枢纽的数量和候选隧道的数量，1 ≤ n ≤ 100000，1 ≤ m ≤ 200000。
第2行到第m+1行，每行三个整数a、b、c，用空格分隔，表示枢纽a和枢纽b之间可以修建一条双向隧道，施工时间为c天，1 ≤ a, b ≤ n，1 ≤ c ≤ 1000000。
输出格式:
输出一行，包含一个整数，表示最少施工天数。
输入样例:
在这里给出一组输入。例如：
6 6
1 2 4
2 3 4
3 6 7
1 4 2
4 5 5
5 6 6
输出样例: 在这里给出相应的输出。例如：
6
思路：本题为最小生成树问题，但是不需要生成完全最小生成树，只需要在1点和n点连通时退出加边行为即可，由于最小生成树的算法每一步加完边后，最后一条边为最大值，因此只需要输出最后一条边的权值即为所求。推荐使用kruskal算法，但是注意并查集的优化，否则可能出现超时现象。
注意：本题会出现非简单图的情况，即存在环形弧，比如1个城市，1条边，注意处理该类情况。
代码如下：
//#pragma warning(disable:4996)
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef struct Edge
{
int from;
int to;
int value;
bool operator < (const struct Edge &a)const
{
return value < a.value;
}
}edge;
edge Vertex[200005];
int father[200005];
int m;
int find1(int v)
{
if (father[v] == v)
return v;
return find1(father[v]);
}
void Union(int x, int y)
{
int fx = find1(x);
int fy = find1(y);
if (fx != fy)
{
father[fy] = fx;
father[y] = fx;
}
}
int main()
{
int n;
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; i++)
{
scanf("%d%d%d", &Vertex[i].from,&Vertex[i].to,&Vertex[i].value);
}
for (int i = 1; i <= m; i++)
{
father[i] = i;
}
sort(Vertex + 1, Vertex + n + 1);
//kruskal核心算法
for (int i = 1; i <= n; i++)
{
int from = Vertex[i].from;
int to = Vertex[i].to;
if (find1(from) != find1(to))
{
Union(from, to);
if(find1(1) == find1(m))
{
printf("%d", Vertex[i].value);
return 0;
}
}
}
if(find1(1) == find1(m))
{
printf("%d", Vertex[m].value);
return 0;
}//环弧的判断，当然也可以在循环退出后统一输出。
return 0;
}
反思：模板格式不对，在考试的时候，将to值和value值传进来时传反导致出错，还对了10分就离谱。
7-4 数据结构设计I (100 分)
小唐正在学习数据结构。他尝试应用数据结构理论处理数据。最近，他接到一个任务，要求维护一个动态数据表，并支持如下操作：
插入操作（I）：从表的一端插入一个整数。
删除操作（D）：从表的另一端删除一个整数。
取反操作（R）：把当前表中的所有整数都变成相反数。
取最大值操作（M）：取当前表中的最大值。
如何高效实现这个动态数据结构呢？
输入格式:
第1行，包含1个整数M，代表操作的个数， 2≤M≤1000000。
第2到M+1行，每行包含1个操作。每个操作以一个字符开头，可以是I、D、R、M。如果是I操作，格式如下：I x, x代表插入的整数，-10000000≤x≤10000000。
输出格式:
若干行，每行1个整数，对应M操作的返回值。如果M和D操作时队列为空，忽略对应操作。
输入样例:
在这里给出一组输入。例如：
6
I 6
R
I 2
M
D
M
输出样例:
在这里给出相应的输出。例如：
2
2
做法：注意mutliset使用和数组标记。
//#pragma warning(disable:4996)
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
int a[10000001];
multiset<int>M;
deque<int>Q;
int flag = 1;
int main()
{
int n;
scanf("%d\n", &n);
for (int i = 1; i <= n; i++)
{
char ch;
scanf("%c", &ch);
switch (ch)
{
case 'I':
{
int num;
scanf("%d", &num);
Q.push_back(num*flag);
M.insert(num*flag);
break;
}
case 'D':
{
if (Q.size() != 0)
{
int a = Q.front();
multiset<int>::iterator it = M.find(a);
M.erase(it);
Q.pop_front();//不能直接erase,否则会全部erase
}
break;
}
case 'R':
{
if (flag == 1)flag = -1;
else flag = 1;
break;
}
case 'M':
{
if (flag == 1)
{
if (Q.size() != 0)
{
multiset<int>::iterator it = M.end();
printf("%d\n", *(--it));
}
}
else
{
if (Q.size() != 0)
printf("%d\n", *M.begin()*flag);
}
break;
}
}
getchar();
}
return 0;
}
注意：multiset的erase的使用方法，本体具体操作代码已经标注。