Educational Codeforces Round 117

Educational Codeforces Round 117

A

判断距离奇偶，在 \((0,\frac {a + b} 2)\) 和 \((\frac {a + b} 2,0)\) 选一可行点。

B

先把 \(a, b\) 分别放到两边，然后将尽量大的数放在左边，尽量小的数放在右边，判断剩下的数是否可行。

C

二分模拟即可。

D

观察这个过程，令 \(b > a\)，将 \((a, b)\) 变成 \((b - a, b)\) 屁用没有，只能变成 \((a, b - a)\) 即这就是个辗转相减的过程，判断过程中是否会出现数 \(x\)，当且仅当某一次 \(b\bmod a = x\bmod a \and x \le b\)。

E

对于选不大于 \(20\) 个数暴力算选每种数的期望得分，贪心排序选即可，对于选大于 \(20\) 个数，首先前 \(20\) 个数的选择方案一定不变，后面增加的数一定小于前面的数（在不计算概率下）的得分，令前选 \(20\) 个数的得分为 \(A\)，多选一个相当于增加了 \(\frac A {21} + \frac a {21} - \frac A {20} = \frac {20a} {420} - \frac A {420}\)，显然这个东西小于 \(0\)，即加一个数不优，加两个数也是如此。

F

降智题

考虑一个 naive 的暴力，建一张图每个点代表现在最大拥有 \((i, j)\)，进行连边就是 \((i, j) \to (\min(i + j + s_{i, j}, n), j)\) 和 \((i, j) \to (i, \min(i + j + s_{i, j}, m))\)，然后跑宽搜即可，但状态多到爆炸。

令 \(n \le m\)，考虑优化状态个数，我们将宽搜的状态按 \(dis\) 分层，若有两点 \((x, y), (x', y')\) 满足 \(x \le x', y \le y'\)，那么直接删去 \((x, y)\) 即可，最后我们使得每层状态个数至多为 \(n\)，看起来还是不可过，我们意识到这种宽搜的时间复杂度（\(\mathcal O(n \times \text{ans})\)）还取决于最后的答案，对于一个矩形长宽皆为 \(n\)，我们发现它的答案最大为 \(\log n\) 级别（由斐波那契可得），那么一个矩形 \((n, m)\)，答案最大为 \(\log n + \frac m n\) 且不满，算一算发现时间复杂度可过。

G

对于数字 \(n\) 有 \(m\) 个，分别填在了 \(\{x_i\}\)，把关于每个点贡献拉出来就是 \(x_i \times (-(m - i) + (i - 1)) = x_i \times (2 \times i - m - 1)\)，那么考虑从后往前填数，因为对于每种数其 \((2 \times i - m - 1)\) 是递减的，填在位置 \(x\) 时贪心地让 \((2 \times i - m - 1)\) 最大的填在这里一定是对的，这样就得到了第一问答案，对于 \((2 \times i - m - 1)\) 相同且最大的数，连续的一段一定都是填这些数，排列一下即可得到方案数。