NOI 2016 网格

发表于 | 更新于

卡常2h，依旧排名倒数

56分做法

对整张平面图求割点 

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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int NM=1e6+11,MAXC=1e5+11,dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int n,m,c;
struct point{int x,y;}p[MAXC];
inline int ID(int x,int y){return (x-1)*m+y;}
inline bool Inside(int x,int y){return 1<=x && x<=n && 1<=y && y<=m;}
bool isblock[NM];
namespace Graph
{
	const int PS=NM,ES=PS<<2;
	struct Edge
	{
		Edge *pre;
		int to;
		Edge(Edge *pre,int to):pre(pre),to(to){}
	}*POOL=(Edge*)malloc(ES*sizeof(Edge)),*ME=POOL,*id[PS];
	void Adde(int f,int t){id[f]=new(ME++) Edge(id[f],t);}
	int dfn[PS],low[PS],dc,stack[PS],top,sc;
	bool instack[PS],iscut[PS],hasCut;
	void DFS(int pos,int fa)
	{
		instack[stack[++top]=pos]=1;
		dfn[pos]=low[pos]=++dc;
		int sonc=0;
		for(Edge *e=id[pos];e;e=e->pre)
		{
			int u=e->to;
			if(!dfn[u])
			{
				sonc++;
				DFS(u,pos);
				chkmn(low[pos],low[u]);
				iscut[pos]|=(fa!=0 && low[u]>=dfn[pos]);
			}
			else if(instack[u])
				chkmn(low[pos],dfn[u]);
		}
		iscut[pos]|=(fa==0 && sonc>1);
		if(low[pos]==dfn[pos])
		{
			++sc;
			while(stack[top+1]!=pos)
				instack[stack[top--]]=0;
		}
		hasCut|=iscut[pos];
	}
}using namespace Graph;
void Reset()
{
	ME=POOL;memset(id,0,sizeof(id));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(instack,0,sizeof(instack));
	memset(iscut,0,sizeof(iscut));
	memset(isblock,0,sizeof(isblock));//..
	hasCut=0;
	dc=sc=0;
}
int Work()
{
	get(n),get(m),get(c);
	for(int i=1;i<=c;++i)
	{
		get(p[i].x),get(p[i].y);
		isblock[ID(p[i].x,p[i].y)]=1;
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(!isblock[ID(i,j)])
				for(int d=0;d<4;++d)
				{
					int x=i+dx[d],y=j+dy[d];//i+dy[d]..
					if(Inside(x,y) && !isblock[ID(x,y)])
						Adde(ID(i,j),ID(x,y));
				}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
		{
			int id=ID(i,j);
			if(!isblock[id] && !dfn[id])
				DFS(id,0);
		}
	if(n*m-c<=1 || (n*m-c==2 && sc==1)) return -1;
	if(sc!=1) return 0;
	if(hasCut) return 1;
	return 2;
}
int main()
{
	int T;get(T);
	while(T--)
		Reset(),put(Work()),putchar('\n');
	return 0;
}

84分做法

把相邻蛐蛐座标的间隔缩到3以内，求割点 

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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
typedef long long ll;
const int NM=1e6+11,MAXC=1e5+11,dx[]={1,-1,0,0},dy[]={0,0,1,-1};
using std::sort;
using std::min;

int n,m,c;
struct point{int x,y;point(int x=0,int y=0):x(x),y(y){}}p[MAXC];
bool cmp_x(const point &a,const point &b){return a.x<b.x;}
bool cmp_y(const point &a,const point &b){return a.y<b.y;}
inline int ID(int x,int y){return (x-1)*m+y;}
inline bool Inside(int x,int y){return 1<=x && x<=n && 1<=y && y<=m;}
bool isblock[NM];
namespace Graph
{
	const int PS=NM,ES=PS<<2;
	struct Edge
	{
		Edge *pre;
		int to;
		Edge(Edge *pre,int to):pre(pre),to(to){}
	}*POOL=(Edge*)malloc(ES*sizeof(Edge)),*ME=POOL,*id[PS];
	void Adde(int f,int t){id[f]=new(ME++) Edge(id[f],t);}
	int dfn[PS],low[PS],dc,stack[PS],top,sc;
	bool instack[PS],iscut[PS],hasCut;
	void DFS(int pos,int fa)
	{
		instack[stack[++top]=pos]=1;
		dfn[pos]=low[pos]=++dc;
		int sonc=0;
		for(Edge *e=id[pos];e;e=e->pre)
		{
			int u=e->to;
			if(!dfn[u])
			{
				sonc++;
				DFS(u,pos);
				chkmn(low[pos],low[u]);
				iscut[pos]|=(fa!=0 && low[u]>=dfn[pos]);
			}
			else if(instack[u])
				chkmn(low[pos],dfn[u]);
		}
		iscut[pos]|=(fa==0 && sonc>1);
		if(low[pos]==dfn[pos])
		{
			++sc;
			while(stack[top+1]!=pos)
				instack[stack[top--]]=0;
		}
		hasCut|=iscut[pos];
	}
}using namespace Graph;
void Reset()
{
	Graph::ME=Graph::POOL;memset(id,0,sizeof(id));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(instack,0,sizeof(instack));
	memset(iscut,0,sizeof(iscut));
	memset(isblock,0,sizeof(isblock));//..
	hasCut=0;
	dc=sc=0;
}
const int D=3;
void Transform()
{
	int delta;p[c+1]=point(n,m);
	sort(p+1,p+1+c,cmp_x);
	delta=0;
	for(int i=1;i<=c+1;++i)
	{	
		p[i].x-=delta;
		if(p[i].x>p[i-1].x+D)
		{
			delta+=p[i].x-(p[i-1].x+D);
			p[i].x=p[i-1].x+D;
		}	
	}
	sort(p+1,p+1+c,cmp_y);
	delta=0;
	for(int i=1;i<=c+1;++i)
	{
		p[i].y-=delta;
		if(p[i].y>p[i-1].y+D)
		{
			delta+=p[i].y-(p[i-1].y+D);
			p[i].y=p[i-1].y+D;
		}
	}
	n=p[c+1].x,m=p[c+1].y;
}
int Work()
{
	static int Case;
	++Case;

	get(n),get(m),get(c);
	for(int i=1;i<=c;++i)
		get(p[i].x),get(p[i].y);
	ll diff=(ll)n*m-c;
	Transform();
	for(int i=1;i<=c;++i)
		isblock[ID(p[i].x,p[i].y)]=1;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(!isblock[ID(i,j)])
				for(int d=0;d<4;++d)
				{
					int x=i+dx[d],y=j+dy[d];//i+dy[d]..
					if(Inside(x,y) && !isblock[ID(x,y)])
						Adde(ID(i,j),ID(x,y));
				}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
		{
			int id=ID(i,j);
			if(!isblock[id] && !dfn[id])
				DFS(id,0);
		}
	if(diff<=1 || (diff==2 && sc==1)) return -1;
	if(sc!=1) return 0;
	if(hasCut || n==1 || m==1) return 1;
	return 2;
}
int main()
{
	int T;get(T);
	while(T--)
		Reset(),put(Work()),putchar('\n');
	return 0;
}

100分做法

从56到84，主要的思路是把图离散化。 84到100也是。 假设存在割点，那么一定是有障碍物围成了一个只有一个缺口的圈。所以只对与这个圈八联通的跳蚤建图求割点。 然后会发现，只处理与蛐蛐直接八联通的跳蚤会出现一些反例，那就每只蛐蛐扩两圈，处理24只跳蚤，就可以了。

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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
typedef long long ll;
using std::vector;
const int MAXC=1e5+11,PS=MAXC*25,//*24
	  dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int n,m,c;
struct point{int x,y;point(){}point(int x,int y):x(x),y(y){}}p[MAXC];
#define HashCode(a) ((ll)(a.x-1)*m+a.y)
#define Inside(p) (1<=p.x && p.x<=n && 1<=p.y && p.y<=m)
bool isblock[PS];
point nodes[PS];int noc;
namespace _Hash_
{
	const int SIZE=PS,P=2499997;
	struct Node
	{
		Node *pre;
		ll key;int val;
		Node(Node *pre,ll key,int val):pre(pre),key(key),val(val){}
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL;
	struct Hash
	{
		Node *id[P];
		Node *Find(ll key)
		{
			register int hs=key%P;
			for(register Node *p=id[hs];p;p=p->pre)
				if(p->key==key)
					return p;
			return 0;
		}
		Node *Find(point p){return Find(HashCode(p));}
		int &operator [](point p)
		{
			ll key=HashCode(p);
			Node *ptr=Find(key);
			if(!ptr)
			{
				int hs=key%P;
				ptr=id[hs]=new(ME++) Node(id[hs],key,-1);
			}
			return ptr->val;
		}
		void Reset(){memset(id,0,sizeof(id));}
	}ref;
}using namespace _Hash_;
bool BlockAround(point pos)
{
	for(int mx=-1;mx<=1;++mx)
		for(int my=-1;my<=1;++my)
		{
			point u(pos.x+mx,pos.y+my);
			if(Inside(u) && ref.Find(u) && isblock[ref[u]]) return 1;
		}
	return 0;
}
namespace _Graph_
{
	const int PS=::PS,ES=PS<<2;
	struct Edge
	{
		Edge *pre;
		int to;
		Edge(Edge *pre,int to):pre(pre),to(to){}
	}*POOL=(Edge*)malloc(ES*sizeof(Edge)),*ME=POOL,*id[PS];
	void Adde(int f,int t)	{id[f]=new(ME++) Edge(id[f],t);}	
	int dfn[PS],low[PS],dc,stack[PS],sn[PS],top,sc;
	bool instack[PS],iscut[PS],hasCut;
	void DFS(int pos,int fa)
	{
		instack[stack[++top]=pos]=1;
		dfn[pos]=low[pos]=++dc;
		int sonc=0;
		for(Edge *e=id[pos];e;e=e->pre)
		{
			int u=e->to;
			if(!dfn[u])
			{
				sonc++;
				DFS(u,pos);
				chkmn(low[pos],low[u]);
				iscut[pos]|=(fa!=0 && low[u]>=dfn[pos]);
			}
			else if(instack[u])
				chkmn(low[pos],dfn[u]);
		}
		iscut[pos]|=(fa==0 && sonc>1);
		if(low[pos]==dfn[pos])
		{
			++sc;
			while(stack[top+1]!=pos)
			{
				sn[stack[top]]=sc;
				instack[stack[top--]]=0;
			}
		}
		hasCut|=(iscut[pos] && BlockAround(nodes[pos]));
	}
	int bn[PS],bc=0;
	void Maximal(point pos,int bnum)
	{
		bn[ref[pos]]=bnum;
		for(int mx=-1;mx<=1;++mx)
			for(int my=-1;my<=1;++my)
			{
				if(mx==0 && my==0) continue;
				point u(pos.x+mx,pos.y+my);	
				if(Inside(u) && ref.Find(u) && !bn[ref[u]])
					Maximal(u,bnum);
			}
	}
}using namespace _Graph_;
vector<int> fleas[MAXC];
void Reset()
{
	memset(isblock,0,sizeof(isblock));
	noc=0;
	_Hash_::ME=_Hash_::POOL;
	ref.Reset();
	_Graph_::ME=_Graph_::POOL;
	memset(id,0,sizeof(id));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	dc=0;
	memset(sn,0,sizeof(sn));//?
	sc=0;
	memset(iscut,0,sizeof(iscut));
	hasCut=0;
	memset(bn,0,sizeof(bn));
	for(int i=1;i<=bc;++i) fleas[i].clear();
	bc=0;
	memset(stack,0,sizeof(stack));//stack不清0
}

bool isCon()
{
	for(int i=1;i<=c;++i)
		if(!bn[i]) Maximal(p[i],++bc);
	for(int i=1;i<=c;++i)
		for(int mx=-2;mx<=2;++mx)
			for(int my=-2;my<=2;++my)
			{
				if(mx==0 && my==0) continue;
				point u(p[i].x+mx,p[i].y+my);
				if(!Inside(u)) continue;
				int &idx=ref[u];
				if(idx==-1) 
				{
					nodes[idx=++noc]=u;//p[i]..
					fleas[bn[i]].push_back(idx);
				}
			}
	for(int i=c+1;i<=noc;++i)
		for(int d=0;d<4;++d)
		{
			point u(nodes[i].x+dx[d],nodes[i].y+dy[d]);
			int idx;
			if(Inside(u) && ref.Find(u) && !isblock[idx=ref[u]]) Adde(i,idx);
		}
	for(int i=c+1;i<=noc;++i)
		if(!dfn[i]) 
			DFS(i,0);
	for(int i=1;i<=bc;++i)
	{
		int pred=0;
		for(vector<int>::iterator it=fleas[i].begin();it!=fleas[i].end();++it)
			if(!pred) pred=sn[*it];
			else if(pred!=sn[*it]) return 0; 
	}
	return 1;
}
int Work()
{
	static int Case;
	++Case;

	get(n),get(m),get(c);
	for(int i=1;i<=c;++i)
	{
		get(p[i].x),get(p[i].y);
		nodes[ref[p[i]]=++noc]=p[i];
		isblock[noc]=1;
	}
	ll diff=(ll)n*m-c;
	bool Con=isCon();
	if(diff<=1 || (diff==2 && Con)) return -1;
	if(!Con) return 0;
	if(hasCut || n==1 || m==1) return 1;
	return 2;
}
int main()
{
	freopen("input","r",stdin);
	int T;get(T);
	while(T--)
		Reset(),put(Work()),putchar('\n');
	return 0;
}

总的来看性价比最高的是写84分的离散化。