https://codeforces.com/contest/1199
虽然我打的是$\rm Div. ~2$但是因为$\rm Div. ~2$前两题实在是太水了这里就不说了。。
不过涨了一百来rating还行（我果然分还是太低了）
A. MP3
算出可以接受的最大种类数然后对着题意模拟吧。。
1 |
|
B. Welfare State
好像有$O(n)$的做法但是我直接拿线段树暴力模拟了。。
1 |
|
C. Matching vs Independent Set
我们把边全连起来同时暴力的找到一个匹配，也就是每次判当前这条边能不能用，如果能就打个标记顺便标记下两个点。
那么如果匹配数$\geqslant n$就做完了，否则一定只有小于等于$2n$个点被标记了，剩下的就是独立集。
1 |
|
D. Rectangle Painting 1
大水题。。直接$dp$就好了。
$f_{x1,y1,x2,y2}$表示当前矩形的答案，显然每次要么把这个矩形涂满要么剖成两半转移。
我写了个记搜结果跑的好慢啊。。。不过记搜是真的好写。
1 |
|
E. Rectangle Painting 2
这差不多就是原题了吧。。可以参考一下：[HNOI2013]消毒。
思想就是每次消一整行或一整列，那么如果$n$不大，我们可以建二分图，左边表示每行，右边是列，每个黑点就弄一条边连向对应行列，答案就是最小点覆盖。
$n$大的话离散化之后就变成了有点权的点覆盖，可以用最小割做。
1 |
|
F. GCD Groups 2
大神题。。我弄了挺久才弄明白。
首先注意到一个数最多只有$k=9$个质因子。
假设我们现在知道了$a,b$在不同的集合，那么我们可以考虑消除每个质因子的影响。
那么可以直接$dp$，设$f_{s,t}$表示左边集合$k$个质因子状态为$s$，其中$0/1$表示有没有被消除，右边为$t$。
那么每次枚举状态，枚举当前数放左边还是右边就好了。
这样$dp$复杂度是$O(2^{2k}\cdot n)$的。
注意到我们一个集合至多只有$k+1$个有用的数，也就是说我们可以把其中的一个集合缩减到$k+1$个数，其他的扔到另一个集合里，方案仍然合法。
所以如果我们任选$a,b$，错误的概率为$\frac{k+1}{n}$。
所以我们直接随机化这个算法，期望只需要做$O(\frac{n}{n-k+1})$次，因为$k$是常数所以这就是$O(1)$次。
那么我们得到了一个$O(2^{2k}\cdot n)$做法。
考虑怎么优化，显然对于一个质因子至多只有$k$个数是有用的，那么一共只有$k^2$个数有用，剩下的都可以随便放。
所以总复杂度为$O(2^{2k}\cdot k^2+n)$。
1 |
|