这次 UER 虽然难度相对于上次简单了一些，但是看起来大家认为还是比较难。这次管理员在对题目难度的判断上还是出现了失误，下次我们尽量把难度再放低一点（如果还有下次）。

赶路

from skip2004

算法一

我会随机化/爆搜/状压/调整法！

我们反正就是要搞一个序列满足条件，随便怎么搞！

得分 $0\sim 100$ 不等，数据基本是随机的，水平高超应该可以通过！

算法二

这个第 $5$ 个点单独列出来，感觉很简单！

事实上也很简单，我们按照原点极角排序，然后走一圈就可以了！容易证明不会有自交。

算法三

这个第 $6, 7$ 个点也很简单！我们按照 $x$ 轴排序就好了！

可惜的是有一些同学没有发现可能有 $x$ 轴相同的点，导致第一个点可能不是 $1$，最后一个点可能不是 $n$。

同时，这个两个点也让我们意识到算法二可以使用的范围：起点不在凸包上。此时其周围都会有点就可以使用算法二了。

算法四

既然起点不在凸包上可以用算法二，那么我们就只要解决起点在凸包上的问题了！

容易发现，我们每次走斜率最小或者最大的边，到达的点还会在剩余点的点集的凸包上。如果这两个点都不是终点，我们任选一个，否则选另外一个。

时间复杂度 $O(Tn^2)$，期望得分 $100$ 分。

当然也有 $O(Tn\log_2 n)$ 的做法，由于这是 UER 所以我们就让小清新的 $n^2$ 做法通过了！

知识网络

from Itst

算法一

考虑对题目问题进行抽象。建立一个 $n$ 个点的图，其中编号为 $i$ 的点对应第 $i$ 个知识点，若两个知识点之间有直接联系或标签相同则在它们之间连一条无向边。那么计算 $f(p,q)$ 即为点 $p,q$ 之间的最短路长度，如果最短路不存在则为 $2k+1$。

图上点数为 $n$，边数为 $O(n^2+m)$，以每个点为起点广度优先搜索计算出最短路长度，复杂度 $O(n^3+nm)$，或者使用 Floyd $O(n^3+m)$ 计算最短路，可以通过测试点 $1$。

算法二

注意到标签产生的边数过多，考虑进行优化。在 $n$ 个知识点代表的节点基础上建立 $k$ 个辅助点表示每个标签，对于产生联系的两个知识点，在它们之间连双向的权值为 $1$ 的边，而对于每个知识点，将它向它所属标签对应的点连权值为 $0$ 的边、标签对应的点向它连权值为 $1$ 的边。

这样利用新建立的 $k$ 个辅助点即可做到标签相同就连 $1$ 边的效果，同时图上的边数压缩为 $O(n+m)$。仍然对每个点使用广度优先搜索运行边权为 01 的最短路，复杂度 $O(n(n+m+k))$，可以通过前三个测试点。

算法三

对于 $m\leq 3000$ 的测试点，绝大部分的知识点在图上仅有一条入边和一条出边，而这样的点到其他点的最短路可以容易地从其所在标签为起点的最短路中得到。因此只需要将所有有联系的知识点和标签对应的点保留运行最短路，当计算每个标签对应的点为起点的最短路后计算其连接的没有联系的知识点相关的答案。复杂度 $O(nk+(m+k)(\min(n,m)+k))$，可以通过前五个测试点。

算法四

注意到算法三中将知识点的计算与其标签的计算联系在了一起，考虑利用这样的思路拓展得到满分算法。

使用算法二的方式建图后，从每个标签开始运行最短路并建立最短路 DAG，复杂度 $O(k(n+m))$ 可以接受。将每个标签的最短路 DAG 建立后，考虑计算出该标签内所有知识点的答案。

注意到正在计算的知识点到目标节点的一种路径是先走到标签对应节点再通过最短路 DAG 到达目标节点，而从标签对应节点走到目标节点的一种路径是通过正在计算的知识点到达，因此正在计算的节点到达目标节点的最短路长度只有两种可能：一种是标签到达它的最短路长度，一种是它减一。而当该长度取到后者时，从从标签所在节点到达目标节点的一条最短路会经过正在计算的节点，因此正在计算的节点在 DAG 上的后继中存在目标节点。

因此容易得出长度取到最短路长度 -1 的充要条件是目标节点是正在计算的知识点在 DAG 上的后继。计算前驱后继相关的信息考虑使用 bitset 进行计算，即维护每个节点的前驱有哪些节点。

但一般的 bitset 长度是固定的，而每一次计算时长度都是不固定的，如果直接开到最大复杂度则会出错。测试点 8 提供了这样的部分分，同时测试点 6,7 也可能可以通过该方法获得分数。

正确的思路是可以对运行的点进行分块，每 $64$ 个为一组进行运行，这样每次可以使用一个 unsigned long long 维护，复杂度为 $O(k(n+m)+\frac{n(n+m)}{w})$，可以通过所有测试点。将块长进行调整可能可以得到常数更小的做法。

面试

from he_____he

算法一

对每个 $(x,y,z)$ 均询问一遍，找到答案为 $0$ 的那一组，即为 $(a,b,c)$ 的值。

询问次数 $(n+1)^3$ ，期望得分 $10$ 分。

算法二

对于 $n=4$ 的部分分，考虑爆搜决策树。枚举第一次询问的三元组，再枚举第一次询问得到的答案，对于每一种不同的答案，继续向下搜索。一共需要枚举 $3$ 次答案和 $3$ 次询问，最后还需要枚举这个分支是否能够求出唯一的答案，复杂度为 $O((3n+1)^3(n+1)^{12})$ ，但可以进行剪枝，让一个分支失败后直接回溯，或规定第一次询问 $(0,0,0)$ 。可以在本机打表出决策树，这只需要一个 $(3n+1)^2$ 大小的表。询问次数 $3$ ，结合算法一可以得到 $30$ 分。

算法三

有很多种与正解类似但不够优秀的做法可以做到 $3$ 次询问后让可能的解集缩小为 $1$ 或 $2$ ，可以通过 $tp$ 为 $2$ 和 $4$ 的数据点，这里不再赘述。与前两个算法结合可以得到 $65$ 分。

算法四

第一次询问 $(0,0,0)$ ，可以得到 $a+b+c$ 的值，设为 $s$ 。

不妨设 $s\leq \frac{3n}2$ ，否则可以将 $a,b,c$ 分别视为 $n-a,n-b,n-c$ 。

如果 $s\leq n$ ，则可以询问 $(0,0,n)$ 和 $(0,n,0)$ 分别得到 $c,b$ 的值，求出 $a,b,c$ 分别是什么，否则 $s>n$ 。

第二次询问 $(n,s-n,0)$ ，得到的答案是 $c+|n-a-c|+(n-a)=n-a+c+|n-a-c|$ ，设为 $2t$ 。

若 $a+c\leq n$ ，则 $n-a=t$ ，否则 $c=t$ 。下面分两种情况讨论：

1. 若 $s-t>n$ ，则第三次询问 $(n,s-t-n,t)$ ，得到的答案是 $(t-c)+(n-a)+(n+t-a-c)=2n+2t-2(a+c)$ ，可以得到 $a+c$ 的值，从而能够分出第二次询问得到的究竟是 $n-a$ 还是 $c$ ，就能求出 $a,b,c$ 的值了。

2. 若 $s-t\leq n$ ，则第三次询问 $(s-t,0,t)$ ，得到的答案是 $(t-c)+|t-b-c|+b=t-c+b+|t-b-c|$ 。由于 $t=c$ 或 $n-a$ ，所以 $t-b-c<0$ 。

   所以询问得到的是 $t-c+b-t+b+c=2b$, 可以得到 $b$ 的值，同样就能够知道 $a+c$ 的值，分出第二次询问属于哪一种情况，求出 $a,b,c$ 的值。

期望得分 $100$ 分。

P.S. 本题 std 只有不到 $\texttt{500B}$，$20$ 多行代码，是一道难得一见的良心题啊！!1