2020-2021:teams:mian:nowcoder_training:2020_multi-university_training_contest_6
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:mian:nowcoder_training:2020_multi-university_training_contest_6 [2020/07/28 16:46] withinlover [A] |
2020-2021:teams:mian:nowcoder_training:2020_multi-university_training_contest_6 [2020/07/31 19:55] (当前版本) grapelemonade [Comments] |
||
|---|---|---|---|
| 行 43: | 行 43: | ||
| 假设长度为 n 的环需要的代价为 $f(n)$，随机打乱总的情况数是 $n!$，然后计算一下所有情况中长度为 $i$ 的环出现的次数，就可以递推的求了，这个可以前缀和优化。 | 假设长度为 n 的环需要的代价为 $f(n)$，随机打乱总的情况数是 $n!$，然后计算一下所有情况中长度为 $i$ 的环出现的次数，就可以递推的求了，这个可以前缀和优化。 | ||
| + | |||
| + | 哦对了，最开始把模数写成 $1e9 + 7$了，死活过不了样例 | ||
| 哦对了，一开始的式子还推错了，不过看样例可以猜出$f(4) = 34/3$。找对这个就OK了 | 哦对了，一开始的式子还推错了，不过看样例可以猜出$f(4) = 34/3$。找对这个就OK了 | ||
| - | 哦对了，如果一开始就猜出了 $f(4) = 34/3$，那其实也不太用推公式了，光看手算的过程已经可以把公式猜出来了（ | + | 哦对了，如果一开始就看出了 $f(4) = 34/3$，那其实也不太用推公式了，光看手算的过程已经可以把公式猜出来了（ |
| 题解用了个 $H()$ 函数和 $f()$ 函数递推，然而看不懂，不过这题主要还是看思路吧，当时没想到找环（ | 题解用了个 $H()$ 函数和 $f()$ 函数递推，然而看不懂，不过这题主要还是看思路吧，当时没想到找环（ | ||
| + | UPD: 貌似题假了，上面就当是废话吧 [[https://www.zhihu.com/question/409954876/answer/1365275315|知乎讨论贴]] | ||
| ===== B ===== | ===== B ===== | ||
| 行 99: | 行 102: | ||
| 1 1 2 1 2 1 2 我居然觉得没问题，我是傻子呜呜呜 | 1 1 2 1 2 1 2 我居然觉得没问题，我是傻子呜呜呜 | ||
| ===== H ===== | ===== H ===== | ||
| + | |||
| + | 数位dp，f(i,j)表示后i为和为j的个数，数位dp枚举到两个数第一个出现不同的位置，枚举差值，再通过f数组求解 | ||
| ===== I ===== | ===== I ===== | ||
| 行 143: | 行 148: | ||
| * 最后讲题的时候才知道稍微改改方程就好dp很多。结果让Gary调了半天，这波全责（H） | * 最后讲题的时候才知道稍微改改方程就好dp很多。结果让Gary调了半天，这波全责（H） | ||
| * 中场的时候把每个题挨个看一遍（最近跟榜总会把水题跟漏了） | * 中场的时候把每个题挨个看一遍（最近跟榜总会把水题跟漏了） | ||
| + | |||
| + | Gary： | ||
| + | |||
| + | * H数位dp写的有点麻烦，调了很久 | ||
| + | * A题的公式推跑偏了，推得值也奇奇怪怪，思路上没想到dp | ||
| + | * 没看J，封榜的时候过的也不多就没注意了 | ||
| + | * （↑ P: 好像是赛中数据错了所以 AC 的人少？） | ||
2020-2021/teams/mian/nowcoder_training/2020_multi-university_training_contest_6.1595925978.txt.gz · 最后更改: 2020/07/28 16:46 由 withinlover
