「NOI考前欢乐赛」[BZOJ3648] 小奇泛舟

2016年6月26日6,5197
「题目背景」

微露点滴 沾衿落袖

丽日绰约 轻解莲舟

蒹葭荣茂 燕雀啁啾

白石溪畔 斜阳逐流

——《白石溪》

「问题描述」

小奇喜欢在斜阳下的白石溪上泛舟。白石溪风光奇美,名花异石甚多,小奇在地图上标记了n处景观(标号从1到n),有些景观通过溪流连接,这样的溪流有m段。小奇想知道,有多少种泛舟的路径,经过的景观数大于等于K呢?(小奇不喜欢一次泛舟重复经过一个景观)

「输入格式」

第一行包括3个整数,n,m,K。

接下来m行,每行2个整数u,v表示景观u和景观v之间有溪流连接。(保证输入无重边自环)

「输出格式」

输出一个整数表示答案。

「样例输入」

5 5 2

1 3

2 4

3 5

4 1

5 2

「样例输出」

20

「数据范围」

对于30%的数据n,m<=5000

对于100%的数据n,m<=100000

其中有50%的数据满足m+1=n,具体如下

测试点

前3个小数据 1树 2链 3环+外向树

后7个大数据 4-6树 7-8环 9-10环+外向树

题解

点分治练习 by hzwer

先把环拿掉剩下若干棵树,每棵树统计一下答案

即先用点分治处理一下每棵树内的路径

大概有快排和树状数组俩种做法

还要统计经过环的路径,那么我们沿着顺时针方向扫两圈,其实就是断开成链,复制一倍,记环的大小为C,现在变成一条场2C的链上面长了一些树

同样也可以用个树状数组,统计到第x棵子树,删去根距离与x超过C的树的信息,对x的每个结点t统计一次答案,即在树状数组中查询>=K-t的路径数,加入x的信息

对于一棵树的信息全部加上一个值,即随着从x->x+1,前面的树要多算一个x与x+1的链长,记录个delta,之后的每个值减去delta,查询时加上delta即可

当然树状数组换成平衡树线段树可以但是毕竟树状数组代码量比较小

 

avatar
5 Comment threads
2 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
6 Comment authors
小蒟蒻猫猫hzwer里奥内尔O(n!) Recent comment authors
  Subscribe  
提醒
小蒟蒻

黄学长,BZOJ3648 并不是这道题啊??

猫猫
猫猫

这题前面可以用线性DP代替点分治……
Claris大法好!

里奥内尔

你BZOJ上变成799题了!快去做题!

O(n!)

弱弱地问一句,这题可以点分治+FFT

ZXC
ZXC

Orz 贴一下BZOJ3648的代码
Orz~~~