2020-2021:teams:farmer_john:2sozx:codeforces_round_561_div._2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2sozx:codeforces_round_561_div._2 [2020/07/17 17:16] 2sozx 创建 |
2020-2021:teams:farmer_john:2sozx:codeforces_round_561_div._2 [2020/07/17 17:28] (当前版本) 2sozx |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| + | <del>vp的时候cf又挂了</del> | ||
| =====A===== | =====A===== | ||
| * 水 | * 水 | ||
| 行 4: | 行 5: | ||
| * 水 | * 水 | ||
| =====C===== | =====C===== | ||
| - | * 题意：给出一个序列 $a$ ，问有多少对 $i,j$ 满足以下条件 $\min(|a_i+a_j|,|a_i-a_j|)\le\min(|a_i|,|a_j|)\le\max(|a_i|,|a_j|)\le\max(|a_i+a_j|,|a_i-a_j|)$ | + | * 题意：给出一个序列 $a$ ，问有多少对 $i,j$ 满足以下条件 $\min(|a_i+a_j|,|a_i-a_j|)\le\min(|a_i|,|a_j|)\le\max(|a_i|,|a_j|)\le\max(|a_i+a_j|,|a_i-a_j|)$\\ $n\le 2\cdot10^5$ |
| - | * 题解：如果不管第二类人，那么第一类人可以吃掉全部的的 $a+b$ 个饼干。因此只需要 $\min(a,b)\ge m$ 并且 $a + b \ge n + m$ 即可。 | + | * 题解：显然可以将 $a$ 的所有数取绝对值，对答案显然没有影响。考虑 $i,j$ 对答案有贡献的条件。设$a_i\le a_j$ ，则条件可化为 $a_j-a_i\le a_i \le a_j \le a_i+a_j$ ，即 $2a_i\ge a_j$ 。将 $a$ 排序扫一遍即可。 |
| =====D===== | =====D===== | ||
| - | * 水 | + | * 题意：$q(q\le10^3)$ 个询问，每个询问给定 $a,b,m(a,b,m\le 10^14)$ ,问是否存在一个序列 $x$ 有 $x_1=a,x_n=b,x_i=x_1+\cdots+x_{i-1}+r_i,1\le r_i\le m$ 显然序列的长度不会超过 $50$。 |
| - | =====E1===== | + | * 题解：设长度为 $k$ ,我们可以简单的推出 $b=2^{k-2}a+\sum_{i=2}^{k-1}2^{k-i-1}r_i+r_k$，由于 $r_i\ge 1$ ，可以先将每个 $r_i$ 减去 $1$，最后再加上即可。对于每个长度贪心求解即可。 |
| - | * 题意：若开始有 $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)$ | + | =====E===== |
| - | * 题解：我们考虑枚举 $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)$ | + | * 题意：有 $n(n\le 10^4)$ 个未知数，$m(m\le 50)$ 个集合，每个集合包含 $s_i$ 个元素，问是否存在 $n$ 个数使得对于任意一个集合 $s_i$ 有集合中位置的元素的 $lcm$ 严格大于非集合中元素的 $lcm$。 |
| - | =====E2===== | + | * 题解：如果集合两两相交则存在，否则不存在。<del>大 胆 猜 测</del> |
| - | * 题意：数据范围改成 $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$ 即可。效率为排序和二分的效率。 | + | |
| =====F===== | =====F===== | ||
| + | * 题意： | ||
| + | * 题解： | ||
2020-2021/teams/farmer_john/2sozx/codeforces_round_561_div._2.1594977387.txt.gz · 最后更改: 2020/07/17 17:16 由 2sozx
