2020-2021:teams:farmer_john:2sozx:codeforces_round_654_div._2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2sozx:codeforces_round_654_div._2 [2020/07/02 21:34] 2sozx [E2] |
2020-2021:teams:farmer_john:2sozx:codeforces_round_654_div._2 [2020/07/02 21:39] (当前版本) 2sozx |
||
|---|---|---|---|
| 行 10: | 行 10: | ||
| =====E1===== | =====E1===== | ||
| * 题意：若开始有 $x$ 个糖果，第 $i$ 个守卫有 $a_i$ 个糖果，如果到第 $i$ 个守卫时糖果数小于 $a_i$ ，则拥有的糖果数不变，否则糖果数 $+1$ ，最后会得到 $y$ 个糖果。现在可以重新排列守卫的顺序，$f(x)$ 表示开始有 $x$ 个糖果，最后的糖果数 $y=x+n$ 的重排个数，问有哪些 $x$ 使得 $f(x)\%p \not = 0$ $(2 \le p \le n \le 2000,a_i \le 2000)$ | * 题意：若开始有 $x$ 个糖果，第 $i$ 个守卫有 $a_i$ 个糖果，如果到第 $i$ 个守卫时糖果数小于 $a_i$ ，则拥有的糖果数不变，否则糖果数 $+1$ ，最后会得到 $y$ 个糖果。现在可以重新排列守卫的顺序，$f(x)$ 表示开始有 $x$ 个糖果，最后的糖果数 $y=x+n$ 的重排个数，问有哪些 $x$ 使得 $f(x)\%p \not = 0$ $(2 \le p \le n \le 2000,a_i \le 2000)$ | ||
| - | * 题解：我们考虑枚举 $x$ ，首先可以知道 $\min\{a_i\} \le x \le \max\{a_i\}$。我们将 $a_i$ 排序，从左到右扫。如果此时 $x \ge a_i$ ，则表示这个 $a_i$ 可以有 $i$ 个位置选择，即 $a_i$ 可以与 $a_j(j<i)$ 互换。如果 $x < a_i$ 如果 $a[i]-x>i-1$ 则这个 $x$ 最终不能达到 $x+n$ ,否则这个 $a_i$ 可以有 $i-a[i]+x$ 种选择。由于 $p$ 是质数，进行的过程中判断是否为 $p$ 即可，注意离散化。效率 $O(\max\{a_i\}n)$ | + | * 题解：我们考虑枚举 $x$ ，首先可以知道 $\min\{a_i\} \le x \le \max\{a_i\}$。我们将 $a_i$ 排序，从左到右扫。如果此时 $x \ge a_i$ ，则表示这个 $a_i$ 可以有 $i$ 个位置选择，即 $a_i$ 可以与 $a_j(j<i)$ 互换。如果 $x < a_i$ 如果 $a[i]-x \ge i$ 则这个 $x$ 最终不能达到 $x+n$ ,否则这个 $a_i$ 可以有 $i-a[i]+x$ 种选择。由于 $p$ 是质数，进行的过程中判断是否为 $p$ 即可，注意离散化。效率 $O(\max\{a_i\}n)$ |
| =====E2===== | =====E2===== | ||
| * 题意：数据范围改成 $2 \le p \le n \le 10^5,a_i \le 10^9$ | * 题意：数据范围改成 $2 \le p \le n \le 10^5,a_i \le 10^9$ | ||
| - | * 题解：显而易见的是 $x \ge \max\{a_i\}$ 时方案数 $mod p$ 一定为零，而且由于每个位置 $x$ 至多加一，因此 $x \ge \max\{a_i\} - n + 1$,并且我们可以二分出可以使得结果为 $x + n$ 的最小 $x$ 值。由上一题知 $x \ge a_p$ 时一定不会被记入答案。 | + | * 题解：显而易见的是 $x \ge \max\{a_i\}$ 时方案数 $mod p$ 一定为零，而且由于每个位置 $x$ 至多加一，因此 $x \ge \max\{a_i\} - n + 1$,并且我们可以二分出可以使得结果为 $x + n$ 的最小 $x$ 值。由上一题知 $x \ge a_p$ 时一定不会被记入答案。再由上一题知当 $x < a_i$ 并且 $i - a_i + x = p$ 时不会被计入答案，因此改变一下第二个式子的顺序，即 $x = p - i + a_i$ 并且满足第一个条件时的 $x$ 不会被记入答案，因此扫一遍 $x$ 即可。效率为排序和二分的效率。 |
| + | =====F===== | ||
2020-2021/teams/farmer_john/2sozx/codeforces_round_654_div._2.1593696850.txt.gz · 最后更改: 2020/07/02 21:34 由 2sozx
