- 1AWS 使用CLI获取角色临时凭证_awscli
- 2安卓App开发 篇二：Android UI和布局
- 3通过cmd命令安装、卸载、启动和停止Windows Service（InstallUtil.exe）_cmd启动一个服务windowsservice
- 4netfilter/iptables配置入门_alpine not starting iptables. first create some ru
- 5「 CISSP学习笔记 」08.安全运营_cissp scom
- 6第二章.线性回归以及非线性回归—LASSO算法_非线性lassio回归代码
- 7python应用系列教程——python操作office办公软件word_python 實現在線編輯器office
- 8Pycharm使用指南_pycharm吉林大学
- 9java精华（4）
- 10【Java练习】给定一个有序整型数组, 实现二分查找_给定一组有序序列,用随机化二分查找的方法查找某元素x。 提示:随机化二分查找方法
数据结构-第六次上机实验-解题报告_数据结构第6版上机实验题
赞
踩
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;//保留余数
}
- 1
- 2
- 3
- 4
- 5
其次，由于该模拟加法只能实现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; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
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; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
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); } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
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); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
