破坏发射台

By NanoApe，题解 By NanoApe

萌萌哒新人来水题大放送啦 >.<

算法一

枚举所有染色方案，一个个看是否符合要求。

复杂度 $O(m^n)$，期望得分 $8$ 分。

算法二

上一个做法太暴力了，我们会发现，第一个格子选第一种颜色的方案数等于第一个格子选第二种颜色的方案数，所以我们可以加点剪枝，利用最小表示法状态去重。

复杂度 $O(n!)$，期望得分 $40$ 分。

算法三

暴力做法已经没有什么可以优化的地方了，我们把它扔进垃鸡嘴里。

$n$ 为奇数的时候，我们设第一格的颜色为 A，然后设个一元二进制状态表示当前格的颜色是否为颜色 A。

设 $F[i][0..1]$ 表示第 $i$ 格的颜色是否为颜色 A 的合法方案数，然后递推一波即可。

复杂度 $O(n)$，期望得分 $32$ 分。

结合算法二，期望得分 $56$ 分。

算法四

算法三的转移可以用个矩阵来表示，然后就是在算法三的基础上套个矩阵快速幂即可。

复杂度 $O(log n)$，期望得分 $40$ 分。

结合算法二，期望得分 $64$ 分。

算法五

$n$ 为偶数的时候，我们设第一格的颜色为 A，设第 $\frac{n}{2}+1$ 格的颜色为 B，然后设个二元三进制状态表示第 i 格和第 $\frac{n}{2}+i$ 格的颜色是否为颜色 A 或颜色 B（$1 \leq i \leq \frac{n}{2}$）。

设 $F[i][0..8]$ 表示推到第 $i$ 格的所有二元三进制状态的合法方案数，然后递推一波即可。

复杂度 $O(n)$，期望得分 $48$ 分。

结合算法四，期望得分 $88$ 分。

算法六

和算法四的优化一样，你把转移写成矩阵然后矩阵快速幂即可，转移可以大力讨论。

复杂度 $O(log n)$，期望得分 $60$ 分。

结合算法四，期望得分 $100$ 分。

破坏蛋糕

By MemoriaIgnitus，题解 By C_SUNSHINE

算法一

对于两个特殊的情况（$n=3$和所有直线与$L1$或$L2$平行），有限的区域分别是三角形和平行四边形，求出这个三角形和平行四边形，在每一段上选关键点判定即可。

时间复杂度$O(n)$，期望得分25分。

算法二

对于每一段，我们取其上一个关键点（例如中点），则问题变成判断一个点所在区域是否为无限。

妈妈我会半平面交！

拉板子，每段$O(n \log n)$，惨啊只能做$n \leq 1000$。

算法三

我们把所有直线按照斜率排好序，排过序之后半平面交就是$O(n)$的了，那么考虑从一段走到下一段，发生了什么变化呢？

有一条直线的方向改变了，而且还是改变了$\pi$，我们把这一条直线拿出来插回去，就做到了每次排序$O(n)$，那么直接套模板似乎就能做$n \leq 5000$了。

然而半平面交有点卡常数？

我们考虑另外一种判定方法，把所有直线面向判定点一侧法向量的斜率拿出来极角排序，如果有两个相邻的法向量，他们的极角转过了超过或等于$\pi$，就说明出现了一个开口。这个区域就是无限的了。

于是判定一下子变得简单很多，$n=5000$就可以轻松做了。

算法四

相信说到极角排序后查看相邻的法向量，很多小朋友已经想到$n \leq 100000$怎么做了。

每次只修改了一个法向量，而且只需要检测相邻的法向量，于是这个事情完全可以用平衡树来做，事实上一个set足矣。写的时候注意转过一圈时的边界情况就好了。

参考代码http://uoj.ac/submission/94838

当然如果你怕被卡精度的话，你可以用向量来表示角度，所有的比较都可以分类讨论+叉积，这样就没有精度误差了。

参考代码http://uoj.ac/submission/94836

时间复杂度$O(n \log n)$，期望得分100分。

这是不是近几场UR中最Simple的一个B题了呢？

破坏导蛋

By ftiasch + jiry_2，题解 By jiry_2

算法一

考虑如何方便的判断一个点是否在三角形内。

在三角形内的限制可以看成要求满足与三条直线之间的位置关系，即要满足三个形如 $ax+by+c \leq 0$ 的不等式，分别带入判断一下即可。

对每组询问爆枚每一个点判断是否满足条件，时间复杂度 $O(nm)$，期望得分 $20$ 分。

算法二

坐标范围很小时，我们可以枚举点的横坐标把二维的限制降至一维，这样询问就变成了询问横坐标等于 $x$ 的点中纵坐标在某一个区间内的点数。对每一个横坐标预处理一下前缀和即可。

时间复杂度 $O(|x||y|+n+m)$，结合算法一期望得分 $40$ 分。

算法三

要同时满足三个 $ax+by+c \leq 0$ 不好处理，可以先只考虑一个限制。即给出限制 $ax+by+c \leq 0$，询问满足条件的点有多少个。

当 $K$ 很小时，可以把所有点按照 $ac+by$ 排序，满足条件的点一定是个前缀，二分一下即可。

现在考虑需要同时满足三个限制，我们可以使用 bitset。即对每一个限制求出每一个点是否满足条件，那么只要把三个 bitset and 起来再求其中 $1$ 的个数就好了。单个限制的时候依然是直接排序，然后维护一下前缀 bitset 即可。

这样的时间复杂度是 $O(Kn \log n+\frac{nm}{w}+m \log n)$ 的，可以接受，然而空间复杂度是 $O(\frac{nm}{w})$ 的，这就太大了。

我们可以对点集进行分块，每一块分别求解，假设块的大小是 $S$，那么时间复杂度是 $O(Kn \log n+\frac{nm \log n}{S}+\frac{nm}{w})$，空间复杂度是 $O(\frac{mS}{w})$ 的，调整一下块大小即可，结合算法一和算法二期望得分 $70$ 分。

算法四

算法三的瓶颈在于讲所有点按照 $ax+by$ 排序，即给出角 $\theta$，把所有点按照 $sin(\theta)x+cos(\theta)y$ 排序。

考虑两个点 $i$ 和 $j$，它们的权值相同时 $\theta$ 有两个取值 $\theta_1$ 和 $\theta_2$，它们把区间 $[-\pi,\pi)$ 分成了三部分 $[-\pi,\theta_1)$,$[\theta_1,\theta_2),[\theta_2,\pi)$。一共有 $n^2$ 对这样的点，所以区间 $[\pi,-\pi)$ 一共被分成了 $O(n^2)$ 段，所以不同的顺序也只有 $n^2$ 种。

把所有关键点排序，从小到大枚举 $\theta$，每一个关键点之后对序列的影响就是交换相邻的两个位置，这样前缀 bitset 还是可以维护的。主要要特判关键点重合（多点共线）的情况。同时离线按照斜率依次处理每一个询问，每一次到了相应的顺序时二分一下就好了。

直接做时间复杂度是 $O(n^2 \log n+m \log n+\frac{nm}{w})$ 的。

依然可以对点集分块，设块的大小是 $S$，那么时间复杂度就是 $O(S^2 \log n+\frac{nm \log n}{S}+\frac{nm}{w})$，期望得分 $100$ 分。

算法五

当然要去掉 bitset 也是可以的，不过细节会多一些。

询问一个三角形内的点数，可以拆成三个询问一条线段下方的点有多少个，这可以看成询问一条直线下方的点中横坐标在一个区间里的有多少个。

可以按照 $x$ 坐标排序然后分块，块内和算法四一样，多余的不超过 $\sqrt n$ 个点直接暴力就好了了。

这样时间复杂度是 $O(S^2 \log n+\frac{nm \log n}{S}+mS)$，期望得分 $100$ 分。

不过在这个数据范围内 bitset 部分只占了很少一部分的运行时间，主要还是在处理每一个块的部分和二分的部分，所以两个算法在运行时间上并差不了多少。

总而言之，这道题主要的思维难度还是在把 $n$ 个点分块上，这题也应该算是一道比较简单的 C 题了吧。