2011 年各省省选选做

发布于 2018-10-21  196 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:2011 年各省省选选做

简单复习一下

详细题解和代码可以参见 Github

顺序按照各省字典序排序

[BJWC2011]禁忌

禁忌串的分割肯定是贪心地从前往后直接割是最优的,那么预处理转移,矩阵快速幂优化。

[BJWC2011]元素

排序后线性基贪心搞搞。

[BJWC2011]最小三角形

类似平面内最近点对的分治来做。

[BJWC2011]双端队列

注意到最后的操作是把所有的队列排序后得到一个非降的序列,那么也就是说,队列内部是有序的,且队列之间也是有序的,所以每一个双端队列都是原整数序列排序后的一段连续区间。
那么由于是双端队列,所以这个连续区间要求其关于原序列的位置编号是先下降再上升的。贪心地选取。
注意有数值相同的情况,把它们放在一起考虑,记录最大位置和最小位置来考虑。

[BJWC2011]神秘好人

线段树维护两边端点之间的最小值。

[BJWC2011]符环

考虑括号匹配的方式,把前后断开,那么前面只能多出未匹配的左括号,而后面只能多出未匹配的右括号,故设 F[i][j][k][l] 表示当前在第 i 格,前半部分多出来的未匹配的左括号为 j 个,后半部分多出来的未匹配的左括号为 k 个,右括号为 l 个。转移的时候呀,前面要求右括号不能超过左括号的个数,而后面的右括号优先与左括号匹配,否则才计入 l 中。最后枚举前面多多少个左括号统计答案。

[CQOI2011]分金币

设$C _ i$表示$i$给$i+1$的金币数,设每一个人最后得到的金币数为$S$,初始金币数为$A _ i$,那么对于第$i$个人有$A _ i+C _ {i-1}-C _ i$,设$x=C _ 1$,那么剩下的$C$都可以用$x$来表示,即$C _ i=x+\sum _ {j=2}^i A _ j-(i-1)S$,那么我们要最小化的就是$\sum |C _ i|$。相当于是多个一次函数取绝对值的和最小值,求出中位数即可。

[CQOI2011]动态逆序对

把时间也看作一维,求出删掉每个点减去的贡献, CDQ 分治。

[CQOI2011]放棋子

若知道了对于某一种颜色的棋子 x ,刚好占据 i 行 j 列的方案数为 $G[x][i][j]$ ,则若设 $F[x][i][j]$ 表示前 x 种金币刚好占据 i 行 j 列的方案数,可以得到一个较简单的 DP $F[x][i][j]=\sum _ {p,q}F[x-1][p][q] \times G[x][i-p][j-q] \times C[i][p] C[j][q]$ 。
如何得到 G[x][i][j] 呢,可以采用容斥的方式,有 $G[x][i][j]=C[ij][Cnt[x]] - \sum _ {p,q}G[x][p][q] \times C[i][p]C[j][q]$ 。

[HAOI2011]向量

有用的向量只有 (a,b),(a,-b),(b,a),(a,-b) 这四个,分别设四个的参数为 k,w,q,c ,可以得到两个方程 (k+w)a+(q+c)b=x,(k-w)b+(q-c)a=y ,根据裴蜀定理, 方程 ax+by=c 有整数解当且仅当 gcd(a,b)|c ,但是 (k+w) 有整数解并不一定代表着 k,w 也有整数解,对于 (q+c) 同理,那么要求 (k+w),(k-w) 同奇偶, (q+c),(q-c) 同奇偶,对于 gcd 讨论一下,四种情况只要有一种满足即有解。

[HAOI2011]防线修建

倒着做,相当于每次在当前的上凸壳上加上一个点。如果本来就被包含,就不用管理,否则加入这个点然后向两边弹出不合法的。周长可以实时维护。

[HAOI2011]problem a

通过每个人可以得到一个区间表示该区间内的人分数相同。那么问题转化为在若干个带权区间中选择不相交的若干使得权值之和最大。线段树优化 DP 。

[HAOI2011]Problem b

莫比乌斯反演。注意 n,m, 不同所以最好容斥一下。

[HAOI2011]Problem c

归纳可得,若记 Sum[i] 表示编号小于等于 i 的人的数量,当出现任意一个 Sum[i]<i 的时候,一定不合法。开始的时候没有编号的人可以看作是编号为 0 ,统计一遍编号已经确定了的人的前缀和,判断是否已经无解,否则一定有解。
接下来的问题就只要求合法方案数了,设 F[i][j] 表示编号小于等于 i 的人有 j 个的方案数,那么从 i-1 转移过来的时候枚举 k 表示有 k 人编号为 i 。注意这里 j 和 k 的枚举上下界, 由于 Sum[i] 要大于等于 i ,故 j 下界为 i 上界为 n ;记已经确定编号一定为 i 的人有 num[i] 个,则 k 的枚举下界为 num[i] 上界为 sum[i] 。转移的时候,由于没有确定的人都是相同的,所以要乘以组合数 C[sum[i]-j+num[i]-k][num[i]-k] 得到方案数,前面一项即代表的剩余自由人的数量,而第二项则是需要选择的自由人个数。

[HNOI2011]XOR和路径

直接求 xor 的期望无法做到很方便的计算,那么就对每一位分开来做。设为 1 的概率为 P[i] ,那么看边是 0 还是 1 建立方程,然后高斯消元。

[HNOI2011]任务调度

首先把在 A,B 都可以运行的确定一个运行位置,然后模拟退火,每次贪心得到解。

[HNOI2011]勾股定理

首先把合法的勾股数对拿出来,这不会太多。那么相当与是求一张图上独立集的个数。考虑如果是树的话,直接设 F[i][0/1] Dp 转移即可。但是在图上的话,先把图上的所有返祖边拿出来,暴力枚举这些边的两边是选择哪一个。
复杂度是假的,要知道图的独立集个数是 NP 的。

[HNOI2011]卡农

先把排列顺序考虑进去,设 F[i] 表示当有 i 个片段时的方案数。因为当前 i-1 个片段都确定的时候,由于要求任意每一个音阶的出现次数为偶数,所以第 i 个其实是确定的。若不考虑第 i 个与之前的重复或者第 i 个为空集的情况, 记 $N=2 ^ n-1$ ,则 F[i]=A[N][i-1] 。
然后要把上面提到的两种不合法情况减去。首先是空集的情况,意味着 i-1 个片段已经满足了每一种的出现次数都为偶数,即 F[i-1] ;然后是第 i 个与前面 i-1 个重复的情况,因为两者一样,所以同时去掉两个之后,依然满足每一种的出现次数为偶数,即 F[i-1] 。与 i 重复的那个元素有 i-1 个位置可以放,同时有 N-(i-2) 中集合的选择。所以综上可以得到递推式 F[i]=A[N][i-1]-F[i-1]-F[i-1] * (i-1)(N-i+2) 。最后再除以 m! 就是除去顺序的方案数。

[HNOI2011]括号修复 / [JSOI2011]括号序列

Splay 搞搞

[HNOI2011]数学作业

分段矩乘

[HNOI2011]数矩形

把每一对点放在他们的中点上。枚举中点,把距离中点相同的枚举一下,组合答案。

[HNOI2011]赛车游戏

乱搞贪心。先把假设速度为 0 的费用算了,然后用堆每次取出一个最小的速度,把它提到与第二小一样,然后合并。

[JLOI2011]飞行路线

分层图最短路

[JSOI2011]序的计数

首先把 K 个点单独拿出来,并全部连向一个虚拟节点 K+1 ,这样强制 K+1 为第一个走的点就可以得到所有的 dfs 序了。设 F[i][S] 表示当前在 i ,经过的点集为 S 的 dfs 序数。由于 dfs 转移的时候,进入一棵子树,如果需要回溯的话一定是从这棵子树里转移出来了,那么提前预处理 G[i][S] 表示当前在 i ,经过的点集为 S ,接下来要经过的点的集合是哪些。转移的时候,进入子树就直接从 G 得到转移的系数。需要注意的是,当某棵子树内存在连向不在 K 个点中的边时,不能再向外转移,因为此时是不能回溯的。

[JSOI2011]柠檬

如果一个位置要与前面合并,一定是选择与当前颜色一样的最优。有方程,$F[i]=max(F[j]+A[i] * (S[i]-S[j]+1)^2)\quad$ 其中A[i]是i处的大小,j是i前面一个与i同大小的柠檬
由于$S[i]$都是非负的,所以我们可以发现,当决策点$j$不动的时候,随着$i$的增大,$(S[i]-S[j]+1)^2$这个值会增长得越来越快。由于二次函数的性质,S[j]更小的j虽然一开始可能比更大的j劣,但它增长得更快,所以决策点是向左移动的。

[JSOI2011]分特产

考虑容斥,所有同学都至少有一个的方案数=总方案数-至少有一个没有+至少有两个没有-至少有三个没有。计算至少有 i 个没有的时候,从 n 个同学中选出 i 个人,即 C[n][i] ;把每一种特产 num 分成可以为空的 n-i 组,方案就是 C[num+(n-i)-1][n-i-1] ,累加计数。

[JSOI2011]棒棒糖

区间众数,那么离线下来枚举右端点维护左端点的答案。

[JSOI2011]任务调度

可并堆模拟一下。

[SCOI2011]地板

考虑一个 L 型,转换成插头相当于若干横向插头+竖插头,然后中间一个转折点。那么先把列交换成小的那一维,然后插头 DP ,每一次有 m 个纵向插头和一个横向插头,设 0/1/2 分别表示没有插头,有一个未转向的插头和有一个已经转向的插头,讨论 6 种情况转移。

[SCOI2011]棘手的操作

可并堆搞搞

[SCOI2011]糖果

差分约数的做法实际上是假的,因为 spfa 复杂度太高。正确姿势是先把有等于号的边连上,tarjan 缩点得到应该相等的点,然后再连边 DAG 上 DP 。

[SCOI2011]飞镖

分类讨论题,首先讨论不包括红心的情况。
可以证明,如果前两张牌是 2a+3b 的形式,可以凑出 [1,2a+3b] 中除了 2a+3b-1 的所有数,同时若让第三张尽量地大,那么就判断能否用这种方式凑出来 x-2k 。然后如果还需要更大,只能是 3a+3b 的形式,这样一定是 3 的倍数,枚举最后那个 2k 的最大的 k 满足使得 x-2k 是 3 的倍数,若此时 x-2k<=6k ,说明有解。
然后把红心考虑进去,总共分为六种情况。
第一类:m,i,i 和 2m,i,i ,首先减去 m/2m ,剩下的转换为判断 i,i 其中要求一个是 2 的倍数,那么类似上面,判 2a+3b 的形式
第二类:m,m,i 和 m,2m,i 和 2m,2m,i ,首先同样还是减去若干个 m ,然后判断剩下的 i 是否是 2 的倍数。
第三类:i,i,2m,减掉 2m 后,剩下的判 2a+3b 或 3a+3b
第四类:m,i,2m 和 2m,i,2m,减去 m 的相关项,剩下的判断是否小于等于 K ,否则是否是 2 的倍数并小于等于 2K ,否则是否是 3 的倍数并小于等于 3K 。
第五类:m,m,2m 和 m,2m,2m 和 2m,2m,2m ,直接判断是否为 4m,5m,6m 。

[SDOI2011]打地鼠

行列分开,对每一行和每一列单独求出可行的最大解,然后求出行和列分别的 gcd 即为答案。因为如果 i 有解那么 i 的约数也一定有解,并且反过来能成为解的一定是最大的可行解 x 的约数。求的时候,枚举宽度或长度,然后从第一个位置开始构造,前缀和得到每一个的操作次数,从而判断是否合法。

[SDOI2011]计算器

快速幂+逆元+BSGS

[SDOI2011]染色

树链剖分+线段树,注意一下标记合并的顺序

[SDOI2011]拦截导弹

每一个导弹被消除的概率就是在所有合法方案中,它出现的次数/总方案数。那么求出包含每个点的方案数。由于转移是个 DAG ,相当于是求经过某一个点的路径条数,那么前后两边二维数点求和再求积。

[SDOI2011]工作安排

费用流建模

[SDOI2011]黑白棋

题目需要加上限制 A 只能向右移动, B 只能向左移动。那么由于 A,B 是相间的,每一对黑白棋子可以看作是一个石子堆,每次相当于是在最多 D 堆石子中选取,由 Nimk 游戏知道,先手必败当且仅当石子堆的二进制的每一位之和都是 D+1 的倍数。那么现在的问题就是选出若干堆石子使得二进制的每一位之和都是 D+1 的倍数。
动态规划,设 $F[i][j]$ 表示现在从低到高 DP 到第 i 位,已经选择了 j 枚石子使得二进制每一位之和都是 D+1 的倍数的方案数,枚举一个 k 表示这一次要让 k(d+1) 堆石子在这一二进制上有 1 ,那么这样就可以满足限制。由于石子是无序的,所以需要乘以一个组合数 C(堆数,这一次选择的堆数) 。
最后统计答案。注意在中间的计算过程与最后统计答案的时候要时刻注意不能超过石子数的上界 n 。这样得到的就是先手必败的方案数,用全部的方案数 C(n,K) 减去必败的就是先手必胜的了。

[SDOI2011]消防

看到这种树上路径最值就要想到直径。
可以证明是放在直径上,然后尺取区间,两边的相当于是取树中最深的,而中间则是取区间最大值,两边的可以提前预处理一下,而中间的就可以用单调队列来维护了。

[SDOI2011]保密

最优化比值,那就分数规划。
但是不能直接分数规划,因为求的是若干个比值的和最小。但同时注意到每个出入口的答案是独立的,那么就分别分数规划+最短路求出到达每一个出入口的最小危险性。然后问题就转化为一个二分图,求最小权点覆盖。费用流建模即可。

[SDOI2011]消耗战

如果是单次询问就树型 DP 即可。多次询问就建出虚树 DP 。

[SHOI2011]双倍回文

一个回文串要求双倍回文也就是说其一半的地方也应该是回文串,增量构建回文自动机,同时维护 fail 树的倍增数组,找到长度为一半的地方看是否存在这样的回文串。

[TJOI2011]书架

容易想到一个 $O(n^2)$ 的 DP ,设 F[i] 表示前 i 本书的最小层宽度之和,则 F[i]=min(F[j]+max(Bk[j+1..i])) 。每一次增量一个点,相当于是修改前面某一段区间的最大值,然后求这个最大值与 F 的和区间最小值。用线段树来维护这个信息,每个节点维护 mnkey 表示区间最小答案,mn 表示区间最小的 F 值,lz 表示区间最大值覆盖懒标记。而需要更新的区间可以用一个单调队列得到。

[TJOI2011]树的序

直接建立出二叉搜索树的最坏复杂度是 $O(n^2)$ 的,由于这里要求生成序列的字典序最小,所以考虑直接构造出解。同样的一棵二叉查找树的中序遍历是相同的,那么就把序列按照键值排序,以原下标作为小根堆参数,构建笛卡尔树。由于笛卡尔树的中序遍历已经能够满足与原二叉查找树相同,那么笛卡尔树的先序遍历就是最小的生成序列。

[ZJOI2011]最小割

最小割树

[ZJOI2011]看电影

根据概率=合法方案/总方案,首先可以知道总方案是$K^N$,那么关键在于如何求出合法方案。
考虑添加一个空座位使得所有的座位成为一个环,那么方案数为$(K+1)^N$,由于是环,每一种方案被算了$K+1$次,所以要除掉一个$K+1$,即$(K+1)^{N-1}$。再从环中去掉一个空座位变成一个合法的序列,环中有$K-N+1$个空座位,那么就是$(K+1)^{N-1}(K-N+1)$,所以答案为$\frac{(K+1)^{N-1}(K-N+1)}{K^N}$。由于$K,N$均不超过$200$,所以直接分解质因数,然后再高精度求积。

[ZJOI2011]礼物

枚举行列相同的那一维是哪一个面,然后单调队列得到每一个点的最大延伸宽度,接下来的问题就是求序列上区间长度乘以区间最小值最大了,求出每一个值的最大值覆盖范围,这个也可以单调队列,然后组合但。

[ZJOI2011]细胞

质量的限制实际上是没用的,因为不会有相同的情况发生。
先考虑如果最后分出来 m 个小球,有多少种断链的方式。设 F[i][0/1] 表示前 i 条链,第 i 条链是否断开的方案数,则容易得到递推 F[i][0]=F[i-1][1],F[i][1]=F[i-1][0]+F[i-1][1] ,合并一下得到 F[i][1]=F[i-1][1]+F[i-2][1] ,最后需要的便是 F[n-1][1] 因为最后的一定要割,发现其实就是斐波那契数。
如果设 Fab[1]=Fab[2]=1 ,则答案就为 F[m-2] ,因为两边的是一定要去掉的。
但是,由于不知道 m ,而直接求 m 的话方案数过大,甚至无法用矩阵快速幂,所以考虑一位一位地进行,设 G[i] 表示从高位到低位的第 i 位,则枚举前面的一个 j-1 让 [j..i] 形成一个在第一次分裂中的完整的数,则 $G[i]=\sum G[j-1] \times Fab[num _ {j..i}]$,关键就在于 $Fab[num _ {j..i}]$ 怎么求,可以预处理一个十进制的斐波那契矩阵以方便快速幂,让 j 从 i 枚举到 1,这样实时维护 j..i 的值,每次移动 j 的时候相当于补充一个最高位,直接作快速幂。
需要注意,由于矩阵乘法不具有交换律,所以要时刻注意矩阵的乘法顺序。
为了方便最后不要求 n-2 ,可以把 G[0] 设置实际的 G[1] 的 -2 次方为 $[1,1] ^ {-2}$ 即 $[1,0]$。

[ZJOI2011]营救皮卡丘

只能从小标号走到大标号,这个构成了一个 DAG 。预处理两点之间只经过不超过当前标号的点的最短路,在这个图上跑费用流。

[ZJOI2011]道馆之战

类似堵塞的交通的做法,线段树维护两边端点之间的连通性以及最长路,同时维护两边端点能延伸出去的最长距离,这样就可以得到最长路了。由于是在树上的,所以再套一个树链剖分。

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:2011 年各省省选选做


HNCJ OIer