数据结构-第六次上机实验课-解题报告
- 7-1 高精度数加法 (100 分)
- 题目
- 思路
- 参考代码
- 7-2 二叉树加权距离 (100 分)
- 题目
- 思路
- 参考代码
- 7-3 修轻轨 (100 分)
- 题目
- 思路
- 参考代码
- 7-4 数据结构设计I (100 分)
- 题目
- 思路
- 参考代码
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
思路
高精度加法,在c++的实验课中已经写过1000!的高精度乘法,不难想到,这题的思路也是运用数组进行模拟加法。
模拟加法操作如下
for(int i=0; i<maxn; i++) {
ans[i]=ans[i]+num1[i]+num2[i];
ans[i+1]=ans[i]/10;//进位
ans[i]%=10;//保留余数
}
其次,由于该模拟加法只能实现2个大数的加减,而题目要求n个,故需要用while(n–)的方式,将每次相加的结果赋值给下一次的第一个数,进行重复操作。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define maxn 200
int main() {
int N;
cin>>N;
char s1[maxn],s2[maxn];
cin>>s1;
int num1[maxn];int num2[maxn];
for(int i=0;i<maxn;i++)
{
num1[i]=0;
num2[i]=0;
}
// 转换过程
int len1=strlen(s1);
for(int i=0; i<len1; i++) {
num1[i]=s1[len1-1-i]-'0';
}
if(N==1){
for(int i=len1-1;i>=0;i--)
cout<<num1[i];
}
if(N==1) return 0;
N--;
int ans[maxn];
for(int i=0; i<maxn; i++) ans[i]=0;
while(N--) {
cin>>s2;
int len2=strlen(s2);
for(int i=0; i<len2; i++) {
num2[i]=s2[len2-1-i]-'0';
}
for(int i=0; i<maxn; i++) ans[i]=0;
for(int i=0; i<maxn; i++) {
ans[i]=ans[i]+num1[i]+num2[i];
ans[i+1]=ans[i]/10;//进位
ans[i]%=10;//保留余数
}
for(int i=0; i<maxn; i++) {
num1[i]=ans[i];
num2[i]=0;
}
}
int flag=0;
for(int i=maxn-10; i>=0; i--) {
if(ans[i]!=0||i==0) flag=1;
if(flag) cout<<ans[i];
}
cout<<endl;
}
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点。若v为u的祖先,则达到v即可停止。
题目意思大概是这么说,但操作时,从v开始计数更为方便。
代码思路:
1.因为只用到双亲节点,无须寻找子节点,故采用father连接的数组表示形式存储该树。
2.选定u点进行上寻,边走边标记,直到根节点。
3.以v点开始上寻,直到达到有标记的点,则已找到公共双亲结点。
(代码中vis数组的值并非0和1这么简单,可以用一个数表示已访问的同时,表示对应高度,方便输出上行长度)
4.计算第2步的长度(减去基准的i=10)3,计算第3步的长度2,相加即是所求结果
参考代码
#include<bits/stdc++.h>
using namespace std;
int father[100001];
int vis[100001];//已访问
int main()
{
// std::ios::sync_with_stdio(false);
// cin.tie(0);
int n;cin>>n;
int u,v;
for(int i=1;i<=n-1;i++)
{
cin>>u>>v;
father[v]=u;//v的父亲是u
}
cin>>u>>v;
for(int i=10;;i++)//以高度10位基准
{
if(father[u]==0)
{
vis[u]=i;
break;//标记根节点并退出
}
vis[u]=i;//除了标记访问外,标记高度差
u=father[u];//向上
}
int sum=0;
while(vis[v]==0)//直到有标记 为止
{
sum=sum+2;
v=father[v];
}
sum=sum+vis[v]*3;
cout<<sum-30<<endl;
}
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
思路
借鉴同学的思路之后,我才发现,其实是一道克鲁斯卡尔求最小生成树的题,拿第五次实验的第3小题(修电站)稍微做修改就能过了。
但题目难,难就难在怎么把形象的表达抽象化为构建最小生成树,并求最小生成树中最大边,这个问题。反思一下,这也正是学完数据结构后,我最欠缺的东西——构建模型的思想。手中有那么多方法,却不知道题目要干啥,该用什么方法去解决都不知道,这是最致命的。
进入正题,思路其实不难,上面已经提到,就是求最小生成树中的最大边的问题。题目中说“同时施工”且“最少需要几天”,脑筋一转,根据木桶效应,可以知道耗时最长的,就是施工的结束时间。而克鲁斯卡尔算法,以不递减的顺序进行加边,满足了最后一次操作,是所有情况中最小的情况。
所以,我们选用Kruskal+并查集+有序边表的方式实现
参考代码
由于代码其实就是Kruskal+并查集+有序边表的方式实现,这里就不做赘述。
#include <bits/stdc++.h>
using namespace std;
typedef struct node
{
int u,v;
int cost;
}edge;
edge e[200010];
int father[100010];
//并查集 find union
int FIND(int v)
{
if(father[v]==v) return v;
return father[v]=FIND(father[v]);
}
int UNION(int x,int y)
{
int fx=FIND(x);
int fy=FIND(y);
if(fx!=fy)
{
father[fy]=fx;
return 1;//返回1表明发生合并
}
}
int main()
{
int E_num,P_num;
cin>>P_num>>E_num;
for(int i=1;i<=E_num;i++)
{
int u,v,cost;
cin>>u>>v>>cost;
e[i].u=u;
e[i].v=v;
e[i].cost=cost;
}
//Kruskal算法
sort(e+1,e+E_num+1,[=](edge &e1,edge &e2){
return e1.cost<e2.cost;
});
for(int i=0;i<=P_num;i++) father[i]=i;//并查集初始化
for(int i=1,k=0;k!=P_num;i++)//k等于边数时结束
{
if(FIND(e[i].u)!=FIND(e[i].v))//不成环
{
UNION(e[i].u,e[i].v) ;
}
if(FIND(P_num)==FIND(1))//已连通则输出
{
cout<<e[i].cost<<endl;
exit(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
思路
思路其实不难,将四种操作封装成函数,循环调用即可。但每次取反,若对容器中元素均*(-1)的话,时间效率极其低下。再如果,每次求最大值进行一次sort,效率将更低下。再如果,你不知道可以使用std::ios::sync_with_stdio(false); cin.tie(0);
进行输入输出的优化,时间将极其极其低下。巧妙的是 ,三个错误我都犯了。
那下面就讲讲如何优化前两步操作:
1.对于R操作,每次取反大可不必,我们只需引入一个flag标记正负,对接下来输入的值进行处理,再对输出做反向操作的手脚,也就等价于将容器内元素进行取反了。
2.对于M操作,刚开始并没有想过使用multiset,故采用sort,每次M操作都得在辅助空间内进行排序,极其呆滞。但实际上,只需一边对队列进行push一边对multiset进行insert即可。但这样操作会有一点小毛病,就是在D操作时,同步删除集合中元素有些小坑。erase函数,如果erase一个值,则会删除所有的值,所有不能se.erase(*it);
而得是se.erase(it);
删除迭代器指向的那一个位置才行。
代码方面,使用queue存储和multiset辅助求最大,并进行两步优化后即可,在此不作赘述。
参考代码
#include<bits/stdc++.h>
using namespace std;
queue<int>dq;
multiset<int>se;
int flag=1;//1为正,0为负
inline void func(char s)
{
if(s=='D'&&dq.empty()!=1)
{
multiset<int>::iterator it=se.find(dq.front());
se.erase(it);
dq.pop();
}
else if(s=='R')
{
if(flag==1) flag=0;
else flag=1;
}
else if(s=='M'&&dq.empty()!=1)
{
if(flag==1)
cout<<*se.rbegin()<<"\n";
else cout<<(*se.begin())*(-1)<<"\n";
}
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
int m;cin>>m;
char s;int x;
for(int i=1;i<=m;i++)
{
cin>>s;
if(s=='I')
{
cin>>x;
if(flag==1)
{
dq.push(x);
se.insert(x);
}
else
{
dq.push(-x);
se.insert(-x);
}
}
else func(s);
}
}