CSP-S 2022 题解
考试经历
估分：$100+100+[50,60]+0=[250,260]$。
实际：$100+100+75+0=275$。
第 1 题：假期计划
题目大意
有一个 $n$ 个点、$m$ 条边的无向图，其中点 $1$ 为家，其他点为景点。小熊计划从家出发去 $4$ 个不同的景点游玩，完成 $5$ 段行程后回家：$\mathrm{家} \to \mathrm{景点 A} \to \mathrm{景点 B} \to \mathrm{景点 C} \to \mathrm{景点 D} \to \mathrm{家}$ 且每段行程最多转车 $k$ 次（两个相邻目的地的距离不超过 $k+1$）。
保证 $5 \le n \le 2500$，$1 \le m \le 10000$，$0 \le k \le 100$，所有景点的分数是 $[1,10^{18}]$ 范围内的整数，保证至少存在一组符合要求的行程。
做法 1
$O(n^2)$ 求出任意两点的距离 $d_{i,j}$，$O(n^2)$ 对每个点 $u$ 求出最佳的若干个点 $v$（这里取 $3$ 个）使得 $dis_{u,v},dis_{v,1} \le k+1$ 且 $s_v$ 最大（$u,v \ne 1$）。然后 $O(n^2)$ 枚举点 $B$、点 $C$。
但是，我搞了个无聊错误，希望 CCF 的数据不要那么强。/kk
第 2 题：策略游戏
做法 1
第 3 题：星战
做法 1：（暴力）判断每个点的出度是否为 $1$
其实只要每个点的出度均为 $1$，从任意一个点出发都是一个环。