1 条题解
-
0
题目分析
20 pts
对于20%的数据,有 。
暴力搜索判断即可。
50 pts
对于50%的数据,有 。
递推:
在不考虑环形即不考虑 与 是否同色时的方案数有 。将上面方案数减去 与 同色的方案数即把这两块当成同一区域,此时方案数为 。
$$a_n = (m-1+1)(m - 1)^{n-1} - a_{n-1} \quad (n \geq 2)$$$a_n = (m - 1)^n+(m-1)^{n-1} - a_{n-1} \quad (n \geq 2)$
这个数列是一个公比为 的等比数列
公比为 的等比数列
代入 =
首项为 公比为 的等比数列
100 pts
对于100%的数据,有 。
由上可知
整理得
令 则 是公比为 首项 的等比数列:
所以 $a_n = (m - 1)^n + (-1)^{n-2}(m - 1) \quad (n \geq 2)$
游览计划
- 考点:图论,bfs,贪心。
- 难度:CSP-J T4
测试点 1~3
给暴力留的分。
测试点4~8
先通过bfs求出每个点到另一个点的最短路径的长度 ,然后暴力枚举四个点 ,然后求 就可以了。
复杂度 。
测试点9~10
答案就是 ,因为在完全图中,任意两点的最短路都是 。
测试点11~15
同样求出 ,然后暴力枚举三个点 ,然后求出离 点最远的点 ,但是 可能是 或者 ,所以需要求出离 点第二远的点 ,第三远的点 ,这样就一定可以找出那个最远的点。
复杂度是 。
当然也有许多其他做法。
测试点16~20
优化上一个算法。
同样求出 和 。
我们枚举两个点 ,然后经过 的最远路径一定是 其中之一。
依次考虑这几种情况,排除掉非法的情况(经过相同的点),直接枚举就可以了。
复杂度是 。
- 1
信息
- ID
- 82
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者