JLU数据结构第六次上机实验

高精度数加法

Code Size Limit 16 KB
Time Limit 100 ms
Memory Limit 1 MB

题目描述

高精度数是指大大超出了标准数据类型能表示的范围的数，例如10000位整数。很多计算问题的结果都很大，因此，高精度数极其重要。

一般使用一个数组来存储高精度数的所有数位，数组中的每个元素存储该高精度数的1位数字或多位数字。 请尝试计算：N个高精度数的加和。这个任务对于在学习数据结构的你来说应该是小菜一碟。 。

输入格式

第1行，1个整数N，表示高精度整数的个数，(1≤N≤10000)。

第2至N+1行，每行1个高精度整数x, x最多100位。

输出格式

1行,1个高精度整数，表示输入的N个高精度数的加和。

输入样例

在这里给出一组输入。例如：

3
12345678910
12345678910
12345678910

输出样例

在这里给出一组输出。例如：

37037036730

思路

类的封装。封装一个高精度整数类，重载加法等操作。

介绍一下高精度数加法怎么算：求x1,x2的和，先假设没有进位，和的第 i 位就是 （x1i+x2i）对10的余数。再考虑进位问题，计算每位上产生的进位，和的第 i+1 位的进位是（x1i+x2i）对10的模。然后 和 把这个进位加上就行了，如果还是会产生进位，那就递归调用这个算法，直到进位为0。

另外，高精度整数建议逆序储存在数组中，方便操作。

二叉树加权距离

Code Size Limit 16 KB
Time Limit 100 ms
Memory Limit 10 MB

题目描述

二叉树结点间的一种加权距离定义为：上行方向的变数×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,v 分别位于某节点 i 两侧的情况。从u开始向上访问到树根，并标记沿途的结点。然后从v开始向上访问，遇到的第一个标记过的结点就是二者交汇的结点 i ，找到 i 求总路径就很容易了。其他的情况，例如u，v是直系亲属，记得在上述访问过程中讨论以下就行了。

因为只需查询一次，这种方法显得很局限，其实把标记清除，重复使用改算法，即使有多次查询也是很快的。两个字评价这个算法，直接。

代码

#include<iostream>
using namespace std;
#define Max 100005
int f[Max];
int vis[Max];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        f[i]=0;
        vis[i]=0;
    }
    for(int i=0;i<n-1;i++){
        int fth,son;
        scanf(" %d %d",&fth,&son);
        f[son]=fth;
    }

    int asw=0;
    int up3,down2;
    scanf(" %d %d",&up3,&down2);
    if(up3==down2){
        printf("0");
        return 0;
    }
    int f1=f[up3];
    while(f1!=0){
        asw+=3;//printf("%d\n",asw);
        if(f1==down2){
            printf("%d",asw);
            return 0;
        }
        vis[f1]=1;
        f1=f[f1];
    }

    asw=0;
    int f2=f[down2];
    while(!vis[f2]){
        asw+=2;
        if(f2==up3){
            printf("%d",asw);
            return 0;
        }
        f2=f[f2];
    }
    asw+=2;
    vis[f2]--;

    f1=f[up3];
    while(vis[f1]){
        asw+=3;
        f1=f[f1];
    }
    asw+=3;

    printf("%d",asw);
    return 0;
}

修轻轨

Code Size Limit 16 KB
Time Limit 500 ms
Memory Limit 10 MB

题目描述

长春市有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

思路

spfa。跑一遍spfa，区别是dis[i]里存储的不是 1 到 i 的最短距离，而是这条路上最长的那一段路，也就是从 1 修路修到 i 的最短施工天数。这个算法还挺暴力的。内存差一点点就爆了。

代码

#include<iostream>
#include<queue>
#include<vector>
#define Max 100005
#define INF 0x7fffffff
using namespace std;
struct e{
    int to,l;
};
vector<e>map[Max];
void addE(int x1,int x2,int l){
    e e0;
    e0.to=x2;e0.l=l;
    map[x1].push_back(e0);
}
bool vis[Max];
int dis[Max];
void spfa(int x0){
    dis[x0]=0;
    queue<int>q;
    q.push(x0);
    vis[x0]=1;
    while(!q.empty()){
        int now=q.front();
        q.pop();vis[now]=0;
        
        for(int i=0;i<map[now].size();i++){
            int l=dis[now];
            e nextE=map[now][i];
            int to=nextE.to;
            l= l>nextE.l ? l:nextE.l;
            if(l<dis[to]){
                dis[to]=l;
                if(!vis[to])
                q.push(to);
            }
        }
    }
}
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++){
        int x1,x2,l;
        scanf(" %d %d %d",&x1,&x2,&l);
        x1--;x2--;
        addE(x1,x2,l);
        addE(x2,x1,l);
    }
    for(int i=0;i<n;i++){
        vis[i]=0;
        dis[i]=INF;
    }
    spfa(0);
    printf("%d",dis[n-1]);
}

数据结构设计I

Code Size Limit 16 KB
Time Limit 500 ms
Memory Limit 50 MB

题目描述

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

插入操作（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

思路

单调队列

这个思路有点不好理解。

不妨先假设没有反转操作吧，由易到难嘛。这样的话难点就在M操作。记录实际的队列的同时，开一个单调递减的deque，记为qd。有数 i 入队时，qd从后面弹出所有比 i 小的数，再让 i 入队保持qd单调递减（因为靠后而大的数存在时，靠前而小的数一定不会有机会成为最大值了）。有数 i 出队时，如果 i 是qd队首的那个数，那qd当然也要弹出这个数。这样，就可保证每次M操作时，qd首元素就是当前队列最大值。

现在，有了反转操作。如果我们真的把每个元素取相反数，一来浪费时间，二来之前维护的qd就废了。因为反转后最小的数变成最大的了，那不如多开一个队列 -qd，这个队列单调递增，专门记录队列最小的元素。那什么时候输出qd队首什么时候输出 -qd队首呢？设置一个标记，表示当前队列元素的符号，每次反转就对这个标记取反，代表队列元素全体取相反数。这个标记也能提示你改输出qd队首还是 -qd队首。

现在剩下最后一个问题，插入。我们设置的标记代表队列内所有元素的符号，那这时要再插入一个新的元素 k 可能破坏这种规则，怎么办呢。这样，如果标记为正，则 k 可以直接入队，如果标记为负，则让 -k入队。这样，就能保证队列内元素与标记作用后都是原来的数！

代码

#include<iostream>
#include<queue>
#include<deque>
using namespace std;
queue<int>q;
deque<int>qd;
deque<int>_qd;
int sign=1;
void opI(){
    int x;
    scanf(" %d",&x);
    if(sign==0)x=-x;
    q.push(x);
    if(!qd.empty())
    while(x>qd.back()){
        qd.pop_back();
        if(qd.empty())break;
    }
    qd.push_back(x);
    if(!_qd.empty())
    while(x<_qd.back()){
        _qd.pop_back();
        if(_qd.empty())break;
    }
    _qd.push_back(x);
}
void opD(){
    if(q.empty())return;
    int a=q.front();
    q.pop();
    if(a==qd.front())qd.pop_front();
    if(a==_qd.front())_qd.pop_front();
}
void opR(){
    sign=(++sign)%2;
}
bool begun=0;
void opM(){
    if(q.empty())return;
    if(begun)printf("\n");
    else begun=1;
    if(sign==1){
        printf("%d",qd.front());
    }else{
        printf("%d",-_qd.front());
    }
}
int main(){
    int M;
    scanf("%d",&M);
    char op;
    for(int i=0;i<M;i++){
        scanf(" %c",&op);
        switch (op) {
            case ‘I‘:{
                opI();
                break;
            }
            case ‘D‘:{
                opD();
                break;
            }
            case ‘R‘:{
                opR();
                break;
            }
            case ‘M‘:{
                opM();
                break;
            }
        }
    }
    return 0;
}

JLU数据结构第六次上机实验

原文：https://www.cnblogs.com/huangyxblog/p/14869178.html