月度归档:2017年07月

BZOJ 3572: [Hnoi2014]世界树(虚树)

Description

世界树是一棵无比巨大的树,它伸出的枝干构成了整个世界。在这里,生存着各种各样的种族和生灵,他们共同信奉着绝对公正公平的女神艾莉森,在他们的信条里,公平是使世界树能够生生不息、持续运转的根本基石。
世界树的形态可以用一个数学模型来描述:世界树中有n个种族,种族的编号分别从1到n,分别生活在编号为1到n的聚居地上,种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连,道路的长度为1。保证连接的方式会形成一棵树结构,即所有的聚居地之间可以互相到达,并且不会出现环。定义两个聚居地之间的距离为连接他们的道路的长度;例如,若聚居地a和b之间有道路,b和c之间有道路,因为每条道路长度为1而且又不可能出现环,所卧a与c之间的距离为2。
出于对公平的考虑,第i年,世界树的国王需要授权m[i]个种族的聚居地为临时议事处。对于某个种族x(x为种族的编号),如果距离该种族最近的临时议事处为y(y为议事处所在聚居地的编号),则种族x将接受y议事处的管辖(如果有多个临时议事处到该聚居地的距离一样,则y为其中编号最小的临时议事处)。
现在国王想知道,在q年的时间里,每一年完成授权后,当年每个临时议事处将会管理多少个种族(议事处所在的聚居地也将接受该议事处管理)。 现在这个任务交给了以智慧著称的灵长类的你:程序猿。请帮国王完成这个任务吧。

Input

第一行为一个正整数n,表示世界树中种族的个数。
接下来n-l行,每行两个正整数x,y,表示x聚居地与y聚居地之间有一条长度为1的双
向道路。接下来一行为一个正整数q,表示国王询问的年数。
接下来q块,每块两行:
第i块的第一行为1个正整数m[i],表示第i年授权的临时议事处的个数。
第i块的第二行为m[i]个正整数h[l]、h[2]、…、h[m[i]],表示被授权为临时议事处的聚居地编号(保证互不相同)。

Output

输出包含q行,第i行为m[i]个整数,该行的第j(j=1,2…,,m[i])个数表示第i年被授权的聚居地h[j]的临时议事处管理的种族个数。

Sample Input

10
2 1
3 2
4 3
5 4
6 1
7 3
8 3
9 4
10 1
5
2
6 1
5
2 7 3 6 9
1
8
4
8 7 10 3
5
2 9 3 5 8

Sample Output

1 9
3 1 4 1 1
10
1 1 3 5
4 1 3 1 1

HINT

N<=300000, q<=300000,m[1]+m[2]+…+m[q]<=300000

 

感觉是虚树上dp的大boss,参考了hzwer的博客才明白怎么做。。。就算这样也调了半辈子。。。

首先肯定要把虚树建出来,但是因为虚树上并不都是关键点,还有关键点的LCA,所以需要先求出这些点的最近关键点才可以。这个两次dfs即可,一次从祖先更新子孙,另一次从子孙更新祖先。也算是个dp的过程吧。。

现在考虑不在虚树上的点,首先这些点一定在虚树上的某条边。枚举每条虚树的边,假如这条边为x->y,因为x的儿子边可能不止x->y,所以我们可以依靠倍增数组查到x->z->y这条边上的z,其中z是x的儿子节点。那么我们现在只考虑z->y这条链上的节点,以及挂在这条链上的不在虚树上的节点。那么肯定有个分界点mid,mid以上的节点归x,剩余的归y管理。

最后需要考虑从没有被讨论的节点。

 

BZOJ 3450: Tyvj1952 Easy

Description

某一天WJMZBMR在打osu~~~但是他太弱逼了,有些地方完全靠运气:(
我们来简化一下这个游戏的规则
有n次点击要做,成功了就是o,失败了就是x,分数是按comb计算的,连续a个comb就有a*a分,comb就是极大的连续o。
比如ooxxxxooooxxx,分数就是2*2+4*4=4+16=20。
Sevenkplus闲的慌就看他打了一盘,有些地方跟运气无关要么是o要么是x,有些地方o或者x各有50%的可能性,用?号来表示。
比如oo?xx就是一个可能的输入。
那么WJMZBMR这场osu的期望得分是多少呢?
比如oo?xx的话,?是o的话就是oooxx => 9,是x的话就是ooxxx => 4
期望自然就是(4+9)/2 =6.5了

Input

第一行一个整数n,表示点击的个数
接下来一个字符串,每个字符都是ox?中的一个

Output

一行一个浮点数表示答案
四舍五入到小数点后4位
如果害怕精度跪建议用long double或者extended

Sample Input

4
????

Sample Output

4.1250

n<=300000
osu很好玩的哦
WJMZBMR技术还行(雾),x基本上很少呢

一开始式子推错了,怎么都过不了样例。。。
设\(dp[i]\)为第i个字符的期望得分,设\(len[i]\)为第i个字符以’o’结尾的最长后缀期望长度。
设第\(i\)个字符为’o’的概率为\(p\)。
那么,\(dp[i]=p*(dp[i-1]+(len[i-1]+1)^{2}-len[i-1]^{2})+(1-p)*dp[i-1]\),\(len[i]=(len[i-1]+1)*p\)
然后直接dp好啦。。。bzoj真傻逼,保留20位小数居然wa。。。可能没有spj。。

 

BZOJ 3611: [Heoi2014]大工程(虚树+树形dp)

Description

国家有一个大工程,要给一个非常大的交通网络里建一些新的通道。
我们这个国家位置非常特殊,可以看成是一个单位边权的树,城市位于顶点上。
在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。
 现在国家有很多个计划,每个计划都是这样,我们选中了 k 个点,然后在它们两两之间 新建 C(k,2)条 新通道。
现在对于每个计划,我们想知道:
 1.这些新通道的代价和
 2.这些新通道中代价最小的是多少
3.这些新通道中代价最大的是多少

Input

第一行 n 表示点数。

 接下来 n-1 行,每行两个数 a,b 表示 a 和 b 之间有一条边。
点从 1 开始标号。 接下来一行 q 表示计划数。
对每个计划有 2 行,第一行 k 表示这个计划选中了几个点。
 第二行用空格隔开的 k 个互不相同的数表示选了哪 k 个点。

Output

输出 q 行,每行三个数分别表示代价和,最小代价,最大代价。

Sample Input

10
2 1
3 2
4 1
5 2
6 4
7 5
8 6
9 7
10 9
5
2
5 4
2
10 4
2
5 2
2
6 1
2
6 1

Sample Output

3 3 3
6 6 6
1 1 1
2 2 2
2 2 2

HINT

n<=1000000

q<=50000并且保证所有k之和<=2*n
一看sigma(k)<=2*n,那么肯定是建虚树了。。。
但是关键是dp不大好搞,得分两类点。我们dp求出maxx[i]为以i为根的子树中关键点到i的最大路径,minn[i]同理。sum[i]则是以i为根的子树中所有关键点的路径和。
那么转移就是:对于sum,考虑儿子y到父亲x这条边len的贡献是y子树中关键点个数乘上不在其中的关键个数。这样就可以转移了。
对于全局的最长路径,一定是儿子y的最长路径和y到x的边加上别的子树的一条最长路径,所以我们可以动态维护maxx[x]的过程即可。
对于全局最短路径同理。
对于关键点来说,minn[rt]其实是0,这样的话在dp的时候才是对的。同样非关键点的maxx[rt]初值应该是-inf,因为是不能以这个点为终点的。
调了好久,一开始是初值不对,后来看看数据发现size求错了。。。。