破坏发射台
萌萌哒新人来水题大放送啦 >.<
算法一
枚举所有染色方案,一个个看是否符合要求。
复杂度
算法二
上一个做法太暴力了,我们会发现,第一个格子选第一种颜色的方案数等于第一个格子选第二种颜色的方案数,所以我们可以加点剪枝,利用最小表示法状态去重。
复杂度
算法三
暴力做法已经没有什么可以优化的地方了,我们把它扔进垃鸡嘴里。
设
复杂度
结合算法二,期望得分
算法四
算法三的转移可以用个矩阵来表示,然后就是在算法三的基础上套个矩阵快速幂即可。
复杂度
结合算法二,期望得分
算法五
设
复杂度
结合算法四,期望得分
算法六
和算法四的优化一样,你把转移写成矩阵然后矩阵快速幂即可,转移可以大力讨论。
复杂度
结合算法四,期望得分
破坏蛋糕
By MemoriaIgnitus,题解 By C_SUNSHINE
算法一
对于两个特殊的情况(
时间复杂度
算法二
对于每一段,我们取其上一个关键点(例如中点),则问题变成判断一个点所在区域是否为无限。
妈妈我会半平面交!
拉板子,每段
算法三
我们把所有直线按照斜率排好序,排过序之后半平面交就是
有一条直线的方向改变了,而且还是改变了
然而半平面交有点卡常数?
我们考虑另外一种判定方法,把所有直线面向判定点一侧法向量的斜率拿出来极角排序,如果有两个相邻的法向量,他们的极角转过了超过或等于
于是判定一下子变得简单很多,
算法四
相信说到极角排序后查看相邻的法向量,很多小朋友已经想到
每次只修改了一个法向量,而且只需要检测相邻的法向量,于是这个事情完全可以用平衡树来做,事实上一个set足矣。写的时候注意转过一圈时的边界情况就好了。
参考代码http://uoj.ac/submission/94838
当然如果你怕被卡精度的话,你可以用向量来表示角度,所有的比较都可以分类讨论+叉积,这样就没有精度误差了。
参考代码http://uoj.ac/submission/94836
时间复杂度
这是不是近几场UR中最Simple的一个B题了呢?
破坏导蛋
By ftiasch + jiry_2,题解 By jiry_2
算法一
考虑如何方便的判断一个点是否在三角形内。
在三角形内的限制可以看成要求满足与三条直线之间的位置关系,即要满足三个形如
对每组询问爆枚每一个点判断是否满足条件,时间复杂度
算法二
坐标范围很小时,我们可以枚举点的横坐标把二维的限制降至一维,这样询问就变成了询问横坐标等于
时间复杂度
算法三
要同时满足三个
当
现在考虑需要同时满足三个限制,我们可以使用 bitset。即对每一个限制求出每一个点是否满足条件,那么只要把三个 bitset and 起来再求其中
这样的时间复杂度是
我们可以对点集进行分块,每一块分别求解,假设块的大小是
算法四
算法三的瓶颈在于讲所有点按照
考虑两个点
把所有关键点排序,从小到大枚举
直接做时间复杂度是
依然可以对点集分块,设块的大小是
算法五
当然要去掉 bitset 也是可以的,不过细节会多一些。
询问一个三角形内的点数,可以拆成三个询问一条线段下方的点有多少个,这可以看成询问一条直线下方的点中横坐标在一个区间里的有多少个。
可以按照
这样时间复杂度是
不过在这个数据范围内 bitset 部分只占了很少一部分的运行时间,主要还是在处理每一个块的部分和二分的部分,所以两个算法在运行时间上并差不了多少。
总而言之,这道题主要的思维难度还是在把