《第一次上机实验》解题报告

• 第1题  连通分量

本题可以使用dfs和并查集，本来是dfs更好写一点（但我当时还不会用vector建不来邻接表）所以我使用的并查集。

思想：每次输入边时将边所连的两个点分为一类（改变其中一个指针指向另一个）。最后数有多少类（根节点---指针指向自己）就行了。因为被卡时间卡怕了，直接就用了带压缩路径的并查集（也是最简单的）。

时间复杂度O（m*a(n)）。

总结：并查集代码简单，但如果临时忘了很难现推出来。在考场先推并查集花了我这道题大量时间。所以最好将并查集代码保存一份，或背下来。

#include<stdio.h>
#include<math.h>
#include<string.h>
int x[50100];
int find(int a)
{
    if (x[a] == a)
        return a;
    return find(x[a]);
}
int main(void)
{
    int n, m, a, b, c, d,s=0;
    scanf("%d %d", &n, &m);
    for (a = 1; a <= n; a++)
    {
        x[a] = a;
    }
    for (a = 1; a <= m; a++)
    {
        scanf("%d %d", &b, &c);
        b=find(b);
        c=find(c);
        x[b] = c;
    }
    for (a = 1; a <= n; a++)
    {
        if (x[a] == a)
            s++;
    }
    printf("%d", s);
    return 0;
}

• 第2题 旅行

单源最短路问题，可以用Dijkstra和Bellman-Ford两种方法我选择的是Dijkstra（因为要求最多经过的城市数）

思想：因为是无向图，所以要存两条边。用数组x[2*m][3]存放边（不要问为什么不用vector了）将边的起点从小到大排序（用快排），再用数组o[n]记录每个节点为起点在边表的开始位置。

从起点开始，维护一个栈z，弹出最小边，压入对应节点的相邻边，同时不断更新最小费用数组与最大经过数组y。

时间复杂度O（n*n+e）

总结；纯c终究还是落后于版本了，如果会vector就不用建立有序边表这么繁琐的操作了。还有判定最短边时各种关系倒来倒去很乱，我也应该优化一下我的代码风格了（我自己写的代码，过了一个星期就看不懂了）

#include<stdio.h>
int x[200100][3];
int y[10010][2];
int z[100100];
int o[10010];
void fx(int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1, a = x[(l + r) >> 1][0], t;
    while (j > i) {
        do i++; while (a > x[i][0]);
        do j--; while (a < x[j][0]);
        if (i < j)
        {
            t = x[i][0];
            x[i][0] = x[j][0];
            x[j][0] = t;
            t = x[i][1];
            x[i][1] = x[j][1];
            x[j][1] = t;
            t = x[i][2];
            x[i][2] = x[j][2];
            x[j][2] = t;
        }
    }
    fx(l, j);
    fx(j + 1, r);
}
int main(void)
{
    int n, m, a, b=1, c, d=1,s,p=0,q=2;
    scanf("%d %d %d", &n, &m,&s);
    for (a = 1; a <= n; a++)
    {
        y[a][0] = 9999999;
    }
    y[s][0] = 0;
    y[s][1] = 0;
    z[1] = s;
    for (a = 1; a <=2*m; a+=2)
    {
        scanf("%d %d %d", &x[a][0], &x[a][1], &x[a][2]);
        x[a + 1][0] = x[a][1];
        x[a + 1][1] = x[a][0];
        x[a + 1][2] = x[a][2];
    }
    fx(1, 2 * m);
    for (a = 1; a <= 2 * m+1; a++)
    {
        if (x[a][0] != d)
        {
            o[d] = a - 1;
            d++;
        }
    }
    for (a = 1; a <= 2*m; a++)
    {
        p++;
        for (b = o[z[p]]; x[b][0] == z[p]; b--)
        {
            if (b <= 0)
                break;
            if (y[x[b][1]][0] > x[b][2] + y[z[p]][0])
            {
                y[x[b][1]][0] = x[b][2] + y[z[p]][0];
                y[x[b][1]][1] = y[z[p]][1]+1;
                z[q] = x[b][1];
                q++;
            }
            if (y[x[b][1]][0] == x[b][2] + y[z[p]][0] && y[x[b][1]][1] < y[z[p]][1] + 1)
            {
                y[x[b][1]][1] = y[z[p]][1] + 1;
                z[q] = x[b][1];
                q++;
            }
            
        }
        if (p ==q)
            break;
    }
    for (a = 1; a < n; a++)
    {
        printf("%d ", y[a][0]);
    }
    printf("%d", y[a][0]);
    printf("\n");
    for (a = 1; a < n; a++)
    {
        printf("%d ", y[a][1]);
    }
    printf("%d", y[a][1]);
    return 0;
}
 

• 第3题 算术表达式计算

这道题真没什么说的，之前做过的，就是有一点繁琐，NaN判断弹出时要想一段时间。

思想；为了美观，写一个put函数，内涵+-*/四种运算。引入f判断数字是否连续，引入n判断是否除数是0，然后开始枚举+-*/四种情况。

时间复杂度O（n）

总结：简单但是很烦，要考虑所有情况，还好之前做过，但依旧有所纰漏，主要考验的就是细心。NaN的情况只要一直break就行了

#include<stdio.h>
int x[5000] = {};
char y[5000] = {};
char ch;
int a, b, d, e, f,n=0;
void put()
{
    b -= 1;
    if (y[b] == '+')
        x[a - 2] += x[a - 1];
    if (y[b] == '-')
        x[a - 2] -= x[a - 1];
    if (y[b] == '*')
        x[a - 2] *= x[a - 1];
    if (y[b] == '/')
    {
        if (x[a - 1] == 0)
        {
            n = 1;
            return;
        }
        x[a - 2] = x[a - 2] / x[a - 1];
    }
    if (y[b] == '^')
    {
        f = x[a - 2];
        for (e = 1; e < x[a - 1]; e++)
            x[a - 2] *= f;
    }
    a--;
}
int main(void)
{
    a = 0;
    b = 1;
    d = 0;
    f = 0;
    y[0] = '#';
    while (1)
    {
        ch = getchar();
        if (ch >= '0' && ch <= '9')
        {
            if (f == 0)
            {
                x[a] = ch - '0';
                a++;
                f = 1;
            }
            else
            {
                x[a - 1] = x[a - 1] * 10 + ch - '0';
            }
        }
        if (ch == '+' || ch == '-')
        {
            while (y[b - 1] != '#' && y[b - 1] != '(')
            {
                put();
                if (n == 1)
                    break;
            }
            y[b] = ch;
            b++;
            f = 0;
        }
        if (ch == '*' || ch == '/')
        {
            while (y[b - 1] == '*' || y[b - 1] == '/' || y[b - 1] == '^')
            {
                put();
                if (n == 1)
                    break;
            }
            y[b] = ch;
            b++;
            f = 0;
        }
        if (ch == '^')
        {
            while (y[b - 1] == '^')
            {
                put();
                if (n == 1)
                    break;
            }
            y[b] = ch;
            b++;
            f = 0;
        }
        if (ch == '(')
        {
            y[b] = '(';
            b++;
            f = 0;
        }
        if (ch == ')')
        {
            while (y[b - 1] != '#' && y[b - 1] != '(')
            {
                put();
                if (n == 1)
                    break;
            }
            b--;
            f = 0;
        }
        if (ch == '=')
        {
            while (y[b - 1] != '#')
            {
                put();
                if (n == 1)
                    break;
            }
            break;
        }
    }
    if (n == 1)
        printf("NaN");
    else
    printf("%d", x[0]);
    return 0;
}

• 第4题 序列乘积

这道题我刚开始的思路和***的很想，维护一个栈，每次弹出一个，压入两个，每次从栈中找最小的弹出，但这是n*n的复杂度，所以不太行。然后我在课上没做出来，课后听到***的想法，决定建堆，然后维护这个堆，于是就可以达到n*log n的时间复杂度。

思想；先写个swap函数使代码美观。先遍历上面一排数乘以下面一排第一个数，建立一个小根堆，然后弹出最上面的根节点，根节点改变（上面不变，下面的数右移一个）然后维护这个小根堆，重复弹出n个数，结束。

时间复杂度O（n*log n）

总结：关键就是维护栈的有序，无论是用堆还是什么（***用的好像不是堆，是优先队列）（纯c已经落后于版本了）只要有序，弹出操作的时间就是log n。我的堆也建的不熟练，课后也建了半天。

  

#include<stdio.h>
int x[100100];
int y[100100];
int z[400100][3];
void swap(int i, int j)
{
    int t;
    t = z[i][0];
    z[i][0] = z[j][0];
    z[j][0] = t;
    t = z[i][1];
    z[i][1] = z[j][1];
    z[j][1] = t;
    t = z[i][2];
    z[i][2] = z[j][2];
    z[j][2] = t;
}
void fx(int i)
{
    int t;
    if (z[i*2][0] == 0 && z[i*2+1][0] == 0)
        return;
    if (z[i*2][0] != 0 && z[i*2+1][0] == 0)
    {
        t = z[i*2][0];
        if (t < z[i][0])
        {
            swap(i*2, i);
            fx(i*2);
        }
        return;
    }
    else
    {
        if (z[i * 2][0] <= z[i * 2 + 1][0])
        {
            t = z[i * 2][0];
            if (t < z[i][0])
            {
                swap(i * 2, i);
                fx(i * 2);
            }
        }
        else
        {
            t = z[i * 2 + 1][0];
            if (t < z[i][0])
            {
                swap(i * 2 + 1, i);
                fx(i * 2 + 1);
            }
        }
    }

}
int main(void)
{
    int a, b, c, d, n;
    long long s;
    scanf("%d", &n);
    for (a = 1; a <= n; a++)
    {
        z[a][1] = a;
        z[a][2] = 1;
        scanf("%d", &x[a]);
    }
    x[n + 1] = 999999999;
    y[n + 1] = 999999999;
    for (a = 1; a <= n; a++)
    {
        scanf("%d", &y[a]);
        z[a][0] = x[z[a][1]] * y[z[a][2]];
    }
    for (a = 1; a < n; a++)
    {
        printf("%d ", z[1][0]);
        z[1][2]++;
        z[1][0] = x[z[1][1]] * y[z[1][2]];
        fx(1);
    }
    printf("%d", z[1][0]);
    return 0;
}