竞赛讨论区 > 中文题(DEFGJ)题解

中文题(DEFGJ)题解

头像
Shawnnnn
发布于 2020-09-14 21:10:47 APP内打开
赞 4 | 收藏 0 | 回复0 | 浏览253

合并序列

显然代价随着增加是递减的,于是我们可以二分。

对于给定的怎么计算答案呢?这是一个经典的哈夫曼树问题。

首先,我们先补一定个数的0。使得 n mod (k - 1) = 1。

然后每次合并最小的个即可。

我们维护一个队列,每次合并后把新产生的数扔里,然后选最小

的个时就在原数列和里选,因为显然也是单调不增的。

于是我们只需要排序预处理就可以了。

 

Minmax

因为区间的交还是一个区间,所以我们考虑枚举最终区间的交[L,R]。

然后统计li <= L且R <= ri的区间个数,令为tot个;

则将min(R-L+1, tot)去更新答案。

优化这个过程,我们可以只枚举右端点R,然后考虑对于每一个左端点L(L <= R),

维护出有多少区间包含[L,R],记为f(L)。

容易发现当R固定时,随着L增加,R-L+1是一个减函数,而f(L)是一个增函数。

所以min(R-L+1, f(L))的最大值,必然是取到这两个函数最接近的时候最优。

朴素的想法,我们可以二分L,找到最小的一个L,满足R-L+1 <= f(L),然后取L-1,L的信息去更新答案。

因为线段树本质也是一个分治结构的形态,所以对于二分答案的题,是可以直接在线段树上二分的。

具体来说,我们令T(L) = R-L+1 - f(L),这样T(L)是一个减函数,我们直接在线段树上二分找到对应的L即可。

当R增加的时候,我们时时维护一下线段树即可,需要支持区间加,区间询问最小值。

 

子序列

考虑计算每种子序列是否出现,为了避免重复计算,我们都只算第一个出现的。

令f[i]表示末尾为i的子序列的期望出现个数,枚举这个子序列下一个字符c。

然后枚举后面所有字符是c的位置x,那么f[i]转移到f[x]的概率就是,[i+1..x-1]中所有等于c的位置被删除的概率*第x个位置不被删的概率。

前缀和转移即可。

 

chess

打个表易得:

1. min(n,m)=1的时候答案为1。

2. Min(n,m)=2的时候答案为max(n,m)/2。

3. 否则答案为n*m。

4. 坑点在n = 3, m = 3 的时候答案是8。

5. 证明见https://apps.topcoder.com/wiki/display/tc/SRM+564

 

Tree

这道题要涉及求(ai,aj)以及(bi,bj)的距离,这两个变量还不好隔离;所以我们考虑先用点分将来简化一对,不妨考虑枚举(ai,aj)越过的重心,令Dep(x)表示x到重心的距离,则i,j之间的权值就变成了: Dep(ai) + Dep(aj) + Dis(bi, bj) 此时(i,j)之间相关的权值只和Dis(bi,bj)有关,剩下的是可以视为i,j的点权的,不影响答案。 接下来有两种方法。 第一种,我们可以再建立一棵点分树,每次合并时,就拿bj去点分树上询问一下权值最大的bi;然后将bj加入点分树即可。注意每次询问时,要求bi和bj在不同的分支上,所以我们需要对点分树上的每一个节点,记录两个属于不同的分支的最大值。 效率为:O(N \log^2 N)。 还有一种方法,我们发现将Dis(ai,aj)分离后,我们本质就是要求点集中带点权的直径;因为我们可以将Dep(ai)视为是bi点的点权。对于一个点集,实现加点后动态枚举直径,是有一个性质的;即距离一个点距离最远的点,必然是直径的两个端点,这个性质在带点权的时候同样正确。 所以我们是不需要用点分树来维护直径的;直接维护出直径的两个端点,每次加入点后,去直径询问一下,并更新即可。把LCA可以写成O(1)的,效率为O(N \log N)。

 

 

 

0条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐