目录
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
思路：
高精度加法这道题目，我觉得要注意的地方就是在将字符数组转成整形后要逆序存放，每次读取一个字符串，要保证数组是干净的（因为空间限制，我们无法读入N个字符串，就开N个数组，实不相瞒，我一开始就是这样的），便于从低位到高位的进位，因为两数相加，得到的和可能要增加一位，如果正着存放从高位到低位，但是是从最低位进行计算，会在空间的运用处理上很别扭。
上代码，写的很丑，此处代码没有封装类，原谅我的能力，之后我会用类封装实现的。
#include<stdio.h>
#include<string.h>
int sum[20000];
int main(){
int N,r1,r2;
int a[105]={0};
char A[105];
scanf("%d",&N);
getchar();
scanf("%s",A);
r1=strlen(A);
int j=1;
for(int i=r1-1;i>=0;i--){
sum[j]=(int)A[i]-'0';
j++;
}
int ant=0,ent; //进位
for(int k=2;k<=N;k++)
{
char s[105];
scanf("%s",s);
r2=strlen(s);
memset(a,0,sizeof(a));
for(int i=r2-1,j=1;i>=0;i--,j++){
a[j]=(int)s[i]-'0';
}
if(r1<r2){
r1=r2;
}
ant=0;
for(int i=1;i<=r1;i++){
ent=a[i]+sum[i]+ant;
if(ent>9){
ant=ent/10;
sum[i]=ent%10;
}
else{
ant=0;
sum[i]=ent;
}
}
while(ant!=0){
r1++;
sum[r1]=ant%10;
ant=ant/10;
}
}
for(int i=r1;i>=1;i--){
printf("%d",sum[i]);
}
return 0;
} 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
思路：
这道题，一开始没有明白题的意思，后来看了李同学的图解还有杨同学给我的讲解才明白了题的意思 。
这道题考察的是最近公共祖先。
最近公共祖先的寻找，应该是从u点开始一直向上直到找到根结点，并给每个被访问过的结点做标记，并记录每个结点高度，然后从v点开始向上查找，直到遇到第一个被访问过的结点，此结点即为最近公共祖先。
计算权值过程中，上行边数就是从u到最近公共祖先经历的边数，下行边就是最近公共祖先到u经历的边数。
代码如下：
#include<iostream>
using namespace std;
const int maxsize=100005;
int father[maxsize]={0};
int visited[maxsize]={0};
int main(){
int N;
int u,v;
int distance=0;
scanf("%d",&N);
for(int i=1;i<=N-1;i++){//树n个节点有n-1条边
int a,b;
scanf("%d %d",&a,&b);
father[b]=a;
}
scanf("%d %d",&u,&v);
//根节点父亲为0
visited[u]=1;
int ceng=1;
while(father[u]){ //上行
visited[u]=ceng++;//被访问标记 ，顺便记录高度
u=father[u];
}
visited[1]=ceng;
while(!visited[v]){ //下行，逆着上去找最近公共祖先
distance+=2;
v=father[v];
}
printf("%d\n",distance+visited[v]*3-3);//最近公共祖先可不一定是根
return 0;
}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是否连通，如果连通，跳出循环 。
代码如下：
#include<iostream>
#include<algorithm>
#define maxsize 200005
using namespace std;
struct TE{ //最小支撑树边的集合
int head;//边的始点
int tail;//边的终点
int cost;//边的开销
}T[maxsize];
int father[maxsize];
void make_set(int x){
father[x]=0;
}
int find(int x){
if(father[x]<=0) return x;
int fx=find(father[x]);
father[x]=fx;
return fx;
}
void Union(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy) return;
if(father[fx]<father[fy]) father[fy]=fx;
else{
if(father[fx]==father[fy]) father[fy]--;
father[fx]=fy;
}
}
bool cmp(struct TE a,struct TE b){
return a.cost<b.cost;
}
int Kruskal_method(int m,int n){
int i,j,v,u;
int result;
sort(T+1,T+m+1,cmp);
for(i=1;i<=m;i++) make_set(i);
for(i=1,j=1;i<=m;i++){
int u=T[i].head,v=T[i].tail;
if(find(u)!=find(v)){
Union(u,v);
result=T[i].cost;
}
if(find(1)==find(n))return result;
}
}
int main(){
int n,m;
scanf("%d %d",&n,&m);
if(n==1){
printf("0\n");
return 0;
}
for(int i=1;i<=m;i++){
scanf("%d %d %d",&T[i].head,&T[i].tail,&T[i].cost);
}
int result=Kruskal_method(m,n);
printf("%d\n",result);
return 0;
}
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
思路：
这道题我写了很长时间，用了最暴力的方法，寻找最大值和把所有数反转成相反数都是暴力方法，我想过设标记进行状态反转，但是由于太菜，没有想到接下来应该怎么办。
暴力代码如下：（他过了两个测试点，得了四十分）
#include<bits/stdc++.h>
#include<deque>
using namespace std;
deque <int> Q1,Q2;
const int INF=1e8+5;
int maxn=-INF;
int judge=1;
void Oper(char x){
switch(x){
case 'I':{
int y;
scanf("%d",&y);
if(y>maxn)maxn=y;
if(judge==1)
{
Q1.push_front(y);
Q2.push_front(-y);
}
else
{
Q1.push_front(-y);
Q2.push_front(y);
}
break;
}
case 'D':{
if(!Q1.empty()){
if(judge==1)
{
deque <int> ::iterator it;
it=Q1.end()-1;
if((*it)==maxn)
{
Q1.pop_back();
Q2.pop_back();
maxn=-INF;
for(it=Q1.begin();it!=Q1.end();it++){
if(maxn<(*it)){
maxn=(*it);
}
}
}
}
else
{
deque <int> ::iterator it;
it=Q2.end()-1;
if((*it)==maxn)
{
Q1.pop_back();
Q2.pop_back();
maxn=-INF;
for(it=Q2.begin();it!=Q2.end();it++){
if(maxn<(*it)){
maxn=(*it);
}
}
}
}
}
else
{
maxn=-INF;
judge=1;
}
break;
}
case 'R':{
if(!Q1.empty()){
if(judge==1){
judge=0;
deque <int> ::iterator it;
maxn=-INF;
for(it=Q2.begin();it!=Q2.end();it++){
if(maxn<(*it)){
maxn=(*it);
}
}
}
else{
judge=1;
deque <int> ::iterator it;
maxn=-INF;
for(it=Q1.begin();it!=Q1.end();it++){
if(maxn<(*it)){
maxn=(*it);
}
}
}
}
else{
maxn=-INF;
judge=1;
}
// printf("*%d*",maxn);
break;
}
case 'M':{
if(!Q1.empty()){
printf("%d\n",maxn);
}
else{
maxn=-INF;
judge=1;
}
break;
}
}
}
int main(){
int M;
char a[2];
scanf("%d",&M);
getchar();
for(int i=1;i<=M;i++){
scanf("%s",a);
Oper(a[0]);
}
return 0;
}改正的方法是受到大佬们的解题报告的指导，
用单调队列获得最大值，设置一个judge来表示状态。维护两个单调队列，一个单调递增，一个单调递减，例如：当judge=1，将读入的数直接入队，当judge=0，将读入的数的相反数入队，访问时，当状态为1时，输出单调递减队列的队头；当状态为0，输出单调递增队列的队头的相反数。
要记住的一点是：一定要记得队列的先进先出性质，如果要删除的元素比最大值小，证明维护的单调队列里面是没有这个数的，无需考虑单调队列里面对他的删除操作。
代码如下：
#include<iostream>
#include<queue>
#include<deque>
using namespace std;
int judge=1;
queue<int> Q;
deque<pair<int,int> > M1,M2;
void Oper(char x){
switch(x){
case 'I':{
int y;
scanf("%d",&y);
// printf("<<<<<11111\n");
if(judge==0){
y=y*(-1);
}
Q.push(y);
//维护递减序列
// printf("<<<<<<32222\n");
while(!M1.empty()&&y>M1.back().first){
M1.pop_back();
}
if(M1.empty()||y<M1.back().first){
M1.push_back(make_pair(y,1));
}
else
{
if(y==M1.back().first)
{
M1.back().second++;
}
}
//维护递增序列
while(!M2.empty()&&y<M2.back().first){
M2.pop_back();
}
if(M2.empty()||y>M2.back().first){
M2.push_back(make_pair(y,1));
}
else
{
if(y==M2.back().first)
{
M2.back().second++;
}
}
break;
}
case 'D':{
if(!Q.empty()){
int y=Q.front();
Q.pop();
//在此，一定要记得队列的先进先出性质，如果y比最大值小，证明单调队列里面是没有y的
if(y==M1.front().first){
M1.front().second--;
if(M1.front().second==0){
M1.pop_front();
}
}
if(y==M2.front().first){
M2.front().second--;
if(M2.front().second==0){
M2.pop_front();
}
}
}
else{
break;
}
break;
}
case 'R':{
if(judge==1){
judge=0;
}
else{
judge=1;
}
break;
}
case 'M':{
if(Q.empty())
{
break;
}
else
{
if(judge==1){
printf("%d\n",M1.front().first);
}
else{
printf("%d\n",-(M2.front().first));
}
}
break;
}
}
}
int main(){
int M;
char a[2];
scanf("%d",&M);
getchar();
for(int i=1;i<=M;i++){
scanf("%s",a);
Oper(a[0]);
}
return 0;
}