9.7.18 考试小记

发布于 2018-07-09  2.05k 次阅读


T1

给定一个nxn的网格,规定(x+y)&1的位置权值非负,否则一定为0,现在可以向图上放L形的石头,同时石头的任意部分不得与其他石头或者障碍重叠,且一块石头能删掉拐角处的数,求图上的最小总权值。

我们考虑用最大费用可行流来解决问题,令奇数列的0格向四周连边,S向奇数列的0格连边,偶数列的0格向T连边,然后处理拐角就好了。

考场上队列的数组开小了,挂了不少分。另外增广的时候要增广到权值非负。

 

T2

一棵n个点的树,每次选择c(<=5)个点(可能相同),使得这些点都走到LCA处,且每个点都选取路径上的一些颜色,要求每个点选出的颜色个数相等且互不重复,求最大的选出的颜色数(<=1000)。

首先,根据hall定理,一个左侧有n个点,右侧有m个点的二分图存在完美匹配,满足任意k个点在右边都有k个点与之相邻。那么,我们就让左侧有i*c个点,右边有m个点,只需求出在c的任意子集中,所有可以到达的颜色的并集大小比上这个子集的大小的最小值,就是答案了。

对于这个东西,我们可以先树剖,用Bitset维护出每个点到达链顶的信息,按照DFS序建出线段树并维护区间信息,这样就可以单次O(logn*m/w)地查询一个点到某个祖先路径上出现的颜色了。

之后,我们再用Bitset搞搞就过了。

 

T3

给出一个长度为n的字符串,同时每个位置都有权值v(非负),求出所有满足权值之和等于排名(降序)的子串的左右端点。

首先,如果我们枚举左端点,右端点向右移动时,排名单调递减,且权值之和单点不降,因此做差之后函数单调递减,我们可以二分判断是否存在零点。只需做到O(logn)算出特定子串的排名,即可O(log^2n)查询零点。我们可以考虑每个排名的后缀对于本质不同的子串产生的贡献,然后二分出合适的位置,问题就解决了。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974