almost 3 years ago

前言

快要省选了,来一波省选题。(中文题目题意就自己看咯)

chorus合唱队

难度的,设表示区间最后一次是插在左边还是右边的方案数。
chorus.cpp

planar平面图判定

由于平面图的边集,且题目里说了存在一条哈密尔顿回路,那么我们根据边之间的相交关系来连边,二分图判定即可。
planar.cpp

fsk物品调度

我们先考虑怎么生成序列
我们可以发现如果要以为第一关键字,为第二关键字,由于可以遍历个位置,那么必定满足,所以我们可以用并查集维护最近的可行的,确定了之后,再用一个并查集维护最近的可行的即可,这个的时间复杂度是均摊的。
接着就是经典问题了,首先考虑所有长度的置换环,如果包括那么对答案的贡献为,否则为,具体为啥就是因为我们可以利用把其他环给拆开,然后再还原回去,时间复杂度
(我的写法细节有点多= =
fsk.cpp

bus公交线路

我们考虑暴力的状压,只需要记录每种车辆的最后一个位置即可,然后由于每辆车是等价的,所以转化成一个长度为的二进制序列,又因为的最后一位一定是,因此状态数就是,于是我们矩阵乘法加速就好了。
bus.cpp

stone取石子游戏

说实话这道题挺玄学的,首先我们知道如果两边的栈和中间的双端队列都是单调的,那么我们可以直接贪心。
考虑对于栈,如果栈底的元素栈底元素的上一个,那么两个人都可以把这个留在最后根据奇偶性来取;
考虑如果栈和队列,如果满足,如果我们考虑计算两个人的差值的话,那么把这三个元素可以等价变形成,一直这样做就可以保证单调性了,最后排序贪心即可,时间复杂度是的。
stone.cpp

city城市建设

这是一道不错的题,首先我们考虑对询问分治,对于区间,把询问的边权设为无穷小,然后做,那么那些不在询问中的边,如果在中,那么无论如何也一定会在中了, 那么我们考虑把由那些边构成的联通块缩点, 这样我们就把点数降到的级别了,原因是询问的边权都是无穷小的,那么它们最多联通的点集。
然后把询问的边权设为无穷大, 做,那么如果还不在中的边,就一定不会出现在中了,因此我们可以删去那些边,这样边集的规模就和点数一样了,也是的,最后在的时候变更边权即可,时间复杂度是的。
city.cpp

bounce弹飞绵羊

裸题不解释。
bounce.cpp

matrix矩阵

玄学题,首先我们可以知道如果确定了第一行和第一列就可以确定整个矩阵。
为令第一行第一列为的矩阵的值,若矩阵从第行第列开始算的话,稍加证明我们就可以得到,那么我们枚举第一行,然后维护第一列每个元素的范围,如果矛盾剪枝即可。(知道真相的我眼泪掉下来)
matrix.cpp

后记

接下来就是咯。

← 又是一道数学题 HNOI2011 →
 
comments powered by Disqus