学校数据结构2021-12-13上机题

T1 小龙猜数字

问题描述

定义字符串的秩为：该字符串长度减去该字符串的最短相等前后缀的长度。若该字符串不存在相等的前后缀，则其秩为 $0$ 。

给出一个字符串 $S$ ，需计算 $S$ 及 $S$ 中所有前缀子串的秩之和。

字符串长度不超过 $10^6$ 。

题解

此题目为 $KMP$ 数组的应用，但 $KMP$ 失败数组求的是最长的相等前后缀，所以要对其进行修改。<center></center>

如图，对于 $ababab$ 其失败数组标明了前后缀相等的子串为 $abab$ ，而子串 $abab$ 的失败数组标明了最长前后缀相等的是 $ab$ ，而因为在原串中前后缀相等的性质，可知原串中必有相等的前后缀 $ab$ 。

因此，可通过不断访问子串的失败数组，来得到最小前缀。

但需要注意，当 $S$ 中所有字符都相等时，该算法时间复杂度为 $O(n^2)$ 。因此需要将子串失败数组，按照类似并查集的方式进行路径压缩。<center> </center>比如在 $ababa$ 中，根据失败数组访问子串 $aba$ 时，发现 $aba$ 的失败数组为 $0$ ，则可将 $ababa$ 失败数组也改成 $0$ ，同理可将 $ababab$ 失败数组改成 $1$ 。

T2 二叉树路径和

问题描述

给定一颗二叉树，树有点权，求问是否有一条路径，其点权和为 $K$ 。

“路径”定义为二叉树中的结点序列 $v_i ,v_{i+1},..., v_j$ ，序列中前一个结点是后一个结点的父结点。

如有多条路径，输出最短的一条，且最靠右，最靠叶节点。

有多组数据，总结点数不超过 $1.5 \times 10^5$ 。

题解

不知此题有没有什么暴力出奇迹的解法，但如果数据强度足够，这题应该是几次上机以来最难的一题。

首先各种暴力，如两次 $DFS$ ，从叶节点反着找等等，都是时间复杂度 $O(n^2)$ 的，很容易超时。

这里提供一种方式，理论上可以通过。

首先，这题输入就比较麻烦，因为并不知道树有多少个节点，而且还是多组数据，没法用 $EOF$ 等方式判断一组数据是否输入结束。同时为了优化时间，选择读入同时建树，依据二叉树带空指针的先根序列表示法，当对应的树建成，就代表一组数据已经读完了。

代码结构大概如此：

build:
    读入左子树信息;
    if (左子树不是空指针)
        build(左子树);
    读入右子树信息;
    if (右子树不是空指针)
        build(右子树);

然后开始对建好的树进行 $DFS$ ，直到叶节点，可见这个操作遍历了树的一条链，遍历过程中，记录每个节点到根节点的点权的前缀和 $sum$ ，及节点的深度 $deep$ 。

可知，所求的路径一定在某一条从根到叶节点的链上，而对于一条链上，我们只要找到两个节点 $x,y$ ，使其满足：

$$deep_x<=deep_y$$

$$sum_y-sum_{x_{father}}=K，x_{father}为 x 父节点$$

则 $x,y$ 之间的路径就是一条合法的路径，而求解时可先枚举确定 $y$ ，然后求对应的 $x$ ，这个过程可暴力枚举，时间复杂度 $O(n^2)$ 。但该式子为一次函数，所以可以先将 $sum,deep$ 排序（需要快排、归并等效率较高的排序），然后通过二分查找确定 $x$ 以进行优化，优化后的时间复杂度为 $O(n \log n)$ ，再通过对程序细节处理上尽量提高效率，理论上可以稳定通过此题数据。

对于题目中要求 <font color=red>“若存在多条满足条件的路径，则输出最短（包含结点个数最少）者，若存在多条最短的路径，则输出最靠右下者。”</font>可在 $DFS$ 顺序上进行修改，优先搜索右子树，同时在枚举 $y$ 时，顺序从叶节点到根节点即可。

DO:
    Sort(sum,deep);   //对sum和deep双关键字排序 
    For y=n to 1 do     //n为链上的节点个数，n是叶，1是根
    {
        Find(x);        //确定对应的x
        Update(Ans);    //更新答案
    }

DFS:
    if (该节点不是叶节点)
    {
        DFS(右子树);
        DFS(左子树);
    }
    else
        DO();

T3 最小支撑树

问题描述

给一个无向图，求最小生成树，注意图可能不连通。

多组数据，每组数据的点数和边数都不超过 $1.5 \times 10^3$ 。

题解

最小生成树模板题，推荐 $Kruskal$ ，利用并查集判断图是否连通即可。