2020-2021:teams:hotpot:codeforceser94
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:hotpot:codeforceser94 [2020/08/28 13:21] misakatao 更新 |
2020-2021:teams:hotpot:codeforceser94 [2020/09/01 20:21] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 68: | 行 68: | ||
| 对于一个非0区间，找到最小值看这个值和区间长度，选择最优的方式减，然后再重复这个过程递归下去，如果最小值大于等于区间长度就直接减区间长度次直接回溯即可 | 对于一个非0区间，找到最小值看这个值和区间长度，选择最优的方式减，然后再重复这个过程递归下去，如果最小值大于等于区间长度就直接减区间长度次直接回溯即可 | ||
| + | |||
| + | =====G - Mercenaries===== | ||
| + | |||
| + | ====问题描述==== | ||
| + | |||
| + | n个元素，从中选若干个。第i个元素可以被选，当且仅当最终选出的元素数量在$[l_i,r_i]$。另有m组数不能被同时选出。问有多少种选法。 | ||
| + | |||
| + | ====数据范围==== | ||
| + | |||
| + | $1\le n \le 3\cdot 10^5,0\le m\le 20$ | ||
| + | |||
| + | ====解题思路==== | ||
| + | |||
| + | 运用容斥原理。若两个点不能被同时选出，则两个点之间连接一条边。枚举$2^m$种情况表示每条边上的两个点是否全被选中。若有奇数条边，则减去结果，偶数条边则加上结果。 | ||
2020-2021/teams/hotpot/codeforceser94.1598592075.txt.gz · 最后更改: 2020/08/28 13:21 由 misakatao
