CVBB ACM Team

水

水

题意：有两种饼干，第一种有 $a$ 个，第二种有 $b$ 个。有两类人，第一类有 $n$ 个，第二类有 $m$ 个。当此时的饼干数 $a>b$ 时，第一类人吃第一种饼干，第二类人吃第二种饼干，否则相反。问是否有一种人的排列顺序使得每个人都有饼干吃。 $a,b,n,m\le 10^{18}$

题解：如果不管第二类人，那么第一类人可以吃掉全部的的 $a+b$ 个饼干。因此只需要 $\min(a,b)\ge m$ 并且 $a + b \ge n + m$ 即可。

水

题意：若开始有 $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 \ge i$ 则这个 $x$ 最终不能达到 $x+n$ ,否则这个 $a_i$ 可以有 $i-a[i]+x$ 种选择。由于 $p$ 是质数，进行的过程中判断是否为 $p$ 即可，注意离散化。效率 $O(\max\{a_i\}n)$

题意：数据范围改成 $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 < a_i$ 并且 $i - a_i + x = p$ 时不会被计入答案，因此改变一下第二个式子的顺序，即 $x = p - i + a_i$ 并且满足第一个条件时的 $x$ 不会被记入答案，因此扫一遍 $x$ 即可。效率为排序和二分的效率。