[国庆集训]Day3解题报告

发表于 | 阅读次数：

题目链接

戳我n(≧▽≦)n

T1

这题实际上并不难（我就是没打出来），只不过需要能够发现其中的奥妙就可以了。

我拿到这题时首先想的是状压DP，然后自己瞎打一通

1
2
3
4
for (Re S=1; S<(1<<K); ++S)
	for (Re i=1; i<=N; ++i)
		for (Re t=head[i];t;t=e[t].next)
			f[e[t].to][S|pd[e[t].to]]=min(f[e[t].to][S|pd[e[t].to]],f[i][S]+e[t].w);

嗯。。。打了这么一个东西，后来发现这是错的。。。

并不能说我没想过正解的做法，只不过是被我迅速否定了。

接下来讲讲正解：

实际上我们很容易注意到$K \le 5$这个条件，肯定就是在这上面做文章（傻*才想状压）。

所以我们可以考虑先做$K$遍的SPFA预处理出K个超市到各个地方的距离。

预处理后又有什么用呢？

我们考虑任意一个起点$u$（$u$不是超市），对于$u$来说，肯定是走到这$K$个超市中的某一个，然后走到其他几个超市（可能经过自己），最后再从某个超市回来。

所以呢，我们可以考虑再预处理一个数组$f[i][j]$，表示走完这$K$超市，起点为第$i$个超市，终点为第$j$个超市的最短路径（可能经过我们的$u$）。

这样我们可以通过$dfs$预处理出$f$数组。

那么统计答案的时候我们只需要枚举个这$K$个超市中的起点和终点就可以了。

统计答案：ans=min(ans,dis[p][i]+dis[q][i]+f[p][q])

到此，这题就被我们暴力过掉了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <queue>
#include <stdio.h>
#include <string.h>
#include <iostream>
#define Re register int

struct Edge{
	int to,next,w;
}e[100005];
std::queue<int> q;
int cnt,head[10005],St,ans=0x7FFFFFFF;
int N,M,K,k[6],dis[6][10005],vis[10005],f[6][6];

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	var=w?-x:x;
}
inline void AddEdge(int u,int v,int w)
{
	e[++cnt]=(Edge){v,head[u],w}; head[u]=cnt;
	e[++cnt]=(Edge){u,head[v],w}; head[v]=cnt;
}
inline void SPFA(int S,int *dist)
{
	for (Re i=1; i<=N; ++i) dist[i]=0x3FFFFFFF,vis[i]=0;
	q.push(S); dist[S]=0; vis[S]=1;
	while (!q.empty())
	{
		int now=q.front(); q.pop(); vis[now]=0;
		for (Re i=head[now];i;i=e[i].next)
			if (dist[e[i].to]>dist[now]+e[i].w)
			{
				dist[e[i].to]=dist[now]+e[i].w;
				if (!vis[e[i].to]) vis[e[i].to]=1,q.push(e[i].to);
			}
	} return;
}
inline void dfs(int d,int now,int len)
{
	if (d==K) {f[St][now]=std::min(f[St][now],len); return;}
	vis[now]=1;
	for (Re i=1; i<=K; ++i)
		if (!vis[i]) dfs(d+1,i,len+dis[now][k[i]]);
	vis[now]=0; return;
}
int main(int argc, char const *argv[])
{
	read(N),read(M),read(K);
	for (Re i=1; i<=K; ++i) read(k[i]);
	for (Re i=1,u,v,w; i<=M; ++i)
		read(u),read(v),read(w),AddEdge(u,v,w);
	for (Re i=1; i<=K; ++i) SPFA(k[i],dis[i]);
	memset(f,63,sizeof(f)); memset(vis,0,sizeof(vis));
	for (Re i=1; i<=K; ++i) St=i,dfs(1,i,0);
	for (Re i=1; i<=K; ++i) vis[k[i]]=1;
	for (Re i=1; i<=N; ++i)
	{
		if (vis[i]) continue;
		for (Re p=1; p<=K; ++p)
			for (Re q=1; q<=K; ++q)
				if (p!=q) ans=std::min(ans,dis[p][i]+dis[q][i]+f[p][q]);
	}
	printf("%d\n",ans); return 0;
}

T2

这道题官方题解的做法是倍增，实际上有更好的做法。

先看一下官方题解吧

对于20%的数据可以每次询问扫一次所有边，用并查集判断是否还是一棵树。
对于另外20%的数据，需要观察出一个性质：如果新加入的那条边的两个端点在原树上
面的路径包含删去的边，那么增删边之后还是一棵树，否则就不是。由于这部分数据树为随
机生成，所以期望树高是logn级别的，因此可以直接每次往上跳判断经过的边。（也许还能
有别的水法？）
对于100%的数据，我们继续沿用刚才的算法，由于树高可能相当大，我们可以先遍历
一次原树，确定每个点在原树的深度，然后每次询问用倍增算法找到询问加入的边的两个端
点往上跳到的删去的边所在深度，再判断一下是不是删去的那条边就可以了。

感觉就非常麻烦。而所谓更简便的做法就是利用树的$dfs$序做文章。

我们考虑断边的操作，它的实质就是把我们一棵完整的树拆成了一棵小子树（不含根节点）和一大团的东西（含根节点）。

再考虑一下连边的操作，如果我们能够证明出连边的两点分别在这两坨东西里面，我们就会发现CD没有得逞。

那么怎么证明呢。

在考场的时候，我用的是并查集（果然蒟蒻就是只会暴力）

实际上用树的$dfs$序可以很好地进行判断。（至于树的遍历、$dfs$序是什么不在本题解范围内，请自行了解）

我们记录每个结点变灰的时间$G[i]$，每个节点变黑的时间$B[i]$，然后判断连边的两点是否是一点在小子树中，一点不在小子树中。时间复杂度为$O(N+Q)$的。（跑的飞快啊）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>
#include <iostream>
#define Re register int

struct Edge{
	int to,next;
}e[400005];
int cnt,head[200005],dep[200005];
int N,Q,u[200005],v[200005],G[200005],B[200005],TimeStamp;

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	var=w?-x:x;
}
inline void AddEdge(int u,int v)
{
	e[++cnt]=(Edge){v,head[u]}; head[u]=cnt;
	e[++cnt]=(Edge){u,head[v]}; head[v]=cnt;
}
void dfs(int now,int fa)
{
	G[now]=++TimeStamp; dep[now]=dep[fa]+1;
	for (Re i=head[now];i;i=e[i].next)
		if (e[i].to!=fa) dfs(e[i].to,now);
	B[now]=++TimeStamp;
}
int main(int argc, char const *argv[])
{
	read(N);
	for (Re i=1; i<N; ++i)
		read(u[i]),read(v[i]),AddEdge(u[i],v[i]);
	dfs(1,0); read(Q); int x,y,z;
	while (Q--)
	{
		read(x),read(y),read(z); int p=u[z],q=v[z];
		if (dep[p]>dep[q]) std::swap(p,q); //保证q为小子树子树的根
		if (((G[q]<=G[x]&&B[q]>=G[x])&&(G[y]<G[q]||B[y]>B[q]))||
			((G[q]<=G[y]&&B[q]>=G[y])&&(G[x]<G[q]||B[x]>B[q]))) printf("NO\n");
		else printf("YES\n");
	}
	return 0;
}

T3

这题其实并不难，代码量也不大。但是思路比较难想。

很多人可能都会想树状数组、线段树能不能做（包括我这个蒟蒻）。

其实这题完全不用，用倍增就好了。

我们设$f[i][j]$为在$i$位置时，向后选$2^j$条线段所能达到的最小右端点$(Ri)$

初始时，$f[i][0]$为以$i$为左端点$(Li)$的所有线段中取一个右端点最小的。（贪心法可证）

但我们在求解$f[i][j]$时要注意，由于线段不能重叠，所以说我们必须这样递推$f[i][j]=f[f[i][j−1]+1][j]$

就是在跳小步的时候要$+1$。

然后还有在$i$比较大时，可能在$i$位置时，后面都没有线段，所以要特判掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
#include <iostream>
#include <algorithm>
#define Re register int

struct Segment{
	int l,r;
}d[100005];
int N,Q,len,f[100005][18],p,q;

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	var=w?-x:x;
}
inline bool cmp(Segment a,Segment b) {return a.l<b.l;}
int main(int argc, char const *argv[])
{
	read(N),read(Q),read(len);
	for (Re i=1; i<=N; ++i) read(d[i].l),read(d[i].r);
	std::sort(d+1,d+N+1,cmp); int p=N,R=len+1;
	for (Re i=len; i>0; --i)
	{
		while (p&&d[p].l==i) R=std::min(R,d[p--].r);
		f[i][0]=R;
	}
	for (Re j=1; j<=17; ++j)
		for (Re i=1; i<=len; ++i)
			if (f[i][j-1]!=len+1) f[i][j]=f[f[i][j-1]+1][j-1];
			else f[i][j]=len+1;
	while (Q--)
	{
		read(p),read(q); int ans=0;
		for (Re i=17; i>=0; --i) if (f[p][i]<=q) ans|=(1<<i),p=f[p][i]+1;
		printf("%d\n",ans);
	}
	return 0;
}