Mambacrose

ride or die

HNOI2015

| Comments

题目

http://pan.baidu.com/s/1i3CchlN
http://pan.baidu.com/s/1sj4upS5
省选被艹翻了,回来做了一天半,终于做完了,补一发题解。

upd:代码 http://pan.baidu.com/s/1EstNg

标准分

arthur

我们可以让轮游戏一起玩,这样我们就可以把题目转化为有个机会分给个人,考虑每个人被选的概率。

表示考虑完了第个人,还有次机会的概率,初始时

每次机会减少的时候累加答案即可。

fruit

我们可以用整体二分解决问题。

首先对于每个节点求出它的序区间,那么每个区间就是它的子树序区间。

考虑到每个盘子,能覆盖它的水果有两种情况。

  • 存在祖先关系。不妨设的祖先,那么能覆盖它的水果序一定满足如下条件。

  • 不存在祖先关系,那么能覆盖它的水果序一定满足如下条件。

这样我们把整个模型映射到二维平面上去,那么一个水果变成了一个点,一个盘子变成了一个矩形或两个矩形,整体二分答案为时,我们就只要统计每个点能被多少个权值为的矩形覆盖即可。

这样就转化成了经典问题,总复杂度

dishes

听说这是一道原题。

我们不妨运用逆向思维,先考虑最后一个位置是什么,一定是出度为的且字典序最大的点。

那么我们就可以反过来构图,拓扑排序每次选字典序最大的,再倒过来输出即可。

maple

考场上没去想这道题真是作死。

如果只是拓扑图的话,那么答案就是所有的入度之积。

加上一条边后,我们只要求出入度之积,再减去不合法的方案即可。

不合法的方案一定存在环,且环一定包含边。考虑到一条路径,那么要减去的答案就是

定义一条路径的权值为所有在这条路径上得点的入度逆元之积。

所以我们直接即可,令表示从的所有路径的权值之和。

复杂度

shop

考场上写了一个树链剖分+主席树水过去了。

对于题目中的每个询问

其中我们可以用前缀和搞一搞,那么我们就只要求

对于每个合法的,将到根的路径上的点,这样我们只要求到根的路径上的点权和即可。

所以我们按年龄前缀建主席树,每颗主席树维护每个点的权值,用树链剖分区间修改,区间求和即可。

虽然复杂度是,但是因为树链剖分常数很小,所以跑得很快。

pairwise

首先我们将具有等号关系的点缩起来,那么我们可以得到一个森林结构。我们搞一个超级根,就可以转化成一棵树。

表示的子树构成的合法序列的方案树,对于任意一个合法序列,我们可以想象为若干个号连接的若干段。

考虑合并,假设我们将合并,此时段,段,我们要合成段。我们可以想象成有个黑球,个白球,放在个位置中,有些位置可以放一个球,有些可以放一个黑球一个白球,那么方案数就是

这要我们就可以做到转移,但是只要合并即可,所以总复杂度

Comments

comments powered by Disqus