此博客停更

这个题解我是在你们做这套题的时候写的♪(^∇^*)

先讲第二题吧-。- 原题是bzoj4080

首先如果有人这题没分。。

。。。。。。。。。。。。。。

好，我们来看前60%的数据，$n<=15$，这个东西只要$2^{15}$枚举就行了我不多说

对于100%的数据，有很多种做法-。-，不知道你们认不认识我给你们的关怀里的那个 “大力”

先讲讲我当时的做法，当时不会做啊~~，我记得当时写了暴力各种乱搞还是T到死，然后看到了数据范围 $n<=100$，这个数据范围我们就可以进行各种shi法

考虑一个肯定错的贪心：初始标记所有肥皂都可拿，然后能拿就拿，拿到一个就把和它距离$>d$的肥皂标记为不可拿

考虑这个贪心能对的情况，便是存在一个拿的顺序使得它能对，于是我们随机化这个顺序，多做几遍……命中率真的很高

至于贪心部分，我们可以用bitset做到$\frac{n^2}{32}$，所以总的复杂度就是 $O(k·\frac{n^2}{32}) (k为随机次数)$

好现在问题来了，有木有什么靠谱的做法！

其实这个东西可以转化成用一个直径为d的圆覆盖尽量多的点

对于一个点数大于等于二的点集，可以移动圆使得刚好让两点在圆上，于是就有了一个n^3的做法：枚举两个点，以他们在直径为d的圆边上作圆，再O(n)判有哪些点在圆内，这个东西只要找到圆的中点就行，于是三角函数乱搞即可√，具体见-->传送门

复杂度：O(n^3) 或 O(n^2\log n)

但是题目卡精度，所以这个做法只能过80分-。- lalalalalala

上面那些不算，是比利把我口胡住了，上面那个 是错的，可以用等边三角形叉掉，其实有一个$O(n^3\log n)$的做法。。但是写起来很麻烦就不说了~而且会被精度卡

那么有没有什么不会被精度卡的靠谱的做法呢？

有！但是这个做法等你们学会了网络流就能看出这个其实是个最大独立集问题，现在不予多说_(:зゝ∠)_

总结一下：随机化大法好！

第4题 （就是不告诉你原题）

单看数据范围我不会做，但还好每个数据点都有限制信息

对于$n=1$需要按y坐标排序去重，再把剩下空着的格子破坏。

对于$m=1$只要看k是否$>0$就行了

对于$3,4,5$三个点，只要$2^{n·m}$暴力就行

对于$6,7,8$三个点……我tm还真不会=。=|||，如果有会的求教_(:зゝ∠)_

对于$k<=1000$，可以把已经破坏的点当成图上的点，点与点之间的距离是横坐标差的绝对值和纵坐标差绝对值的最大值-1（自己yy一下），然后只要最左边到最右边能阻断从上到下就行了，于是把两边都当成点，一个是起点一个是终点，图构好直接跑最短路就行-。- 复杂度$O(k^2)$

对于$n,m<=1000$，不能用上面的做法，但其实道理是一样的，考虑从左边走到右边，走到没被破坏的点上代价是1，走到已经被破坏了的点上代价是0，然后这个直接上spfa也可以，bfs也可以，我没写过spfa，所以如果有人被卡了请和我说，我帮你看，复杂度$O(n·m)$

总结一下，这题不难，考验的是你们分数据段拿分的能力，如果这题有人没分-。-。。。。

。。。。。。。

p.s.毒瘤比利的 t1+t3 的题解-->http://hzq84621.is-programmer.com/posts/193345.html

loading...