2020-2021:teams:hotpot:codeforceser94
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:codeforceser94 [2020/08/28 12:50] misakatao 创建 |
2020-2021:teams:hotpot:codeforceser94 [2020/09/01 20:21] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 53: | 行 53: | ||
| ====解题思路==== | ====解题思路==== | ||
| - | 分类讨论即可。若两个区间相离，可以枚举我们要操作其中i个区间。不多解释 | + | 先$O(n^2)$预处理出每个位置往后某个数有多少，然后枚举$i$和$k$，每次$k$移动的时候会变两个数，直接计算合法的对数，如果此时$a_i=a_k$就把数加进答案 |
| - | =====E - Calendar Ambiguity===== | + | =====E - Clear the Multiset===== |
| ====问题描述==== | ====问题描述==== | ||
| - | 一种历法，一年有m个月，每个月有d天，每周有w天。求数对(x,y)的个数，$x<y$且x月y号和y月x号的都是星期某。 | + | 给出$n$个数，每次可以把一个数任意减小但是不能减到负数，或者把一个所有数大于零的区间全部减一，问最少几次可以全变成零 |
| ====数据范围==== | ====数据范围==== | ||
| - | $1\le m,d,w\le 10^9$ | + | $1 \le n \le 5000$ |
| ====解题思路==== | ====解题思路==== | ||
| - | 等价于要求$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$ | + | 对于一个非0区间，找到最小值看这个值和区间长度，选择最优的方式减，然后再重复这个过程递归下去，如果最小值大于等于区间长度就直接减区间长度次直接回溯即可 |
| - | 枚举y-x，再等差数列求和即可。 | + | =====G - Mercenaries===== |
| - | + | ||
| - | =====F - Biocolored Segments===== | + | |
| ====问题描述==== | ====问题描述==== | ||
| - | 给定n个闭区间，每个区间有一个颜色t。从中取若干区间，要求任意两个颜色不同的区间没有交集为空。问最多取几个区间 | + | n个元素，从中选若干个。第i个元素可以被选，当且仅当最终选出的元素数量在$[l_i,r_i]$。另有m组数不能被同时选出。问有多少种选法。 |
| ====数据范围==== | ====数据范围==== | ||
| - | $1\le n \le 2\cdot 10^5$,$1\le l_i \le r_i \le 10^9$,$t_i\in \{1,2\}$ | + | $1\le n \le 3\cdot 10^5,0\le m\le 20$ |
| ====解题思路==== | ====解题思路==== | ||
| - | 每个区间建一个点。若两个区间不能放在一起，则连上边。本题等价于求这个二分图的最小割（去掉若干个点，剩余点两两不相连），也就等价于求这个二分图的最大匹配。 | + | 运用容斥原理。若两个点不能被同时选出，则两个点之间连接一条边。枚举$2^m$种情况表示每条边上的两个点是否全被选中。若有奇数条边，则减去结果，偶数条边则加上结果。 |
| - | + | ||
| - | 这个最大匹配我们可以贪心。首先按区间左端点排序。每次放入一个新点，删去原图中所有右端小于新点左端的点。找到与新点颜色不同的点中，右端最小的，和其进行匹配。 | + | |
| - | + | ||
| - | 设这个最大匹配是m，最终答案为n-m | + | |
| - | + | ||
| - | =====G - Directing Edges===== | + | |
| - | + | ||
| - | 不会，跳了 | + | |
2020-2021/teams/hotpot/codeforceser94.1598590250.txt.gz · 最后更改: 2020/08/28 12:50 由 misakatao
