20180206 题目列表

2018-02-06 15:48:01 By youyl

NOIP2014 联合权值

https://www.luogu.org/problemnew/show/P1351

考虑距离为2的点对的时候考虑他们的中点

第一问很容易解决,在每个点上记录相邻点的最大值和次大值即可

第二问可以按照每条边分别计算对答案的贡献

NOIP2013 货车运输

https://www.luogu.org/problemnew/show/P1967

首先找出最大生成树

然后问题变成询问树上一条路径的最小值

用树上倍增解决

NOIP2015 运输计划

https://www.luogu.org/problemnew/show/P2680

先二分答案,假设二分的答案是t

长度小于等于t的路径可以直接排除,接下来就是在剩余路径的交集中找一条权值最大的路径进行改造

使用树上差分可以快速求出交集

NOIP2012 疫情控制

https://www.luogu.org/problemnew/show/P1084

先二分答案

可以看出让所有的军队尽量向上走一定是最优的。可以倍增求出所有的军队在mid的时间里最多走到哪个点。

对于所有走不到根的军队,它们就只能停在那里了。对于所有走到根之后还有剩余时间的军队,可以继续走到根的别的儿子上,这些军队成为可以调动的军队。

枚举根的每一个儿子,如果这个儿子所代表的子树已经被控制了,即子树中所有走不到根的军队已经可以控制了这个子树,就不用管它。

如果它代表的子树没有被控制(注意这里不包括经过这个子树走到根的点),那么称这个点为需要调入的点。

所有可调动的军队都有一个剩余时间,所有需要调入的点都有一个需要时间(即根到儿子的边的权),将这两种点分别从小到大排序,贪心地分配,就可以达到目的。

需要注意的一点是,所有能走到根的军队一定是从根的某一个儿子走上来的,如果再让这个军队调去这个儿子的话,不能计算时间。具体做法是从小到大排序后,如果当前军队走上来的那个点没有被控制的话,就让这支军队去控制它走上来的那个点,否则的话,让它去控制它能控制的最小的点。

NOIP2016 天天爱跑步

https://www.luogu.org/problemnew/show/P1600

将每条路径按照lca拆成两条链,考虑自下而上的那条链,设它为u->v

设di为点i的深度,那么路径上的点必须满足du-di=wi,即di+wi=du才可以收到u->v的贡献,问题转化成支持以下两种操作:1.给一条路径上每个点加入一个数x 2.查询一个点上有多少个di+wi

先用差分转化一下,将操作1改为在u处插入一个数x,在v的父亲处删除一个数x,那么操作2就变成了子树询问

通过dfs序将子树操作转化为序列操作,这时候可以使用可持久化数据结构来实现

如果不使用可持久化数据结构,就考虑离线,先把所有操作预处理出来,按照dfs序顺推,每到一个点就计算该点对应的询问

自上而下的那条链可以用类似方法处理

bzoj1787 紧急集合

http://www.lydsy.com/JudgeOnline/problem.php?id=1787

求出三个点两两lca,其中有两个相同,答案为另一个

codeforces 519E

http://codeforces.com/problemset/problem/519/E

设询问的点为A和B,分四种情况讨论

  • A=B:答案为n

  • A和B距离为奇数:答案为0

  • A和B到他们最近公共祖先P的距离相等:则答案为n减去A和B对应的P的儿子的子树大小

  • 其他情况:假设A的深度更大,找到A和B的中点M,答案为M的子树大小减去A对应的M的儿子的子树大小

评论

回复

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。