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/27 22:41] grapelemonade [B] |
2020-2021:teams:mian:nowcoder_training:2020_multi-university_training_contest_6 [2020/07/31 19:55] (当前版本) grapelemonade [Comments] |
||
|---|---|---|---|
| 行 7: | 行 7: | ||
| * Solved 5 out of 11 problems | * Solved 5 out of 11 problems | ||
| * Rank 95 / 1120 in official records | * Rank 95 / 1120 in official records | ||
| - | * Solved 6 out of 11 afterwards | + | * Solved 8 out of 11 afterwards |
| <HTML> | <HTML> | ||
| 行 28: | 行 28: | ||
| ^ Solved ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^ I ^ J ^ K ^ | ^ Solved ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^ I ^ J ^ K ^ | ||
| | Pantw | | √ | | | | | O | | | | √ | | | Pantw | | √ | | | | | O | | | | √ | | ||
| - | | Withinlover | | | √ | | √ | | | | | | | | + | | Withinlover | O | | √ | | √ | | | | | O | | |
| | Gary | - | | | | | | | √ | | | | | | Gary | - | | | | | | | √ | | | | | ||
| 行 40: | 行 40: | ||
| ===== A ===== | ===== A ===== | ||
| + | 没看懂题解的 H 函数自己瞎推一推 | ||
| + | |||
| + | 假设长度为 n 的环需要的代价为 $f(n)$，随机打乱总的情况数是 $n!$，然后计算一下所有情况中长度为 $i$ 的环出现的次数，就可以递推的求了，这个可以前缀和优化。 | ||
| + | |||
| + | 哦对了，最开始把模数写成 $1e9 + 7$了，死活过不了样例 | ||
| + | |||
| + | 哦对了，一开始的式子还推错了，不过看样例可以猜出$f(4) = 34/3$。找对这个就OK了 | ||
| + | |||
| + | 哦对了，如果一开始就看出了 $f(4) = 34/3$，那其实也不太用推公式了，光看手算的过程已经可以把公式猜出来了（ | ||
| + | |||
| + | 题解用了个 $H()$ 函数和 $f()$ 函数递推，然而看不懂，不过这题主要还是看思路吧，当时没想到找环（ | ||
| + | |||
| + | UPD: 貌似题假了，上面就当是废话吧 [[https://www.zhihu.com/question/409954876/answer/1365275315|知乎讨论贴]] | ||
| ===== B ===== | ===== B ===== | ||
| 行 46: | 行 59: | ||
| 具体证明没看懂，回头补。（大概吧） | 具体证明没看懂，回头补。（大概吧） | ||
| ===== C ===== | ===== C ===== | ||
| + | |||
| + | 可以证明，取两列的结果一定不优。样例是迷惑人的。 | ||
| + | |||
| + | 把每一列的单独算，然后取个最大值就行了 | ||
| ===== D ===== | ===== D ===== | ||
| ===== E ===== | ===== E ===== | ||
| + | |||
| + | 给定n，k的值是固定的，只要给定的k不对就无解。 | ||
| + | |||
| + | n, 1, n - 1, 2, n - 2, ... | ||
| + | |||
| + | n, n/2, 1, n - 1, 2, n - 2, ... | ||
| + | |||
| + | 这俩看情况选一个就行了 | ||
| ===== F ===== | ===== F ===== | ||
| 行 77: | 行 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 ===== | ||
| 行 82: | 行 109: | ||
| ===== J ===== | ===== J ===== | ||
| + | 赛后过题，不愧是我 | ||
| + | |||
| + | 找出约瑟夫变换的数组后，变换x次显然可以快速幂写掉。这个复杂度是$ \log $的，所以瓶颈在于如何求约瑟夫变换的那个数组。 | ||
| + | |||
| + | 我本打算写个暴力找一下然后看题解。然后暴力打着打着发现复杂度好像是对的。（二分 + 树状数组） | ||
| + | |||
| + | 然后就A了（正解貌似没有二分，想起来在说吧） | ||
| + | |||
| + | 找的思路类似于约瑟夫问题的那个 $ O(n) $的dp，但是不确定在原数组中的位置，然后我就用树状数组 + 二分暴力了一下。 | ||
| ===== K ===== | ===== K ===== | ||
| 行 101: | 行 137: | ||
| ====== Comments ====== | ====== Comments ====== | ||
| + | ptw: | ||
| + | |||
| + | * 别 再 看 错 特 例 了 (G) | ||
| + | * 特例可以 double-check 一下，稳一点 (G) | ||
| + | * 可以早点想 A 和 J | ||
| + | |||
| + | withinlover: | ||
| + | |||
| + | * 最后应该早点想A的，稍微推一推其实挺可做的（这个傻子挨个手算了2-8的答案就是想不到去判一下n=1呢）（G） | ||
| + | * 最后讲题的时候才知道稍微改改方程就好dp很多。结果让Gary调了半天，这波全责（H） | ||
| + | * 中场的时候把每个题挨个看一遍（最近跟榜总会把水题跟漏了） | ||
| + | |||
| + | Gary： | ||
| + | * H数位dp写的有点麻烦，调了很久 | ||
| + | * A题的公式推跑偏了，推得值也奇奇怪怪，思路上没想到dp | ||
| + | * 没看J，封榜的时候过的也不多就没注意了 | ||
| + | * （↑ P: 好像是赛中数据错了所以 AC 的人少？） | ||
2020-2021/teams/mian/nowcoder_training/2020_multi-university_training_contest_6.1595860894.txt.gz · 最后更改: 2020/07/27 22:41 由 grapelemonade
