Reincarnation

正因为梦易碎，才格外美好。

号家军集训 图论选做

发表于 更新于 分类于
本文字数： 34k 阅读时长 ≈ 31 分钟

讲师：丁晓漫

BerDonalds

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/266/D

形式化题意：存在一个 个结点， 条边的无向图，你需要在这张图中找到一个点 ，其中 可以在边上任意位置，使得 最小。

数据范围：

使题目条件最小，也就是找到这个图的最小直径树，也就是找到其绝对中心，考虑分讨。

如果 是某一个结点，那答案就是 ，这个可以使用多源最短路解决。

如果 在一条边上，记这条边为 ，且 ，那么 。

考虑最后将 处理完后得到的一个距离函数：

img

取自

那么 的位置就已经很显然了。

如何处理，设 表示距离 第 近的结点。那么对于结点上的答案我们用 来更新，而对于边上的答案，我们每次取其中的两条折线然后暴力取 再求 即可。

但考虑一个不太像暴力的做法，我们首先最大化 的答案，也就是从大到小枚举 ，记当前枚举到 ，此时 的枚举为 ，我们比较 的大小，如果 的话，而 又是保证的，所以此时对于 产生了交点，所以我们更新答案，并通过 找到下一个交点。

设 是目前考虑过的所有 中使得 最大的那个，此时 的那条折线的递减部分一定是完全暴露在外的。因此若此时有 ，则会在 的递减部分产生一个新的合法最小值拐点。那么此时 和 一定同时是最长路径（还没考虑到的点的拐点在 的后面，而交点是在 的拐点前面，因此图像都在 下面），由此计算更新答案。

AC Code
 
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// ----- Eternally question-----
// Problem: BerDonalds
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF266D
// Memory Limit: 250 MB
// Time Limit: 5000 ms
// Written by: Eternity
// Time: 2023-07-12 14:40:50
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e2+10,MAXM=2e4+10;
const int INF=0x3f3f3f3f;
int N,M;
int Dist[MAXN][MAXN];
int tmp[MAXN],Rk[MAXN][MAXN];
struct Edges
{ int fr,to,val; }Ed[MAXM];
inline bool cmp(int a,int b){ return tmp[a]<tmp[b]; }
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N,M);
	std::memset(Dist,0x3f,sizeof(Dist));
	for(int i=1;i<=N;++i) Dist[i][i]=0;
	for(int i=1,u,v,w;i<=M;++i) read(u,v,w),Dist[u][v]=Dist[v][u]=w,Ed[i]=(Edges){u,v,w};
	for(int k=1;k<=N;++k) for(int i=1;i<=N;++i) for(int j=1;j<=N;++j) checkMin(Dist[i][j],Dist[i][k]+Dist[k][j]);
	for(int i=1;i<=N;++i)
	{
		for(int j=1;j<=N;++j) Rk[i][j]=j,tmp[j]=Dist[i][j];
		std::sort(Rk[i]+1,Rk[i]+N+1,cmp);
	}
	int ans=INF;
	for(int i=1;i<=N;++i) checkMin(ans,Dist[i][Rk[i][N]]*2);
	for(int i=1;i<=M;++i)
	{
		auto e=Ed[i];
		for(int pos=N,j=N-1;j;--j) if(Dist[e.to][Rk[e.fr][j]]>Dist[e.to][Rk[e.fr][pos]])
			checkMin(ans,Dist[e.fr][Rk[e.fr][j]]+Dist[e.to][Rk[e.fr][pos]]+e.val),pos=j;
	}
	printf("%.2lf",(double)ans/2);
	return 0;
}
/*

*/

Gift

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/76/A

形式化题意：给定一个有 个结点 条边的无向图，每条边的权值是一个二元组 ，现给定 ，求出这个图的一个生成树，并最小化 。

数据范围：

考虑降维处理，从小到大枚举 ，并处理 的贡献。

相当于我们有一个初始为空的边集 ，每次向这个集合中填入一些边并求出这个边集关于 的最小生成树。这个求最小生成树的过程我们可以动态维护一个关于 的单调栈，让其边数维持在 左右，最后判答案即可。

时间复杂度 ，勉强能过。

AC Code
 
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
// ----- Eternally question-----
// Problem: Gift
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF76A
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-07-12 19:05:57
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e2+10,MAXM=5e4+10;
const ll INF=0x3f3f3f3f3f3f3f3f;
int N,M,G,S;
ll ans=INF;
struct Edges
{
	int fr,to,g,s;
	bool operator<(const Edges &x) const { return g<x.g; }
}Ed[MAXM],tmp[MAXM];
struct DSU
{
	int Rt[MAXN];
	inline void build(int n){ for(int i=1;i<=n;++i) Rt[i]=i; }
	inline int getRt(int x){ return Rt[x]==x?x:Rt[x]=getRt(Rt[x]); }
	inline void merge(int u,int v)
	{
		int p=getRt(u),q=getRt(v);
		if(p==q) return ;
		Rt[p]=q;
	}
	inline bool connect(int u,int v){ return getRt(u)==getRt(v); }
}Dsu;
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N,M,G,S);
	for(int i=1,u,v,g,s;i<=M;++i)
	{
		read(u,v,g,s);
		Ed[i]=(Edges){u,v,g,s};
	}
	std::sort(Ed+1,Ed+M+1);
	for(int i=1,Tot=0,cnt=0;i<=M;++i)
	{
		int pos=++Tot;
		auto e=Ed[i];
		while(pos>=2&&tmp[pos-1].s>e.s) tmp[pos]=tmp[pos-1],--pos;
		tmp[pos]=e,Dsu.build(N);
		cnt=0;int maxS=0;
		for(int j=1;j<=Tot;++j)
		{
			int u=tmp[j].fr,v=tmp[j].to;
			if(!Dsu.connect(u,v))
			{
				checkMax(maxS,tmp[j].s),tmp[++cnt]=tmp[j];
				Dsu.merge(u,v);
			}
		}
		if(cnt==N-1) checkMin(ans,(ll)maxS*S+(ll)Ed[i].g*G);
		Tot=cnt;
	}
	write(ans==INF?-1:ans);
	return 0;
}
/*

*/

月票购买

题目简介

题目名称： 月票购买

题目来源：

评测链接：https://loj.ac/p/2350

形式化题意：给定一个 的边带权无向图，已知一条路径 的最短路经过的所有边权值不计入代价，求 的最短路。

数据范围：

考虑如果 不存在的话，直接跑一遍最短路就好了，那如果纳入了 的考虑，我们思考正解的出现形式，记录 上的两个不同结点 ，那么最后的路径应该形如 ，最后记录答案为 ，因为 不计入答案。

所以考虑处理最短路 ，并在 路径上设 表示从 路径上到 的最短长度， 同理。

用 可以处理， 可以考虑把 链拉出来直接跑一遍 什么的，存储答案：

就大概结束了，时间复杂度 。

AC Code
 
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
// ----- Eternally question-----
// Problem: #2350. 「JOI 2018 Final」月票购买
// Contest: LibreOJ
// URL: https://loj.ac/p/2350
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-07-12 19:53:21
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10,MAXM=2e5+10;
const ll INF=0x3f3f3f3f3f3f3f3f;
int N,M,S,T,U,V;
struct G
{ int next,to,val; }Edge[MAXM<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v,int w)
{
	Edge[++Total]=(G){Head[u],v,w};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u,w};Head[v]=Total;
}
struct Node
{
	int x;ll val;
	Node(int x=0,ll val=0):x(x),val(val){}
	bool operator<(const Node& x) const { return val>x.val; }
};
bool Vis[MAXN];
inline void Dijkstra(int st,ll Dist[])
{
	std::priority_queue<Node>Pq;
	for(int i=1;i<=N;++i) Vis[i]=0,Dist[i]=INF;
	Pq.push(Node(st,0)),Dist[st]=0;
	while(!Pq.empty())
	{
		int u=Pq.top().x;Pq.pop();
		if(Vis[u]) continue;
		Vis[u]=1;
		for(int e=Head[u];e;e=Edge[e].next)
		{
			int v=Edge[e].to;
			if(checkMin(Dist[v],Dist[u]+Edge[e].val)) (!Vis[v])&&(Pq.push(Node(v,Dist[v])),1);
		}
	}
}
ll DistS[MAXN],DistT[MAXN],DistU[MAXN],DistV[MAXN];
ll FrU[MAXN],ToV[MAXN],ans=INF;
void dfsCalc(int x)
{
	if(Vis[x]) return ;
	Vis[x]=1;
	FrU[x]=DistU[x],ToV[x]=DistV[x];
	for(int e=Head[x];e;e=Edge[e].next)
	{
		int v=Edge[e].to;
		if(DistS[x]+DistT[v]+Edge[e].val>DistS[T]) continue;
		dfsCalc(v);
		checkMin(FrU[x],FrU[v]),checkMin(ToV[x],ToV[v]);
	}
	checkMin(ans,std::min(FrU[x]+DistV[x],ToV[x]+DistU[x]));
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N,M,S,T,U,V);
	for(int i=1,u,v,w;i<=M;++i) read(u,v,w),addEdge(u,v,w);
	Dijkstra(S,DistS),Dijkstra(T,DistT),Dijkstra(U,DistU),Dijkstra(V,DistV);
	// write(DistS[T],' ',DistT[S],' ',DistU[V],' ',DistV[U],'\n');
	ans=DistU[V];
	for(int i=1;i<=N;++i) Vis[i]=0;
	dfsCalc(S);
	write(ans);
	return 0;
}
/*

*/
题目简介

题目名称：

题目来源：

评测链接：https://www.luogu.com.cn/problem/P6890

形式化题意：给定一个 个结点 条有向边的图，保证每个结点有且仅有 的出度，每次操作可以向这张图添加一条长度为 的有向边，求使得 到任意结点的距离不超过 ，需要的最少操作次数。

数据范围：

这张图实际上是一个内向基环树。

考虑一种贪心的添边方式，肯定从 直接拉过去是最优的。而对于一些入度为 的点，是必须要添边的，否则会直接不连通，每次选点后更新整张图的最短路，并把所有 的点全部删掉，然后就会出现新的入度为 的点，重复上述操作即可。

考虑环的做法，每次向环上点连边会覆盖一个长度为 的区间，那么最后会连边 条，其中 是环长，所以环上的方案也是一个长度为 的循环，所以至多枚举 个点即可，最后的时间复杂度还是 的。

AC Code
 
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
// ----- Eternally question-----
// Problem: P6890 [CEOI2006] Link
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6890
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-12 20:41:31
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e5+10,MAXM=1e6+10;
const int INF=0x3f3f3f3f;
int N,K,ans;
std::vector<int>Edges[MAXM];
int To[MAXM],In[MAXN],Dist[MAXN],Cov[MAXN],Nxt[MAXN];
bool Vis[MAXN],Cir[MAXN],isCov[MAXN];
std::vector<int>Circle;
void Dfs(int x)
{
	Vis[x]=1,Dist[x]=INF;
	for(int v:Edges[x])
	{
		if(Cir[v]) continue;
		Dfs(v),checkMin(Dist[x],Dist[v]+1);
	}
	if(x==1) Dist[x]=0;
	if(!Cir[x]&&Dist[x]>K) Dist[x]=1,++ans;
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N,K);
	for(int i=1,u,v;i<=N;++i)
	{
		read(u,v);Edges[v].emplace_back(u);
		To[u]=v,++In[v];
	}
	for(int i=1;i<=N;++i)
		if(!Vis[i])
		{
			Circle.clear();
			int x=i;Circle.emplace_back(-1);
			while(!Vis[x]) Vis[x]=1,x=To[x];
			Circle.emplace_back(x),Cir[x]=1;
			int y=To[x];
			while(x!=y) Circle.emplace_back(y),Cir[y]=1,y=To[y];
			int cnt=Circle.size()-1;
			for(int j=1;j<=cnt;++j) Dfs(Circle[j]),Cov[j]=Cov[j+cnt]=0;
			for(int j=1;j<=cnt;++j) 
				if(Dist[Circle[j]]<=K)
				{
					++Cov[j];
					if(j+K-Dist[Circle[j]]<cnt<<1) Cov[j+K-Dist[Circle[j]]+1]--;
				}
			for(int j=1;j<cnt<<1;++j) Cov[j]+=Cov[j-1];
			for(int j=1;j<=cnt;++j) 
				if(Cov[j]||Cov[j+cnt]) isCov[j]=isCov[j+cnt]=1;
				else isCov[j]=isCov[j+cnt]=0;
			Nxt[(cnt<<1)+1]=(cnt<<1)+1;
			for(int j=cnt<<1;j;--j)
				if(isCov[j]) Nxt[j]=Nxt[j+1];
				else Nxt[j]=j;
			int flag=0,Minn=INF;
			for(int j=1;j<=cnt;++j)
			{
				if(isCov[j]) continue;
				int tmp=0;
				for(x=j;x<j+cnt;)
				{
					++tmp,x+=K;
					if(x<j+cnt) x=Nxt[x];
				}
				checkMin(Minn,tmp);
				if(++flag==K) break;
			}
			if(Minn!=INF) ans+=Minn;
		}
	write(ans);
	return 0;
}
/*

*/

主旋律

题目简介

题目名称：主旋律
题目来源：

评测链接：https://uoj.ac/problem/37

形式化题意：给定一个 个结点 条边的有向图，求有多少个边的子集使得整张图是一个强连通图。

数据范围：

考虑求其补集，也就是求多少个边集使整张图非强连通。而如果这张图非强连通的话，缩点之后是一个 ，考虑有标号有向无环图的计数问题。

设 表示点集 中删除一些边使其成为 的方案总数。枚举入度为 的点，并进行计算，但考虑到在 的补集 中同样存在入度为 的点，所以需要容斥：

暴力计算时间复杂度 。

缩点后的图是一个由若干个强连通分量组成的 ，我们用 表示点集 是否是一个 ，那么这就是答案的组成了。

用 分别表示当前强连通分量个数为奇数和偶数的方案数：

其中 表示两个集合之间的连边个数。

然后就可以直接做了。

AC Code
 
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
// ----- Eternally question-----
// Problem: #37. 【清华集训2014】主旋律
// Contest: UOJ
// URL: https://uoj.ac/problem/37
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-13 07:56:17
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=15,MAXM=3e2+10,MAXS=1<<15|10;
const int Mod=1e9+7;
template<class T>
inline void add(T &x,T y){ x=x+y>=Mod?x+y-Mod:x+y; }
int N,M;
ll D[MAXS],S[MAXS],f[MAXS],Pw[MAXS];
std::bitset<MAXM>In[MAXS],Out[MAXS];
inline int calc(int s,int t){ return (Out[s]&In[t]).count(); }
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N,M),Pw[0]=1;
	int sx=(1<<N)-1;
	for(int i=1;i<=N*N;++i) Pw[i]=(ll)Pw[i-1]*2%Mod;
	for(int i=1,u,v;i<=M;++i)
	{
		read(u,v);
		for(int j=1;j<=sx;++j)
		{
			if(j&(1<<(u-1))) Out[j][i]=1;
			if(j&(1<<(v-1))) In[j][i]=1;
		}
	}
	S[0]=1;
	for(int s=1;s<=sx;++s)
	{
		f[s]=Pw[calc(s,s)];
		for(int t=(s-1)&s;t;t=(t-1)&s)
		{
			add(f[s],(-(D[t]-S[t])*Pw[calc(t,s-t)+calc(s-t,s-t)]%Mod+Mod)%Mod);
			if((t&(s&-s))==0) continue;
			add(D[s],f[t]*S[s-t]%Mod);
			add(S[s],f[t]*D[s-t]%Mod);
		}
		add(f[s],(S[s]-D[s]+Mod)%Mod);
		add(D[s],f[s]);
	}
	write(f[sx]);
	return 0;
}
/*

*/

Graph Game

题目简介

题目名称：

题目来源：

评测链接：https://acm.hdu.edu.cn/showproblem.php?pid=3267

形式化题意：给定一个 个结点 条边的无向图，现有 人进行博弈，每次每个人能够选择一条边。求是否存在必胜策略使得后手能够选择一个边集使得整张图连通。多测。

数据范围：

首先，图中不能存在桥，否则先手必胜。

考虑后手最劣势情况下的胜利状态，就是选择了这个图上的某一个生成树。

所以当先手选择了一条生成树上的边，后手必须能够选择一条有相同效果的边来替换这条边，否则就无法构成生成树。如此下来，在 轮决策后，先手和后手应该都选择了一棵生成树。然后感性理解一下，得到必胜策略是这张图存在两个边不相交的生成树时，后手必胜。

如果条件成立，则当先手选择了其中一棵生成树的边时，后手就能够一一对应选择另外一棵生成树的对应边；而如果图中不存在两棵生成树，那必定存在一条边是桥，先手必胜。

考虑如何实现，可以直接暴力枚举所有大小为 的边集对补集进行连通性判断，一共只有 种方案，每次判断只需要 判断，随便剪一下枝就能过了。

AC Code
 
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
// ----- Eternally question-----
// Problem: P - Graph Game
// Contest: Virtual Judge - 【2023 暑期集训 NOI班】图论（丁晓漫）
// URL: https://vjudge.net/contest/568648#problem/P
// Memory Limit: 32 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-13 08:58:51
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
#define popcount(x) __builtin_popcount(x)
const int MAXN=20,MAXM=40;
int N,M;
struct Edges
{
	int fr,to,val;
	bool operator<(const Edges &x) const { return val<x.val; }
}Ed[MAXM];
std::mt19937 rnd(19260817);
struct DSU
{
	int Rt[MAXN],Siz[MAXN],Stk[MAXN],Top;
	inline void build(int n)
	{
		for(int i=1;i<=n;++i) Rt[i]=i,Siz[i]=1;
		Top=0;
	}
	inline int getRt(int x)
	{
		while(Rt[x]!=x) x=Rt[x];
		return x;
	}
	inline void merge(int u,int v)
	{
		int p=getRt(u),q=getRt(v);
		if(p==q) return ;
		if(Siz[p]<Siz[q]) std::swap(p,q);
		Siz[p]+=Siz[q],Rt[q]=p,Stk[++Top]=q;
	}
	inline bool connect(int u,int v){ return getRt(u)==getRt(v); }
	inline void back()
	{
		int q=Stk[Top--];
		Siz[Rt[q]]-=Siz[q],Rt[q]=q;
	}
	inline void back(int x){ while(Top>x) back(); }
}Dsu;
struct G
{ int next,to; }Edge[MAXM<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
bool Vis[MAXN],Usd[MAXM],ans;
void dfsChk(int x)
{
	if(Vis[x]) return ;
	Vis[x]=1;
	for(int e=Head[x];e;e=Edge[e].next) dfsChk(Edge[e].to);
}
inline void check()
{
	Total=0;
	for(int i=1;i<=N;++i) Head[i]=0,Vis[i]=0;
	for(int i=1;i<=M;++i) if(!Usd[i]) addEdge(Ed[i].fr,Ed[i].to);
	dfsChk(1);
	for(int i=1;i<=N;++i) if(!Vis[i]) return ;
	ans=1;
}
void dfsMix(int cnt,int pos)
{
	if(cnt>=N-1) return check();
	if(ans) return ;
	for(int i=pos;i<=M;++i)
	{
		auto e=Ed[i];
		if(!Dsu.connect(e.fr,e.to))
		{
			// write(i,' ',e.fr,' ',e.to,'\n','{',' ');
			Dsu.merge(e.fr,e.to),Usd[i]=1,dfsMix(cnt+1,i+1);
			if(ans) return ;
			Dsu.back(),Usd[i]=0;
			// write(' ','}','\n');
		}
	}
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	while(true)
	{
		read(N,M);
		if(!~N&&!~M) break;
		for(int i=1;i<=M;++i) read(Ed[i].fr,Ed[i].to),++Ed[i].fr,++Ed[i].to;
		for(int i=1;i<=M;++i) Usd[i]=0;
		ans=0,Dsu.build(N);
		dfsMix(0,1);
		puts(ans?"YES":"NO");
	}
	return 0;
}
/*

*/

Rearranging

题目简介

题目名称：

题目来源：

评测链接：https://atcoder.jp/contests/agc010/tasks/agc010_e

形式化题意：给定一个长度为 的序列 ，先手可以任意构造一个排列 并使 序列变为 ，也就是以任意顺序重排 序列，而后手可以移动任意两个相邻的不互质元素，即必须满足 ，后手可以操作无数次。

先手要求结果序列字典序最小，后手要求字典序最大，二者都采用最优策略的前提下，求最后得到的序列。

数据范围：

考虑如果存在一个 与其他数全部都互质的话，那这个 就可以在序列里自由移动，而这个时候出现了 ，那 无论如何都无法僭越 ，至此 永远只能在 的左边或者右边。

所以，所有不互质的数对在先手操作结束后就已经确定了。而对于这些确定数对，肯定要使 排列，这样，我们也可以是做连了一条 的有向边，而使后手在“遍历”的时候只能先选 再选 ，这就转换成一个图论模型了。

那对于 的情况呢，就需要后手来决定谁在前谁在后，所以可以得到一个 的双向边。如此而来，就可以得到一个可能不连通的有向图，后手的操作就是在这个图上跑一遍拓扑排序，而至于字典序最大，就是每次取出值最大的就可以了。

AC Code
 
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// ----- Eternally question-----
// Problem: [AGC010E] Rearranging
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_agc010_e
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-07-13 14:44:59
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e3+10,MAXM=1e6+10;
int N,a[MAXN];
struct G
{ int next,to; }Edge[MAXM<<1];
int Head[MAXN],Deg[MAXN],Total;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;++Deg[v];
	// Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
int gcd(int a,int b){ return !b?a:gcd(b,a%b); }
bool Con[MAXN][MAXN];
int Cnt,Vis[MAXN];
void Dfs(int x)
{
	Vis[x]=Cnt;
	for(int v=1;v<=N;++v) if(Con[x][v]&&!Vis[v]) Dfs(v),addEdge(x,v);
}
inline void Topo()
{
	std::priority_queue<int>Pq;
	for(int x=1;x<=N;++x) if(!Deg[x]) Pq.push(x);
	while(!Pq.empty())
	{
		int u=Pq.top();Pq.pop();
		write(a[u],' ');
		for(int e=Head[u],v;e;e=Edge[e].next)
		{
			v=Edge[e].to;
			if(!(--Deg[v])) Pq.push(v);
		}
	}
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i) read(a[i]);
	std::sort(a+1,a+N+1);
	for(int i=1;i<=N;++i) for(int j=1;j<i;++j) if(gcd(a[i],a[j])!=1) Con[i][j]=Con[j][i]=1;
	for(int i=1;i<=N;++i) if(!Vis[i]) ++Cnt,Dfs(i);
	Topo();
	return 0;
}
/*

*/

校园旅行

题目简介

题目名称：校园旅行
题目来源：湖南省选

评测链接 ：https://loj.ac/p/3057
评测链接 ：https://www.luogu.com.cn/problem/P5292

形式化题意：给定一个 个结点， 条边的点带权图，且点权 。图中不存在自环和重边，共 次询问，每次询问 之间是否存在一条路径（不要求简单），使得将其点权拼接成字符串后回文。

数据范围：

考虑有一个比较特殊的性质，也就是路径不要求简单，意味着我们可以走一条边很多很多次，以弥补无法通过前进一步使得回文的效果。

考虑用 表示 之间是否存在回文路径，显然，对于 和连通的 肯定是满足的，我们以这些为初始状态，每次扩展没有到过的与 相连的边，并判断回文，注意这里奇回文与偶回文都应该计算。

可能认为这样的复杂度是 ，但事实上，状态数的确是 ，但我们是由边扩展，所以时间复杂度应该是 的。

那是否存在一种 的做法呢，显然是有的，否则这题没法做了。

考虑根据点权将这个图二分，构成一个可能不是二分图的二分图。

因为我们通过非简单路径可以在任意时刻任意位置修改当前回文串的奇偶性，所以我们的回文串一定由 四种子串组成。

考虑将边分成两类，一类左右连接不同权值的点，另一类连接相同的。

在转移相同的边的时候，我们只需要保证左右转移的边数相同，更抽象一点就是奇偶性相同，这一点就可以联想到二分图，因为二分图保证了路径的奇偶性，且保证连通。且有一个条件是非简单路径，那奇偶性就更好理解了，我随便挑条边来回跑就行了，所以对于相同边组成的连通块，整一棵生成树是等价的。但需要注意的是，如果无法转换为二分图，也就是原图存在奇环，让我们牢牢记住非简单路径，那找个点连一个自环就行了。

然后考虑权值不同的边的转移，一定存在一种方法使得点集被划分成二分图，然后按照上面的方法选择一个生成树就可以了，这样剩下的边数是 级别的，暴力做就行了。

AC Code
 
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
// ----- Eternally question-----
// Problem: P5292 [HNOI2019] 校园旅行
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5292
// Memory Limit:  500 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-07-16 19:29:51
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using Pir=std::pair<int,int>;
#define fir first
#define sec second
const int MAXN=5e3+10,MAXM=5e5+10;
int N,M,Q;
struct G
{ int next,to; }Edge[MAXM<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
std::vector<int>Edges[MAXN];
std::queue<Pir>Pq;
int Col[MAXN];
bool ans[MAXN][MAXN],flag;
char Str[MAXN];
struct DSU
{
	int Rt[MAXN];
	inline void build(int n){ for(int i=1;i<=n;++i) Rt[i]=i; }
	inline int getRt(int x){ return Rt[x]==x?x:Rt[x]=getRt(Rt[x]); }
	inline void merge(int u,int v)
	{
		int p=getRt(u),q=getRt(v);
		if(p==q) return ;
		Rt[p]=q;
	}
	inline bool connect(int u,int v){ return getRt(u)==getRt(v); }
}Dsu;
void dfsCol(int x,int col)
{
	Col[x]=col;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if(Str[(v=Edge[e].to)]!=Str[x]) continue;
		if(Col[x]==Col[v]) flag=1;
		if(!Col[v])
		{
			dfsCol(v,col^1);
			ans[x][v]=ans[v][x]=1;
			Edges[x].push_back(v),
			Edges[v].push_back(x);
			Pq.push({x,v});
		}
	}
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M,Q);Dsu.build(N);
	scanf("%s",Str+1);
	for(int i=1,u,v;i<=M;++i)
	{
		read(u,v);addEdge(u,v);
		if(Str[u]!=Str[v]&&!Dsu.connect(u,v)) Dsu.merge(u,v),Edges[u].push_back(v),Edges[v].push_back(u); 
	}
	for(int i=1;i<=N;++i) if(!Col[i])
	{
		flag=0;dfsCol(i,4);
		if(flag) Edges[i].push_back(i);
	}
	for(int i=1;i<=N;++i) ans[i][i]=1,Pq.push({i,i});
	while(!Pq.empty())
	{
		auto u=Pq.front();Pq.pop();
		for(int x:Edges[u.fir]) for(int v:Edges[u.sec])
			if(!ans[x][v]&&Str[x]==Str[v]) ans[x][v]=ans[v][x]=1,Pq.push({x,v});
	}
	for(int qx,qy;Q--;)
	{
		read(qx,qy);
		puts(ans[qx][qy]?"YES":"NO");
	}
	return 0;
}

Nastya and Time Machine

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/1340/D

形式化题意：给定一棵有 个结点的树，经过任意一条边需要 个单位的时间，在任意结点的任意时刻，你可以选择将当前时间变为不超过当前时间的任意非负整数，求在下列条件限制内，经过结点最大时间的最小值。

  1. 每个结点至少经过 次；
  2. 每次经过同一个结点的时间互不相同；
  3. 起始点和终止点都在 号结点。

构造出一种方案，求出所有步骤（包括行动与调时），步数不超过

数据范围：

考虑记度数为 ，那么结点 至少会被经过 次，同理，我们发现经过结点最大时间的最小值就是 。然后考虑如何构造。

我们设 表示进入结点 时的时间，那么遍历 子树时分以下情况讨论：

  1. 时，显然 不会成为答案构造瓶颈，无论如何我们都可以在离开 时让时间变成 。
  2. ，此时我们必须返回一定时间，才能让答案不超过限制，一共会占据 个时间点，所以我们返回到 即可。
AC Code
 
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
// ----- Eternally question-----
// Problem: D. Nastya and Time Machine
// Contest: Codeforces - Codeforces Round 637 (Div. 1) - Thanks, Ivan Belonogov!
// URL: https://codeforces.com/problemset/problem/1340/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-08-15 07:50:52
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e5+10;
int N;
struct G
{ int next,to; }Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
int Deg[MAXN],Top,Cnt,T;
struct Answer
{ int pos,tim; }ans[MAXN<<4];
inline void add(int p,int t)
{ ans[++Cnt]=(Answer){p,t}; }
void dfsTree(int x,int last,int t)
{
	add(x,t);
	int _t=t;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==last) continue;
		if(t==T&&_t>Deg[x]) t=T-Deg[x],add(x,t);
		if(t==Deg[x]&&_t<=Deg[x]) t=0,add(x,t);
		dfsTree(v,x,++t);
		add(x,t);
	}
	if(_t>=1&&t!=_t-1) add(x,_t-1);
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=2,u,v;i<=N;++i) read(u,v),addEdge(u,v),++Deg[u],++Deg[v];
	for(int i=1;i<=N;++i) checkMax(T,Deg[i]);
	dfsTree(1,0,0);
	write(Cnt,'\n');
	for(int i=1;i<=Cnt;++i) write(ans[i].pos,' ',ans[i].tim,'\n');
	return 0;
}
/*

*/
相关文章