一些捉不起的题集锦

以后的学弟学妹可以省去找题解的烦恼。

第K大乘积

给出一个长度为N的整数序列,求在从中选取M个数的所有方案中,第K大的乘积是多少?

显然可以分选0个负数、2个负数、……、2k个负数来讨论吧。
要找一个好的方式可以使每一个方案被唯一扩展出,思考一下,我们可以平移一段连续的后缀。可以证明,这是很优秀的扩展方案。

之后就写个堆乱搞一下就行了。

最大凸包

平面上有N个点,求面积最大的一个内部不含其他点的凸包。

四方DP可以过的。
枚举底端顶点,目的是防止第一条边和最后一条边凹进去。然后F[i,j]表示 < i ,j > 是凸包最后一条边的最大面积,暴力转移即可。

激光强度调节装置

给定一无向带权图,求两两点对间不同的最大流流量。

裸的Gusfield直接上。

五彩斑斓

给定一个N * M的棋盘,现在有一个对其中每个格子的染色方案,你需要求出最少的染色次数使得能够染出给定样式的棋盘。

这题有几个性质需要注意。

第一点:至多染色N+M-1次。
第二点:将未染色的那一列作为初始条件,如果条件不满足一定没有合法方案。

证明脑补一下。这里就说一下怎么判断有无可行解,假设当前假设第x行未染色,那么第i列的染色就与Col[x,i]相同,对每个非x行的各自进行枚举,如果颜色与当前列不一样且当前行未染色,则将当前行染成该色。若当前行染色也与该色不同则无解。若当前格子无色但行或列有色无解。最后将N+M个行列建成N+M个点,当一个点所在行列染色不同时,颜色为行的颜色就加一条列到行的边,vice versa.

彩色圆环

给定一个长度为N的环,用M种颜色染色,每种颜色在每个位置均等概率出现,对于每种方案的贡献是各段长度之积。求期望贡献。

简单DP。F[i,j]表示前i个最后一段连续j个且最后一段颜色与第一段相同的期望, G[i,j]表示前i个最后一段连续j个且与第一段不同的期望。答案就是。转移就很显然了。为什么不用考虑段首段尾颜色相同的例子?我们总是可以把它平移到一种不同的方案,使得个数唯一确定。

O(N)的优化也比较可想,可以发现第二维状态可以优化。然后就没有然后了。

矩阵

给定集合,你需要分配权值,求

最小割经典模型,这题巧妙在对第一个和式的转化,两元素在相同集合有贡献比较好做,将贡献事先累加,在算割时减去即可。但是这题是当且仅当在S集合才有贡献。这该怎么搞呢?实际上把费用U double一下,S到i连U的流量,S到j连U的流量,i到j和j到i连U的流量,这样的建模显然是满足条件的。

小A的树

给定一个带点权的树,询问任意两点路径的期望and、or、xor值。

这题比较傻逼,直接按位treedp记录当前and(xor,or)值为0或1的点的个数,乱搞一下。

小B的涂色方案

你得到了一个长度为N的环,每个点你可以染上M种颜色,要求相邻2个珠子颜色不同,且M种颜色都得用上,求本质不同的方案个数。

这题比较有意思。全面考察了对Polya和容斥的运用。

首先我们发现要求M种颜色全用上这个限制很难搞,不妨放宽限制。想想要求两个相邻珠子不同。对在旋转置换下的项链,颜色肯定是一段一段重复出现的,我们只需要对这一段处理即可。因为是环,所以可以设F[i,0..1]分别表示是否与第一颗珠子同色,这个可以矩阵快速转移。思路就很清晰了,容斥颜色数。现在子问题变为有K种颜色去染长度为N的环,在各个旋转变换下不变的置换总数。可以发现旋L格循环节个数为gcd(L,N),但是枚举N铁定TLE。咋整呢?枚举N的约数D,小于等于N的与一个数gcd为D的数的个数为phi(N/D),对于循环节个数为X的染色方案数为F(X,K)。

时间复杂度

小C的填数游戏

题意较长就不简述了。

方法是维护一棵线段树,线段树节点维护的信息是一个4 * 4的状态,分别表示当前区间前段选择情况为s1,后段选择情况为s2的最优值。合并的时候分类讨论下长度为1的就行了。

疯狂赛车

给定一个折线赛道,赛道之外的地方是沙地,赛道不自交,在赛道上行驶速度为,在沙地行驶速度为,求从起点到终点的最短时间。

求导后可知一点到另一条线段的最优点,将折点间的边、点到对应边的最优点的边、一条直线上相邻点的边连接起来Dijkstra+堆即可。

剪刀石头布

给定一个竞赛图,其中有些边未定向,你需要寻找一个定向方案使得图中的三元环数量最多。

补集转化。
与其求三元环,不如求非三元环。
那么什么是非三元环呢?

因为是竞赛图,非三元只能是在任意一个(A,B,C)中,有且仅有一个点在子图中入度为2。
所以答案就是

接下来我们的任务就是使得最大就是了。给每条边定向搞一个费用流就可以了。注意到费用是凸的,直接拆边即可。