[12/07/19]Day1

旧城等待， 2021-12-01 14:10 213阅读 0赞

### T1 ###

**20'**: 手推

**80'**: 由 \\(20'\\) 做法可知，我们可以建一个分层图，每一层的节点都与上一层，下一层的所有节点联通，且最上面一层为节点 \\(1\\) ，最下面一层为节点 \\(n\\) 。因为最短路径不考虑环，可以证明当前从 \\(1\\) 到 \\(n\\) 的任一路径均为最短路，且值为各层节点数代数积。

**100'**: 有了上述做法，很明显构造图的方式就是将 \\(k\\) 分解质因数并作为各层节点数。但若 \\(k\\) 为一个巨大的质数就肯定 \\(GG\\) ，所以我们需要一种新的方式。可以发现，如果在当前节点层下方增加节点数为 \\(2\\) 的一层，则可以完成从 \\(f(n)\\) 推导到 \\(f(2n)\\) 的过程；如果在当前图的根节点（即 \\(1\\) 节点）单独接一条线到最深层的任一节点，并使此路径的长度等于原最短路径，则可以完成从 \\(f(n)\\) 到 \\(f(n+1)\\) 的推导。这就是典型的倍增思想。

![1739468-20190712194001460-1710767891.png][]

### T2 ###

**100'**: 首先用栈判 \\(-1\\) ，若当前元素与栈顶元素相同，弹出栈顶元素病不加入当前元素。若栈顶最后不为空则为 \\(-1\\) 。与此同时以一定哈希规则记录下每次操作完后栈内字符串的哈希值。设字母哈希值为 \\(i\\)，操作后栈内字符串哈希值为 \\(j\\) 的字母所在位置为 \\(map\[i\]\[j\]\\) ，第 \\(i\\) 次操作完后栈内哈希值为 \\(s\[i\]\\) ，容易知道，两个字母可以匹配的充要条件为 \\(s\[l-1\]=s\[r\]\\) 且 \\(a\[l\]=a\[r\]\\)。那么我们就可以使用 \\(dfs\\) 分治，对于每一个当前区间的左端点 \\(l\\)，寻找在区间内且与右端点最接近的匹配点且未使用的 \\(x\\) 进行匹配（直接加入 \\(ans\\) 数组），并将当前区间划分成 \\(\[l+1,x-1\]\\) 和 \\(\[x+1,r\]\\)，递归。由于题目要求字典序最小，在递归时要先递归右区间。其次我们需要一个 \\(nxt\[\]\\) 数组来维护每个字母左边相邻相同字母且相同 \\(s\[i\]\\) 的位置避免不必要的对其它字母的查询。

![1739468-20190712200239674-1354702044.png][]

### T3 ###

**90'**: 看到“最短路径”的下意识应该就是祭出玄学的斯泼斯特拉。但是由于数据太大，不可以直接艹每个 \\(n\\) ，怎么办？容易知道，对于每个 \\(a\\) ，若存在，则这个 \\(a\\) 一定能使 \\(f(x)=|x\*(\\)当前小明最短路经过边数\\(-\\)当前全图最短路径经过边数\\()+\\)当前小明最短路长度\\(-\\)当前全图最短路径长度 \\()\\) 存在最小的值。所以这个问题可以由更加玄学的二分解决。但由于 \\(f(x)\\) 的参数并不是常量，即此函数并没有绝对的单调性，所以并不能保证绝对正确。这个算法实现性强，且对随机数据表现优异。

**100'**: 考虑 \\(dp\\) ，因为若通过加常数使原本不是最短路的路径变成最短路，这条路径通过的点数（即边数）一定比其他的路径少，证明略。所以我们可以用 \\(f\_\{i,j\}\\) 来记录小明经过 \\(i\\) 个关键点后到达 \\(j\\) 所需最短长度，用 \\(g\_\{i,j\}\\) 来记录小红经过 \\(i\\) 个点后到达 \\(j\\) 所需最短长度。若只经过 \\(i\\) 个点无法到达 \\(j\\) 点，函数值为 \\(INF\\)。\\(dp\\) 转移方程即从 \\(f\_\{i-1,k\}\\) 向 \\(f\_\{i,j\}\\) 转移，\\(g\\) 函数同理。枚举 \\(f\_\{i,t\}\\)，如果存在 \\(g\_\{j,t\}\\)，\\(j<i\\) 满足 \\(g\_\{j,t\}\\)<\\(f\_\{i,t\}\\) ，即全图最短路经过点数比经过最少的关键点的路径的点数少且全图最短路径小于经过关键点的最短路径，那么就 \\(Impossible\\)；当 \\(f\_\{i,t\}≠inf\\) 且任意 \\(j<i\\)， \\(g\_\{j,t\}=inf\\) ，即全图最短路经过点数比经过最少的关键点的路径的点数多，那么就 \\(Infinity\\)。

当然还有个好写点的打法：在错误的二分得到的答案左右再 \\(check\\) 一下，取最优值。

其他情况最多能加 \\\[\\min \\\{ \\frac \{g\_\{j,t\}-f\_\{i,t\}\}\{i-j\} |j<i\\\}\\\]

![1739468-20190713105143149-53267415.png][]

转载于:https://www.cnblogs.com/alexiswithlucifer/p/11178045.html

[1739468-20190712194001460-1710767891.png]: /images/20211201/3f486f1c3a6840ec82ea050a10ddb699.png
[1739468-20190712200239674-1354702044.png]: /images/20211201/f98ab3ab17f0483799e2e6b2ebc93801.png
[1739468-20190713105143149-53267415.png]: /images/20211201/77787460c0cd47f488601c98e7f12085.png