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

作者 谷方明

单位 吉林大学

代码长度限制 16 KB

时间限制 100 ms

内存限制 1 MB

解法一：

思路：

对于加法，每次进位只会向前进一位，且进位值必定为1（9+9是最大的情况），则可以使用string来保存数字，一个int类型来维护进位，从后往前依次累加；有同学提到使用数组时反过来存，由于我是使用string，字符串拼接写起来很方便，如果算到最前面有进位再拼接一个‘1’在最前面就可以了。这样做确实会耗时间一点，但是在这只做一次，完全可以忽略；老师之前好像提过string的底层是链表，不过还是需要警惕的，我之前写Huffman编码时在循环内做这种类似的事情直接导致效率低到爆炸，猜测string也有使用数组做底层容器的情况。

细节：

1.我这里使用了pop_back()其实完全没必要，追求效率直接用下标就行了。

2.我这里面为了避免讨论，若一个序列已尽，另一个还没有，直接屏蔽掉差异，将已尽序列每次取新值都取0。

代码实现：

#include <iostream>
#include <vector>
#include <string>
using namespace std;
string add(string a, string b) {
	vector<char> cup;//保存答案
	int cuppp = 0;//保存对应位之和
	int jinwei = 0;//维护进位
	char cupa = '0', cupb = '0';//对应从a，b中取的末尾数
	while (!a.empty() || !b.empty()) {//只要不都空
		if (!a.empty()) {//非空取最后
			cupa = a.back();
			a.pop_back();
		}
		else {//空则置0，简化代码逻辑
			cupa = '0';
		}
		if (!b.empty()) {
			cupb = b.back();
			b.pop_back();
		}
		else {
			cupb = '0';
		}
		cuppp = cupa + cupb - 2 * '0' + jinwei;//计算对应位之和
		if (cuppp < 10) {
			cup.push_back(cuppp % 10 + '0');
			jinwei = 0;
		}
		else {
			cup.push_back(cuppp % 10 + '0');
			jinwei = 1;
		}
	}
	if (jinwei == 1) {//算完讨论是否在原最高位还要进位
		cup.push_back('1');
	}
	string ans(cup.rbegin(), cup.rend());
	return ans;
}
int main() {
	int n = 0;
	cin >> n;
	string ans="0",cup;
	for (int i = 0; i < n; i++) {
		cin >> cup;
		ans = add(ans, cup);
	}
	cout << ans;
}

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

作者 谷方明

单位 吉林大学

代码长度限制 16 KB

时间限制 100 ms

内存限制 10 MB

解法一：

解决本题关键有两点：

1.如何建树。

2.如何找加权距离。

对于第一点，这次机考之前之前做图论做得比较多，二叉树本质上可以看作特殊的有向图，我这里为了方便直接使用邻接表来存了。(当然，经过同学提醒，这里之后甚至就可以直接使用图论算法求解)

对于第二点，要考虑两种情况 1.在一条直线上，2.不在同一条线上(共享同一个公共祖先)。

在一条直线上很好解决，那么就要寻找最近的公共祖先了。

首先使用一次dfs求出每个节点的深度。

求最近公共祖先：这里我使用的是dfs，整体思路是每次站在一个结点，带着两个要求公共祖先的结点的数据域，往左右子树分别探查，如果探查到了其中一个就返回true，当这一层递归中的两个dfs均为true时证明现在这个结点是给定的两个结点的最近公共祖先。那么记录下它的深度。

之后计算，如果dfs找到了祖先的深度，分别计算两个结点到祖先的加权路径再求和即可；如果没有找到，说明二者在一条直线上，那么直接计算即可。

细节：

1.为了避免找到最近公共祖先之后dfs还在进行，设置一个全局标记域，找到了置为true，每次进入递归函数时，只要该标志为true则返回。这样可大大减少无谓的计算。

2.由于本题输入没有设置结束标志，我采用判断输入结束的方法:若最后输入的两个点任意一个已出现过，则结束输入。

思路：

代码实现：

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
vector<vector<int>> tu;
int* depth;
int* read;
int compa = 0;
bool flag = 0;
void dfs(int u,int before_depth) {//求深度
	depth[u] = before_depth + 1;
	for (int i = 0; i < tu[u].size(); i++) {
		dfs(tu[u][i], before_depth + 1);
	}
}
bool dfs2(int now,int u, int v) {//最近公共祖先
	if (flag) {//找到了，所有递归作废
		return 0;
	}
	if (now == u || now == v) {//找到其中一个，带回true
		return 1;
	}
	bool dep1 = 0,dep2 = 0;
	if (tu[now].size() >= 1) { dep1 = dfs2(tu[now][0], u, v); }//往左走
	if (tu[now].size() == 2) { dep2=dfs2(tu[now][1], u, v); }//往右走
	if (dep1 && dep2) {
		compa = now;//同时为真，为最近公共祖先全局变量赋值
		flag = 1;
	}
	if (dep1||dep2) {//找到一个，逐级带回结果
		return 1;
	}

	return 0;

}
int lenth(int s, int e) {//计算在一条线上的两个结点的加权距离
	int ans = depth[s] - depth[e];
	if (ans > 0) {
		ans = ans * 3;
	}
	else if (ans < 0) {
		ans = -ans * 2;
	}
	return ans;
}
int main() {
	int n = 0, u = 0, v = 0;
	scanf("%d", &n);
	if (n == 1) {
		printf("0");
		return 0;
	}
	tu = vector<vector<int>>(n + 1);
	depth = new int[n+1];
	read = new int[n + 1];
	memset(depth, 0, sizeof(int) * (n + 1));
	memset(read, 0, sizeof(int) * (n + 1));
	while (1) {
		scanf("%d%d", &u, &v);
		if (read[v]) {
			break;
		}
		read[v] = 1;
		tu[u].push_back(v);
	}
	int s = u, e = v, ans = 0;
	dfs(1, 0);
	dfs2(1, s, e);
	if (compa) {//如果找到公共祖先
		ans = lenth(s, compa) + lenth(compa, e);
	}
	else {//没找到则在一条直线上
		ans = lenth(s, e);
	}
	printf("%d", ans);
}

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

作者 谷方明

单位 吉林大学

代码长度限制 16 KB

时间限制 500 ms

内存限制 10 MB

解法一：

思路：

由于涉及到两点：

1.连通两个点。

2.使连通过程权值最大的边取得它可以取到的最小权值。

于是想到了最小生成树。

由于这里输入给的是边，使用Kruskal更为方便，直接开一个边数组，排序，然后再配合并查集执行Kruskal，由Kruskal的性质，当连通的那一刻，也就是最后加入的那一条边，就是权值最大的边，其权值就是本题答案。

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_NUM 100001
int N = 0, M = 0;
class UniteFindSet//并查集类
{
public:
	UniteFindSet(int num);
	void join(int root1, int root2);
	int find(int root);
	bool isConnect(int root1, int root2);


private:
	int par[MAX_NUM];      
};



UniteFindSet::UniteFindSet(int num)
{
	for (int i = 0; i < num; i++)
		par[i] = i;


}

int UniteFindSet::find(int root)
{
	int tmp = 0;
	int son = root;
	while (root != par[root])
	{
		root = par[root];
	}
	while (son != root)  
	{
		tmp = par[son];
		par[son] = root;
		son = tmp;
	}
	return root;
}

void UniteFindSet::join(int root1, int root2)
{
	int x = find(root1);
	int y = find(root2);
	if (x == y)
		return;
	else
		par[x] = y;
}

bool UniteFindSet::isConnect(int root1, int root2)
{
	return find(root1) == find(root2);
}

struct Node
{
	int start;
	int end;
	int length;
};
bool compare(Node a, Node b)
{
	return a.length < b.length;
}
void Kruskal(vector<Node>& arr)
{
	UniteFindSet bcj(N + 1);//新建并查集

	sort(arr.begin(), arr.end(), compare);//边排序
	int weight = 0, i = 0;
	int cup = bcj.find(1);
	cup = bcj.find(N);
	while (bcj.find(1) != bcj.find(N))//两点连通为止
	{
		if (bcj.find(arr[i].start) != bcj.find(arr[i].end))//避免有环
		{
			weight = arr[i].length;//每次保存weight，由于Kruskal的性质，结束时的weight就是答案
			bcj.join(arr[i].start, arr[i].end);//维护并查集
		}
		i++;
	}
	cout << weight;
}

int main() {
	scanf("%d%d", &N, &M);
	vector<Node> edge(M);
	int u = 0, v = 0, c = 0;
	for (int i = 0; i < M; i++) {
		scanf("%d%d%d", &edge[i].start, &edge[i].end, &edge[i].length);//边存进数组
	}
	Kruskal(edge);
}

7-4 数据结构设计I (100 分)

小唐正在学习数据结构。他尝试应用数据结构理论处理数据。最近，他接到一个任务，要求维护一个动态数据表，并支持如下操作：

1. 插入操作（I）：从表的一端插入一个整数。

2. 删除操作（D）：从表的另一端删除一个整数。

3. 取反操作（R）：把当前表中的所有整数都变成相反数。

4. 取最大值操作（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

作者 谷方明

单位 吉林大学

代码长度限制 16 KB

时间限制 500 ms

内存限制 50 MB

解法一：

思路：

解决本题的关键：

1.如何高效进行取反操作。

2.如何高效维护最大最小值。

3.如何进行一端插入，另一端删除。

对于第一点，观察到任意一个数在数据结构中最多只有两种状态:1.已取反。2.未取反。又由于插入和取反是动态进行的，因此整个数据结构的数据并不总全是同一种状态，但必定处于其中一种，因此我设置了两个全局布尔变量，两个变量的状态永远相反，为true表示已取反，false表示未取反。再为每一个数据结点增加一个布尔值指针，每次插入一个数据时将该指针指向当前时刻处于false状态的布尔值。这样每次执行取反操作只需要互换两个布尔变量的值即可。

对于第二点，每次插入数据时，分别和最大最小值进行比较，动态更新。重点：删除数据时有可能已将当前的最大或最小值删除，出现这种情况就必须再次寻找最大或最小值(当然最大最小值是一个数据的情况下就必须同时发生，正是少考虑这种情况导致我一直过不了最后的点)，为此我为每个数据结点又增加了一个mark域，增设一个全局变量counter，在数据结点的构造函数中将当前的counter赋值给mark，再对counter进行+1，这样确保每个结点有唯一的标识，在保存最大值最小值时将mark值也保存，这样每次删除的时候就判断 1.最大最小值的mark是否都等于当前要删除的数据的mark 2.最大值的mark是否等于当前要删除的数据的mark 3.最小值的mark是否等于当前要删除的数据的mark。一旦等于就调用findmax findmin函数更新对应的最大值最小值。

更新最大值最小值：

我这里直接采用了暴力的遍历更新，但每次会先查看结点当中的布尔变量来确定当前结点的符号状态，从而保证能正确得到每一个结点的正负号，返回时将mark和找到的最值一起带回。

对于第三点，可以直接使用deque，很方便。

细节:

1.其实唯一标识一个结点用地址就可以了，只是因为我是半路改的，已经用了deque，线性stl元素的地址会动态变化，所以就只能加一个mark域。

2.题目要求：队列为空的操作要忽略。

代码实现：

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
#define INT_MAX 1<<29
#define INT_MIN -(1<<29)
FILE* p = NULL;
using namespace std;
int mark1 = 0;
bool flag1 = 0, flag2 = 1;
struct ans {//存最大最小值的结构体，其实没必要，跟数据用一个结构体就可以了
	int shu;
	int mark;
	ans(int shu):shu(shu),mark(0){}
};
struct shuzi {//存数据的结构体
	int shu;
	bool* flag;
	int mark;
	shuzi(int shu) :shu(shu), flag(0), mark(mark1) { mark1++; }
};
deque<shuzi> dl;
int findmin(int* dizhi) {//dizhi带回mark数据
	int min = INT_MAX;
	int cup = 0;
	for (int i = 0; i < dl.size(); i++) {
		cup = dl[i].shu;
		if (*dl[i].flag == 1) {//按照标志的意志决定当前查看数据的符号
			cup = -cup;
		}
		if (cup < min) {
			min = cup;
			*dizhi = dl[i].mark;
		}
	}
	return min;
}
int findmax(int* dizhi) {
	int max = INT_MIN;
	int cup = 0;
	for (int i = 0; i < dl.size(); i++) {
		cup = dl[i].shu;
		if (*dl[i].flag == 1) {
			cup = -cup;
		}
		if (cup > max) {
			max = cup;
			*dizhi = dl[i].mark;
		}
	}
	return max;
}
ans maxx(INT_MIN),minn(INT_MAX);
inline void I(int num) {
	dl.push_front(num);
	if (!flag1) {//flag指针指向当前为false的bool变量，标识未取反
		dl.front().flag = &flag1;
	}
	else {
		dl.front().flag = &flag2;
	}
	if (num > maxx.shu) {//插入时动态更新最大最小值
		maxx.shu = num;
		maxx.mark = dl.front().mark;
	}
	if (num < minn.shu) {
		minn.shu = num;
		minn.mark = dl.front().mark;
	}
}
inline void R() {//取反
	if (dl.empty()) {
		return;
	}
	bool cupflag = flag1;
	flag1 = flag2;//更新标志
	flag2 = cupflag;
	ans cup = 0;
	cup = minn;
	minn = maxx;//当前最大最小值互换
	maxx = cup;
	maxx.shu = -maxx.shu;
	minn.shu = -minn.shu;

}
inline void D() {
	if (dl.empty()) {
		return;
	}
	int* dizhi = new int;
	if (dl.back().mark == maxx.mark && dl.back().mark == minn.mark) {//如果最大最小值对应结点同时被删除
		dl.pop_back();
		maxx = findmax(dizhi);
		maxx.mark = *dizhi;
		minn = findmin(dizhi);
		minn.mark = *dizhi;
		delete dizhi;
		return;
		}
		else if (dl.back().mark == maxx.mark) {//分别讨论
			dl.pop_back();
			maxx = findmax(dizhi);
			maxx.mark = *dizhi;
			delete dizhi;
			return;
		}
		else if (dl.back().mark == minn.mark) {
				dl.pop_back();
				minn = findmin(dizhi);
				minn.mark = *dizhi;
				delete dizhi;
				return;
		}
		delete dizhi;//释放堆内存
	dl.pop_back();
}
inline void M() {
	ios::sync_with_stdio(false);
	if (dl.empty()) {
		return;
	}
}

int main() {
	//fopen_s(&p,"out.txt", "w");
	ios::sync_with_stdio(false);//为了方便字符串和数字输入混用，使用cin，但是要加速一下，不加速会爆时间
	int n = 0;
	cin >> n;
	char opt = '0';
	int num = 0;
	for (int i = 0; i < n; i++) {
		cin >> opt;
		if (opt == 'I') {
			cin >> num;
			I(num);
		}
		else if (opt == 'R') {
			R();
		}
		else if (opt == 'M') {
			M();
		}
		else if (opt == 'D') {
			D();
		}
	}
}

总结：

1.综合的题目还是比较有趣的。

2.体会到了数据结构在根据实际的改编和应用。