赛后总结

zhangyuhaoaa

·

2024-10-06 17:38:33

·

个人记录

赛后总结

比赛复盘

T1

T1直接贪心即可，我们如果想让 Luke 尽可能的名次高，那么就让每一个题目的比他低的人都总分比他低，那么这样 Luke 就可以名次就可以求出了，即 m 减去每一个题目比他低的人数的总和和 1 求最大，然后我们在考虑让 Luke 的名次尽可能的低的情况，我们可以让每个题目比他高的的人总和都比他高，那么他的名次就是每个题目比他高的人数的总和和 m 求最小。

预计100分，实际55分，因为我把 n 和 m 搞反了！！！

T2

T3我读完题目以后发现每一个数字的值域都非常的小，所以我们考虑桶排序，贪心的想，如果想让最大值最小，那么一定要让 a 中的最大值和 b 中的最小值匹配， a 中的次大值和 b 中的次小值匹配。我们用反证法证明：如果我们把两个数字交换，那么这样一组的数据就会非常的小，但是一组的数据非常的大，这样取较大值以后答案会比原先的大。

预计100分，实际90分，梦熊把数据出错了，在提示里写着没有0，但是在数据中却有0！！！！！

T3

直接 dfs 暴力。

预计20分，实际20分。

T4

我们用 floyd 加上暴力枚举4个点即可，复杂度 O(n^4)。

预计50分，实际50分。

总结

预计得分 100 + 100 + 20 + 50 = 270分。

实际得分 55 + 90 + 20 + 50 = 215分。

比赛过程中好的做法和不足

做的好的地方

无

做的不好的地方

T1脑瘫把 n 和 m 搞错了！！

知识点分析

T1 ：贪心

T2 ：桶排序

T3 ：数学

T4 ：图论

补题情况

T3

我们在不考虑 a_1 和 a_n 相同或不相同的时候，方案就是 (m-1)^{n-1} \times m。但是却有 a_1 和 a_n 相同的情况在里面，需要减去 a_1 和 a_n 相同的情况，如果 a_1 和 a_n 相同，那么我们就可以把 a_1 和 a_n 合并成一个大点，那么方案就是把 n-1 个点染色的情况。这样我们就有了递推公式 f(n)=(m-1)^{n-1} \times m-f(n-1) 。然后这样的时间复杂度就是 O(n^2)。然后考虑优化，我们把递推公式整理，得到 a_n-(m-1)^n=-[a_{n-1}-(m-1)^{n-1}]，我们令 a_i-(m-1)^i 看作 b_i，那么 b 数组就是一个公比为 -1 的等比数列，然后我们知道首项为 m-1，那么第 n 项就是 a_n=(m-1)^n+(-1)^{n-2} \times (m-1)。