2020-2021:teams:hotpot:codeforceser92
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:codeforceser92 [2020/07/31 15:09] 喝西北风 |
2020-2021:teams:hotpot:codeforceser92 [2020/07/31 15:37] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 14: | 行 14: | ||
| =====B - Array Walk===== | =====B - Array Walk===== | ||
| + | |||
| + | ====问题描述==== | ||
| 给定长为n序列a。一开始在第一格，分数是$a_1$。每次可以向左或向右走一格，但最多一共向左走z次，且不能连续向左走两格。问走k次后最大分数。 | 给定长为n序列a。一开始在第一格，分数是$a_1$。每次可以向左或向右走一格，但最多一共向左走z次，且不能连续向左走两格。问走k次后最大分数。 | ||
| 行 69: | 行 71: | ||
| ====解题思路==== | ====解题思路==== | ||
| - | 等价于要求$xd+y\equiv yd+x pmod w$,即$(y-x)(d-1)\equiv 0 pmod w$。设$n=gcd(d-1,w)，w_0=\frac w{n}$。等价于要求$\frac w_0|y-x$ | + | 等价于要求$xd+y\equiv yd+x pmod w$,即$(y-x)(d-1)\equiv 0 pmod w$。设$n=gcd(d-1,w)，w_0=\frac w{n}$。等价于要求$w_0 | y-x$ |
| 枚举y-x，再等差数列求和即可。 | 枚举y-x，再等差数列求和即可。 | ||
| 行 81: | 行 83: | ||
| ====数据范围==== | ====数据范围==== | ||
| - | $1\le n \le 2\cdot 10^5$,$1\e l_i \le r_i \10^9$,$t_i\in \{1,2\}$ | + | $1\le n \le 2\cdot 10^5$,$1\le l_i \le r_i \le 10^9$,$t_i\in \{1,2\}$ |
| + | |||
| + | ====解题思路==== | ||
| + | |||
| + | 每个区间建一个点。若两个区间不能放在一起，则连上边。本题等价于求这个二分图的最小割（去掉若干个点，剩余点两两不相连），也就等价于求这个二分图的最大匹配。 | ||
| + | |||
| + | 这个最大匹配我们可以贪心。首先按区间左端点排序。每次放入一个新点，删去原图中所有右端小于新点左端的点。找到与新点颜色不同的点中，右端最小的，和其进行匹配。 | ||
| + | |||
| + | 设这个最大匹配是m，最终答案为n-m | ||
| + | |||
| + | =====G - Directing Edges===== | ||
| + | |||
| + | 不会，跳了 | ||
2020-2021/teams/hotpot/codeforceser92.1596179383.txt.gz · 最后更改: 2020/07/31 15:09 由 喝西北风
