ICPC2020上海站

题解传送门

E.The Journey of Geor Autumn

这道题看似复杂，其实就是个很直观的递推。乍一看貌似无从下手，但是可以从最小数的放置方式入手，从而实现递推求解。注意这里递推的方式，可以手算一下，还是很好化简的。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef double db;
const int maxn=1e7+5;
const ll mod=998244353;
const double eps=1e-10;
int n,k;
ll f[maxn];
ll fac[maxn],infac[maxn];
ll quick_p(ll x,ll y){
	ll res=1;
	while(y){
		if(y&1)res*=x,res%=mod;
		y/=2;
		x*=x,x%=mod;
	}
	return res;
}
int main(){
	scanf("%d%d",&n,&k);
	fac[0]=1;
	for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i,fac[i]%=mod;
	infac[n]=quick_p(fac[n],mod-2);
	for(int i=n-1;i>=1;i--)infac[i]=infac[i+1]*(i+1),infac[i]%=mod;
	for(int i=1;i<=k;i++)f[i]=fac[i];
	ll sum=fac[k]*k%mod;
	for(int i=k+1;i<=n;i++){
		f[i]=sum;
		sum=(sum-f[i-k]*fac[i-1]%mod*infac[i-k]%mod+mod)%mod;
		sum*=i,sum%=mod;
		sum+=f[i],sum%=mod;
	}
	printf("%lld\n",f[n]);
	return 0;
}

K.Traveling Merchant

挺妙的一个点双连通分量的题目。题解的做法已经讲的很清楚了，这里就不再重复，只是简单说一下为什么最后的答案是一条重复的路。比如会不会存在一条路径，并没有经过任何一个循环呢，就像无理数那样没有循环节？

其实，就算没有循环节，也肯定会重复经过某个点，假设我第一次重复经过的点是p点，那么一定把可以从第一次经过p点到第二次经过p点前的那个点之间的路径视作一个循环。所以如果没有循环节，那么就一定没有一条无穷长的路径。

注意本题中判断两个点是否在同一个点双内时的方法，这次算是第一次写，以后要总结起来，感觉这个板子还挺重要的。注意这个题目中，如果lca是割点，那么也不可以组成路径（但是割点可能属于该点上方的点双内）。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef double db;
const int maxn=2e5+5;
const ll mod=998244353;
const double eps=1e-10;
int n,m,sz;
char s[maxn];
int low[maxn],dfn[maxn],vis[maxn],dep[maxn],in[maxn],tot;
int pa[maxn][30];
vector<int>st;
vector<int>e1[maxn],e2[maxn];
void clear(){
	for(int i=0;i<n;i++){
		e1[i].clear();
		e2[i].clear();
		for(int j=0;j<=20;j++)pa[i][j]=-1;
		dep[i]=0;vis[i]=0;low[i]=0;dfn[i]=0;in[i]=0;
	}
	tot=sz=0;st.clear();
}
void tarjan(int u,int p){
	pa[u][0]=p;
	vis[u]=1;
	low[u]=dfn[u]=++tot;
	st.push_back(u);
	for(auto v:e1[u]){
		if(!vis[v]){
			dep[v]=dep[u]+1;
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<=low[v]){
				in[u]=++sz;
				int cur=-1;
				while(cur!=v){
					cur=st.back();
					st.pop_back();
					in[cur]=sz;
				}
			}
			
		}
		else if(v!=p){
			low[u]=min(low[u],dfn[v]);
		}
	}
}
bool solve(){
	for(int u=0;u<n;u++){
		for(auto v:e2[u]){
			if(!low[u]||!low[v])continue;
			// if(low[u]==u||low[v]==v)continue;
			int x=u,y=v;
			if(dep[x]<dep[y])swap(x,y);
			for(int j=20;j>=0;j--){
				if(pa[x][j]==-1)continue;
				int temp=pa[x][j];
				if(dep[temp]<dep[y])continue;
				x=temp;
			}			
			for(int j=20;j>=0;j--){
				if(pa[x][j]==-1||pa[y][j]==-1)continue;
				if(pa[x][j]==pa[y][j])continue;
				x=pa[x][j],y=pa[y][j];
			}
			int cur=x;	
			if(x!=y)cur=pa[x][0];
			if(u==cur||v==cur)return true;
			if(cur==0)continue;
			if(in[cur]==in[u])return true;
			else if(in[cur]==in[v])return true;
		}
	}
	return false;
}
int main(){
	int T=1;scanf("%d",&T);
	while(T--){
		clear();
		scanf("%d%d%s",&n,&m,s);
		for(int i=1;i<=m;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			if(s[u]!=s[v]){
				e1[u].push_back(v);
				e1[v].push_back(u);					
			}
			else e2[u].push_back(v);
		}
		tarjan(0,-1);
		for(int j=1;j<=20;j++){
			for(int i=0;i<n;i++){
				if(pa[i][j-1]==-1)continue;
				pa[i][j]=pa[pa[i][j-1]][j-1];
			}
		}
		if(!solve())printf("no\n");
		else printf("yes\n");
		// for(int i=0;i<n;i++)printf("%d %d %d\n",i,dep[i],in[i]);
	}


	return 0;
}

ICPC2020济南站

J.Tree Constructer

可以说这是我今年做过最妙的构造题之一了。由于树是一个二分图，所以可以从此入手。把一部分的点当成钥匙，一部分当成锁，并且留出两位，保证锁与锁，钥匙与钥匙之间的点不会有连边。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef double db;
const int maxn=1e5+5;
const ll mod=998244353;
const double eps=1e-10;
int n;
vector<int>e[maxn];
int vis[maxn],cnt[5],rk[maxn];
ll p2[70],ans[105];
void dfs(int u,int p){
	cnt[vis[u]]++;
	for(auto v:e[u]){
		if(v==p)continue;
		vis[v]=vis[u]^1;
		dfs(v,u);
	}
}
int main(){
	int T=1;
	p2[0]=1;
	for(int i=1;i<=60;i++)p2[i]=p2[i-1]*2;
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<n;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			e[u].push_back(v);
			e[v].push_back(u);
		}
		vis[1]=0;
		dfs(1,0);
		for(int i=1;i<=n;i++){
			if(vis[i])ans[i]+=p2[59];
			else ans[i]+=p2[58];
		}
		int sgn=0,tot=0;
		if(vis[0]>vis[1])sgn=1;
		for(int i=1;i<=n;i++){
			if(vis[i]!=sgn)continue;
			rk[i]=++tot;
			ans[i]+=p2[58]-1-p2[tot];
		}
		for(int i=1;i<=n;i++){
			if(vis[i]==sgn)continue;
			for(auto v:e[i]){
				ans[i]+=p2[rk[v]];
			}
		}
		for(int i=1;i<=n;i++){
			printf("%lld ",ans[i]);
		}
	}
	return 0;
}

E.Tree Transform

这是我今年写过最折磨的一个题了，前前后后写了两三天QAQ…

我的做法从层序遍历第二棵树，然后依次把第一颗树中对应的点连到它的父亲上去。如果当前操作的节点与目标点（即它在第二棵树中的父节点）之间刚好隔了一个点，那么有两种情况：

  • 隔开它们的这个点是它们的lca
  • 当前操作的点是这个点的儿子，而这个点又是目标点的儿子

明确讨论范围之后，剩下的就是亿点点细节
注意连接的时候，有可能会导致长度为4的路径消失，所以应尽量保证图中一直存在长度为4的路径。
题解有种做法是把图化成链，再冒泡排序，这样可以少掉很多判断。但是我觉得这种做法并不能严格保证操作数小于10410^4当然，也有可能是我naive了

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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef double db;
const int maxn=1e5+5;
const ll mod=998244353;
const double eps=1e-10;
int n,tot;
vector<int>e1[maxn],e2[maxn];
int fa1[maxn],fa2[maxn];
int sz1[maxn],sz2[maxn];
int vis[maxn];
struct mytp{
	int x,y,z,w;
	int a1,b1;
	int a2,b2;
	int a3,b3;
}opt[maxn];
// int dep1[maxn],dep2[maxn];
void dele(int cur,int x){
	vector<int>vec;
	for(auto p:e1[cur]){
		if(p==x)continue;
		vec.push_back(p);
	}
	e1[cur].clear();
	for(auto p:vec){
		if(fa2[p]!=cur)e1[cur].push_back(p);
	}
	for(auto p:vec){
		if(fa2[p]==cur)e1[cur].push_back(p);
	}
}
void ad(int cur,int x){
	e1[cur].push_back(x);
}
void dfs1(int u,int p){
	fa1[u]=p;
	for(auto v:e1[u]){
		if(v==p)continue;
		dfs1(v,u);
	}
}
void dfs2(int u,int p){
	fa2[u]=p;
	for(auto v:e2[u]){
		if(p==v)continue;
		// dep2[v]=dep2[u]+1;
		dfs2(v,u);
	}
}
int fa3[maxn];
void dfs3(int u,int p){
	fa3[u]=p;
	for(auto v:e1[u]){
		if(v==p)continue;
		dfs3(v,u);
	}
}
bool  solve(int x){
	int cur=x,to=fa2[x];
	dfs3(to,0);
	vector<int>vec;
	vec.clear();
	while(cur!=to){
		for(auto v:e1[cur]){
			if(fa3[cur]==v){
				cur=v;
				vec.push_back(v);
				break;
			}
		}
	}
	int ed=fa1[x];
	for(int i=0;i<vec.size()-2;i+=2){
		opt[++tot]={x,vec[i],vec[i+1],vec[i+2],
			x,vec[i+2],
			vec[i+1],vec[i+2],
			vec[i],vec[i+1]};
		dele(vec[i],x);
		dele(x,vec[i]);
		ad(vec[i+2],x);
		ad(x,vec[i+2]);
		fa1[x]=vec[i+2];
		ed=vec[i+2];
	}
	if(to!=ed){
		if(fa1[to]==ed){
			int flag=0;
			for(auto v:e1[to]){
				if(v==ed||v==fa1[to])continue;
				if(fa2[v]==to)continue;
				opt[++tot]={v,to,ed,x,
					v,x,
					ed,to,
					ed,x};
				dele(v,to);
				dele(to,v);
				ad(v,x);
				ad(x,v);
				fa1[v]=x;
				break;										
			}
			for(auto i:e1[ed]){
				if(flag)break;
				for(auto j:e1[i]){
					if(j==ed)continue;
					flag=1;
					if(i==to){
						opt[++tot]={j,to,ed,x,
							j,to,
							to,ed,
							x,to};
						dele(ed,x);
						dele(x,ed);
						ad(to,x);
						ad(x,to);
						fa1[x]=to;	
					}
					else if(i==x){
						opt[++tot]={to,ed,x,j,
							to,ed,
							x,j,
							x,to};
						dele(ed,x);
						dele(x,ed);
						ad(to,x);
						ad(x,to);
						fa1[x]=to;	
					}
					else {
						opt[++tot]={x,ed,i,j,
							x,i,
							i,j,
							ed,i};
						dele(ed,x);
						dele(x,ed);
						ad(i,x);
						ad(x,i);
						fa1[x]=i;			
						opt[++tot]={to,ed,i,x,
							to,ed,
							ed,i,
							x,to};
						dele(i,x);
						dele(x,i);
						ad(to,x);
						ad(x,to);
						fa1[x]=to;							
					}
					break;
				}
			}
			if(!flag)return false;
		}
		else {
			for(auto v:e1[to]){
				if(v==ed||v==fa1[to])continue;
				if(fa2[v]==to)continue;
				opt[++tot]={v,to,ed,x,
					to,ed,
					ed,x,
					x,v};
				dele(v,to);
				dele(to,v);
				ad(v,x);
				ad(x,v);
				fa1[v]=x;
				break;						
			}
			int tp=0;
			for(auto v:e1[to]){
				if(v==ed)continue;
				tp=v;
				break;
			}
			if(tp){
				opt[++tot]={x,ed,to,tp,
					x,to,
					ed,to,
					to,tp};
				dele(ed,x);
				dele(x,ed);
				ad(to,x);
				ad(x,to);
				fa1[x]=to;					
			}
			else {
				int flag=0;
				for(int i=1;i<=n;i++){
					if(fa1[fa1[i]]!=ed)continue;
					flag=1;
					if(fa1[i]==x){
						opt[++tot]={to,ed,x,i,
							to,ed,
							x,to,
							x,i};
						dele(ed,x);
						dele(x,ed);
						ad(to,x);
						ad(x,to);
						fa1[x]=to;							
					}
					else {
						opt[++tot]={x,ed,fa1[i],i,
							x,fa1[i],
							ed,fa1[i],
							i,fa1[i]};
						dele(ed,x);
						dele(x,ed);
						ad(fa1[i],x);
						ad(x,fa1[i]);
						fa1[x]=fa1[i];		
						opt[++tot]={to,ed,fa1[i],x,
							to,ed,
							ed,fa1[i],
							x,to};
						dele(fa1[i],x);
						dele(x,fa1[i]);
						ad(to,x);
						ad(x,to);
						fa1[x]=to;	
					}
					break;
				}
				if(!flag)return false;
			}
		}
	}	
	return true;
	
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		e1[x].push_back(y);
		e1[y].push_back(x);
	}
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		e2[x].push_back(y);
		e2[y].push_back(x);
	}
	dfs2(1,0);
	dfs1(1,0);
	queue<int>q;
	q.push(1);vis[1]=1;
	while(!q.empty()){
		int p=q.front();
		q.pop();
		if(fa1[p]!=fa2[p]){
			if(!solve(p)){
				printf("NO\n");
				return 0;
			}
		}
		for(auto v:e2[p]){
			if(!vis[v]){
				q.push(v);
				vis[v]=1;
			}
		}
	}
	printf("YES\n%d\n",tot);
	for(int i=1;i<=tot;i++){
		printf("%d %d %d %d\n",opt[i].x,opt[i].y,opt[i].z,opt[i].w);
		printf("%d %d %d %d %d %d\n",opt[i].a1,opt[i].b1,opt[i].a2,opt[i].b2,opt[i].a3,opt[i].b3);
	}
	return 0;
}