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

2016年6月26日6,7137

「题目背景」

微露点滴沾衿落袖

丽日绰约轻解莲舟

蒹葭荣茂燕雀啁啾

白石溪畔斜阳逐流

——《白石溪》

「问题描述」

小奇喜欢在斜阳下的白石溪上泛舟。白石溪风光奇美，名花异石甚多，小奇在地图上标记了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

「样例输出」

「数据范围」

对于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即可

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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll ans;
int n,m,K,cnt,C;
int rt,sum,tot,top,delta;
int last[100005];
int f[100005],size[100005],dis[100005];
int q[100005],t[300005],cir[200005];
bool inq[100005],vis[100005];
struct edge{
	int to,next;
	}e[200005];
void insert(int u,int v)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
	e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}
int query(int x)
{
	if(x<1)return 0;
	int tmp=0;
	for(int i=x;i;i-=i&-i)tmp+=t[i];
	return tmp;
}
void add(int x,int val)
{
	tot+=val;
	for(int i=x;i<=2*C+n;i+=i&-i)t[i]+=val;
}
void getrt(int x,int fa)
{
	f[x]=0;size[x]=1;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa&&!vis[e[i].to])
		{
			getrt(e[i].to,x);
			size[x]+=size[e[i].to];
			f[x]=max(f[x],size[e[i].to]);
		}
	f[x]=max(f[x],sum-size[x]);
	if(f[x]<f[rt])rt=x;
}
void dfs(int x,int fa)
{
    q[++top]=dis[x];
	for(int i=last[x];i;i=e[i].next)
		if(!vis[e[i].to]&&e[i].to!=fa)
		{
			dis[e[i].to]=dis[x]+1;
			dfs(e[i].to,x);
		}
}
void solve(int x)
{
	vis[x]=1;
	for(int i=last[x];i;i=e[i].next)
		if(!vis[e[i].to])
		{
			dis[e[i].to]=1;
			dfs(e[i].to,x);
			for(int j=1;j<=top;j++)
			{
				if(q[j]+1>=K)ans++;
				ans+=tot-query(K-q[j]-2);
			}
		    while(top)add(q[top--],1);
		}
	for(int i=last[x];i;i=e[i].next)
		if(!vis[e[i].to])
	    {
			dfs(e[i].to,x);
		    while(top)add(q[top--],-1);
		}
	for(int i=last[x];i;i=e[i].next)
		if(!vis[e[i].to])
		{
			if(size[e[i].to]<K)continue;
			rt=0;sum=size[e[i].to];
			getrt(e[i].to,x);
			solve(rt);
		}
}
void div(int x)
{
	sum=n;f[0]=n+1;rt=0;
	getrt(x,0);
	solve(rt);
}
void getc(int x,int fa)
{
	if(cir[0])return;
	q[++top]=x;inq[x]=1;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa)
		{
			if(inq[e[i].to])
			{
				while(q[top]!=e[i].to)cir[++cir[0]]=q[top--];
				cir[++cir[0]]=e[i].to;
			}
			else getc(e[i].to,x);
		}
	top--;inq[x]=0;
}
void solvecir()
{
	getc(1,0);top=0;
	C=cir[0];delta=2*C;
	for(int i=1;i<=C;i++)cir[i+C]=cir[i];
	for(int i=1;i<=C;i++)vis[cir[i]]=1;
	for(int i=1;i<=C;i++)
	{
		vis[cir[i]]=0;
		div(cir[i]);
		vis[cir[i]]=1;
	}
	for(int i=1;i<=n;i++)vis[i]=0;
	for(int i=1;i<=C;i++)vis[cir[i]]=1;
	for(int i=1;i<=2*C;i++)
	{
		if(i>C)
		{
			vis[cir[i-C]]=0;dfs(cir[i-C],0);vis[cir[i-C]]=1;
			for(int j=1;j<=top;j++)add(q[j]+delta+C,-1);
			for(int j=1;j<=top;j++)
				ans+=tot-query(K+delta-q[j]);
			top=0;
		}
		dis[cir[i]]=1;
		vis[cir[i]]=0;dfs(cir[i],0);vis[cir[i]]=1;
		while(top)add(q[top--]+delta,1);delta--;
	}
}
int main()
{
	n=read();m=read();K=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read();
		insert(u,v);
	}
	if(n==m)solvecir();
	else div(1);
	printf("%lld\n",ans);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

ll ans;

int n,m,K,cnt,C;

int rt,sum,tot,top,delta;

int last[100005];

int f[100005],size[100005],dis[100005];

int q[100005],t[300005],cir[200005];

bool inq[100005],vis[100005];

struct edge{

int to,next;

}e[200005];

void insert(int u,int v)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;

e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;

}

int query(int x)

{

if(x<1)return 0;

int tmp=0;

for(int i=x;i;i-=i&-i)tmp+=t[i];

return tmp;

}

void add(int x,int val)

{

tot+=val;

for(int i=x;i<=2*C+n;i+=i&-i)t[i]+=val;

}

void getrt(int x,int fa)

{

f[x]=0;size[x]=1;

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa&&!vis[e[i].to])

{

getrt(e[i].to,x);

size[x]+=size[e[i].to];

f[x]=max(f[x],size[e[i].to]);

}

f[x]=max(f[x],sum-size[x]);

if(f[x]<f[rt])rt=x;

}

void dfs(int x,int fa)

{

q[++top]=dis[x];

for(int i=last[x];i;i=e[i].next)

if(!vis[e[i].to]&&e[i].to!=fa)

{

dis[e[i].to]=dis[x]+1;

dfs(e[i].to,x);

}

void solve(int x)

{

vis[x]=1;

for(int i=last[x];i;i=e[i].next)

if(!vis[e[i].to])

{

dis[e[i].to]=1;

dfs(e[i].to,x);

for(int j=1;j<=top;j++)

{

if(q[j]+1>=K)ans++;

ans+=tot-query(K-q[j]-2);

}

while(top)add(q[top--],1);

}

for(int i=last[x];i;i=e[i].next)

if(!vis[e[i].to])

{

dfs(e[i].to,x);

while(top)add(q[top--],-1);

}

for(int i=last[x];i;i=e[i].next)

if(!vis[e[i].to])

{

if(size[e[i].to]<K)continue;

rt=0;sum=size[e[i].to];

getrt(e[i].to,x);

solve(rt);

}

void div(int x)

{

sum=n;f[0]=n+1;rt=0;

getrt(x,0);

solve(rt);

}

void getc(int x,int fa)

{

if(cir[0])return;

q[++top]=x;inq[x]=1;

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa)

{

if(inq[e[i].to])

{

while(q[top]!=e[i].to)cir[++cir[0]]=q[top--];

cir[++cir[0]]=e[i].to;

}

else getc(e[i].to,x);

}

top--;inq[x]=0;

}

void solvecir()

{

getc(1,0);top=0;

C=cir[0];delta=2*C;

for(int i=1;i<=C;i++)cir[i+C]=cir[i];

for(int i=1;i<=C;i++)vis[cir[i]]=1;

for(int i=1;i<=C;i++)

{

vis[cir[i]]=0;

div(cir[i]);

vis[cir[i]]=1;

}

for(int i=1;i<=n;i++)vis[i]=0;

for(int i=1;i<=C;i++)vis[cir[i]]=1;

for(int i=1;i<=2*C;i++)

{

if(i>C)

{

vis[cir[i-C]]=0;dfs(cir[i-C],0);vis[cir[i-C]]=1;

for(int j=1;j<=top;j++)add(q[j]+delta+C,-1);

for(int j=1;j<=top;j++)

ans+=tot-query(K+delta-q[j]);

top=0;

}

dis[cir[i]]=1;

vis[cir[i]]=0;dfs(cir[i],0);vis[cir[i]]=1;

while(top)add(q[top--]+delta,1);delta--;

}

int main()

{

n=read();m=read();K=read();

for(int i=1;i<=m;i++)

{

int u=read(),v=read();

insert(u,v);

}

if(n==m)solvecir();

else div(1);

printf("%lld\n",ans);

return 0;

}

« 「NOI考前欢乐赛」小奇遐想 FJ2016集训 day7 »

小蒟蒻

黄学长，BZOJ3648 并不是这道题啊？？

猫猫

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

里奥内尔

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

hzwer

啥题挂了。？

O(n!)

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

ZXC

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

hzwer

这就是3648啊

hzwer.com _ Home | http://hzwer.com

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

分类目录

热门文章

Myfriends

近期评论