2017-2018 ACM-ICPC, Asia Tsukuba Regional Contest

发表于 分类于

比赛链接

链接

A

设 $f_{i,0/1}$ 表示填满前 $i$ 行时，最上面一行是白/黑的方案数。

时间复杂度 $O(n)$。

B

由于 $m\leq 16$，那么总方案数最多为 $\frac{\binom{16}{8}8!}{2^8}=2027025$。

于是直接爆搜，由于时限10s，那么暴力 $O(m^2)$ 判断都可以。

C

还没看。

E

设 $f_i$ 表示考虑到前 $i$ 个时的最小操作次数。

$f_i=\min{f_j+g(j+1,i)}$，其中 $g(l,r)$ 表示 $[l,r]$ 最小需要的操作次数，也就是 $t[l,r]$ 中不同的连续段数+1的一半。单调队列或线段树优化即可。

时间复杂度 $O(n)$ 或 $O(n\log n)$。

F

从 $1,2$ 分别跑一次原图，反图最短路，建出从 $1$ 开始的，能到 $2$ 的最短路图，边反向后是否令最短路减小很好判断，是否增大则需要根据该边是否为最短路图中从 $1$ 到 $2$ 的必经路。

预处理出这些边即可。

H

最大值直接跑二分图匹配即可。

最小值的话很像一个最小割的形式，同一时刻，如果选了一个 $X$，那么 $Y$ 那边就不必选。也就是说，若出现了 $X,Y$ 中两个任务的时间重叠，那么就连一条边，然后相当于最小割。

但是时间可能分配不够，于是就相当于每个时间有一个节点容量一，然后 $s$ 连向 $X$，$X$ 连向时间点，时间点连向 $Y$，$Y$ 连向 $t$，就可以做最小割了。

K

题意

给定 $n$ 个点 $m$ 条边的无向连通图，求出简单环的个数。

$n-1\le m \le n-15$。

$3 \le n \le 10^5$。

题解

显然先dfs建出一棵树，而非树边是不会出现横叉边的。

最多只有 $m-(n-1)\le 16$ 条非树边。

暴力枚举每条非树边是否进行选择，若选择一条边 $(x,y)$ 则可看做为在树中从 $x$ 走到 $y$。

若能走出一个环，必要条件是每条边都必须经过偶数次。

那么判断是否可行时统计出树中每条边的经过的次数，若出现了奇数次，则该树边一定要选上。

最后形成一个边的集合，判断这个边集是否是个简单环就可以了。

于是写一个虚树即可。

注意最后判断边是否形成简单环时要注意，有些点是没有边出去的，这些也是可以的。

时间复杂度 $O(2^{m-n}\times (m-n)\log n+n\log n)$，也可以优化并去掉一个log，但是会没有必要。

程序

打了我快1h…

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
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=200020;
namespace Graph{
	vector<int> adj[N];
	int dep[N],dfn[N],tim;
	int f[N][19];
	int sum;
	struct edge{
		int x,y;
	};
	vector<edge> e;
	inline void add(int x,int y)
	{
		if(x==y) {sum++; return;}
		adj[x].pb(y); adj[y].pb(x);
	}
	void dfs(int u,int pre)
	{
		dfn[u]=++tim; dep[u]=dep[pre]+1;
		f[u][0]=pre;
		fo(i,1,18) f[u][i]=f[f[u][i-1]][i-1];
		bool flag=0;
		for(auto v:adj[u])
		{
			if(v==pre)
			{
				continue;
			}
			if(dfn[v])
			{
				if(dfn[v]<dfn[u]) e.pb((edge){u,v});
			}
			else dfs(v,u);
		}
	}
	inline int lca(int x,int y)
	{
		if(dep[x]>dep[y]) swap(x,y);
		fd(i,18,0) if(dep[f[y][i]]>=dep[x]) y=f[y][i];
		if(x==y) return x;
		fd(i,18,0) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
		return f[x][0];
	}
	vector<int> _adj[N];
	vector<edge> ed;
	void _add(int x,int y)
	{
		_adj[x].pb(y); _adj[y].pb(x);
	}
	int rt;
	int st[N],top,now;
	void build(vector<int> &a)
	{
		rt=a[0];
		for(auto v:a) rt=lca(rt,v);
		a.pb(rt);
		sort(all(a),[&](const int &x,const int &y){return dfn[x]<dfn[y];});
		a.resize(unique(all(a))-a.begin());
		top=0;
		int y;
		for(auto x:a)
		{
			if(top)
			{
				y=lca(x,st[top]);
				if(y!=st[top])
				{
					for(;top>=2&&dep[st[top-1]]>=dep[y];top--) _add(st[top],st[top-1]);
					if(st[top]!=y) _add(st[top],y),st[top]=y;
				}
			}
			if(st[top]!=x) st[++top]=x;
		}
		if(top) for(;--top;) _add(st[top],st[top+1]);
	}
	vector<int> V;
	int w[N];
	void dfs2(int u,int pre)
	{
		V.pb(u);
		for(auto v:_adj[u])
			if(v!=pre)
			{
				dfs2(v,u);
				w[u]^=w[v];
			}
		if(w[u]&&u!=rt) ed.pb((edge){u,pre});
	}
	void clr(int u,int pre)
	{
		for(auto v:_adj[u]) if(v!=pre) clr(v,u);
		_adj[u].clear(); w[u]=0;
	}
	int vis[N],deg[N];
	inline void __add(int x,int y)
	{
		_adj[x].pb(y); _adj[y].pb(x);
		deg[x]++; deg[y]++;
	}
	bool ans;
	void dfs3(int u,int pre)
	{
		if(!ans) return;
		if(vis[u])
		{
			if(vis[u]!=tim) ans=0;
			return;
		}
		vis[u]=tim;
		for(auto v:_adj[u])
			if(v!=pre) dfs3(v,u);
	}
	inline int check()
	{
		ans=1;
		for(auto x:ed) __add(x.x,x.y);
		tim=0;
		for(auto x:V) if(deg[x]&&deg[x]!=2) {ans=0; break;}
		if(ans)
		{
			for(auto x:V) vis[x]=0;
			for(auto x:V)
			if(deg[x])
			{
				if(!vis[x]) tim++,dfs3(x,0);
			}
		}
		if(tim>=2) ans=0;
		for(auto x:V) _adj[x].clear(),vis[x]=deg[x]=0;
		V.clear();
		return ans;
	}
	vector<int> a;
	int solve(int n)
	{
		sum=0;
		dfs(1,0);
		int m=e.size();
		ff(i,0,m) if(dep[e[i].x]>dep[e[i].y]) swap(e[i].x,e[i].y);
		bool flag;
		ff(s,1,(1<<m))
		{
			flag=1;
			a.clear(); ed.clear(); V.clear();
			ff(i,0,m) if((1<<i)&s) a.pb(e[i].x),a.pb(e[i].y),ed.pb((edge){e[i].x,e[i].y});
			for(auto x:a) if(!dfn[x])
			{
				flag=0;
				break;
			}
			if(!flag) continue;
			build(a);
			ff(i,0,m) if((1<<i)&s) w[e[i].y]^=1,w[e[i].x]^=1;
			dfs2(rt,0);
			clr(rt,0);
			sum+=check();
			rt=0;
		}
		return sum;
	}
}
int n,m;
int main()
{
	n=read(); m=read();
	fo(i,1,m) Graph::add(read(),read());
	printf("%d\n",Graph::solve(n));
	return 0;
}