题解：P5983 [PA 2019] Osady i warownie 2

桑格莉娅不止一次地启发我做网格行走相关题目：

贴模型走路是一个很实用的技巧，可以在这类网格路径题中有效地去除一些重复冗余状态。

比如这道题，定义首末两行、两列为边缘部分，其他为非边缘部分，我们可以发现无论怎么在非边缘部分添加障碍，都存在至少两条合法路径，如下图：

TXT

OOOOO
O.X.O
OXX.O
OX.XO
OOOOO

X 代表障碍，O 代表边缘部分，. 是普通的空地。我们发现只要存在边缘部分，我们就不用管普通的空地。

但是边缘部分可能会改变。比如在一个空的

5 \times 5

网格中添加一个障碍：

TXT

OOOX.
O.OOO
O...O
O...O
OOOOO

不难发现障碍的作用是“如果处在原来的边缘部分，就把这个边缘部分挪个地方到左下角/右上角”，或者说“如果处在原来的边缘部分，则令自己左下角/右上角不可能再为边缘部分”。到底哪个角就要看自己原先处在左下角的边缘还是右上角的边缘。如果同时处在两类边缘，那说明没有路径可以走了，此时输出 TAK，我们也顺便获得了是否有路径的充要条件。

边缘的修改是可以均摊的，因为每个点最多被一类边缘用一次，于是写一个事件驱动模拟。其中需要找最大最小值，set 常数大，换成堆就可以了。

CPP

 /* NE_Cat 4.1 */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

const int N = 100010;
typedef pair < int, int > PII;
struct Point {int x, y, val, id;} p[N * 10];
int n, m, k, lim[4][N]; map < PII, int > mp;
priority_queue < PII, vector < PII >, greater < PII > > conS[4][N];
priority_queue < PII > conL[4][N];

inline bool check(int opt, Point pos)
{
	if(opt == 0 && pos.y <= lim[0][pos.x]) return true;
	if(opt == 1 && pos.x >= lim[1][pos.y]) return true;
	if(opt == 2 && pos.y >= lim[2][pos.x]) return true;
	if(opt == 3 && pos.x <= lim[3][pos.y]) return true;
	return false;
}
inline void search_A(Point pos);
inline void search_B(Point pos);
inline void get(int opt, int id);
inline void get(int opt, int id)
{
	if(opt == 0)
	{
		while(!conS[0][id].empty() && conS[0][id].top().first <= lim[0][id])
		{
			PII cur = conS[0][id].top();
			conS[0][id].pop();
			search_A(p[cur.second]);
		}
	}
	else if(opt == 1)
	{
		while(!conL[1][id].empty() && conL[1][id].top().first >= lim[1][id])
		{
			PII cur = conL[1][id].top();
			conL[1][id].pop();
			search_A(p[cur.second]);
		}
	}
	else if(opt == 2)
	{
		while(!conL[2][id].empty() && conL[2][id].top().first >= lim[2][id])
		{
			PII cur = conL[2][id].top();
			conL[2][id].pop();
			search_B(p[cur.second]);
		}
	}
	else
	{
		while(!conS[3][id].empty() && conS[3][id].top().first <= lim[3][id])
		{
			PII cur = conS[3][id].top();
			conS[3][id].pop();
			search_B(p[cur.second]);
		}
	}
}
inline void search_A(Point pos)
{
//	cerr << "A " << pos.x << " " << pos.y << '\n';
	if(pos.x - 1 >= 1)
	{
		lim[0][pos.x - 1] = max(lim[0][pos.x - 1], pos.y + 1);
		get(0, pos.x - 1);
	}
	if(pos.y + 1 <= m)
	{
		lim[1][pos.y + 1] = min(lim[1][pos.y + 1], pos.x - 1);
		get(1, pos.y + 1);
	}
}
inline void search_B(Point pos)
{
//	cerr << "B " << pos.x << " " << pos.y << '\n';
	if(pos.x + 1 <= n)
	{
		lim[2][pos.x + 1] = min(lim[2][pos.x + 1], pos.y - 1);
		get(2, pos.x + 1);
	}
	if(pos.y - 1 >= 1)
	{
		lim[3][pos.y - 1] = max(lim[3][pos.y - 1], pos.x + 1);
		get(3, pos.y - 1);
	}
}

int main()
{
//	freopen("text.in", "r", stdin);
//	freopen("prog.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 1; i <= k; ++i) cin >> p[i].x >> p[i].y >> p[i].val, p[i].id = i;
	memset(lim[1], 0x3f, sizeof(lim[1]));
	memset(lim[2], 0x3f, sizeof(lim[2]));
	lim[0][n] = m; lim[1][1] = 1;
	lim[2][1] = 1; lim[3][m] = n;
	for(int i = 1, v = 0; i <= k; ++i)
	{
		p[i].x ^= v, p[i].y ^= v;
		p[i].x %= n, p[i].y %= m;
		++p[i].x, ++p[i].y;
//		cerr << p[i].x << " " << p[i].y << " +++++++++++++++++++++++++++++\n";
		if(mp[{p[i].x, p[i].y}]) {cout << "NIE" << '\n'; continue;}
		mp[{p[i].x, p[i].y}] = true;
		if(!check(0, p[i]) && !check(1, p[i]) && !check(2, p[i]) && !check(3, p[i]))
		{
			cout << "NIE" << '\n';
			conS[0][p[i].x].push({p[i].y, i});
			conL[1][p[i].y].push({p[i].x, i});
			conL[2][p[i].x].push({p[i].y, i});
			conS[3][p[i].y].push({p[i].x, i});
		}
		else if((check(0, p[i]) || check(1, p[i])) && (check(2, p[i]) || check(3, p[i])))
		{
			cout << "TAK" << '\n';
			v ^= p[i].val; mp[{p[i].x, p[i].y}] = false;
		}
		else if(check(0, p[i]) || check(1, p[i])) cout << "NIE" << '\n', search_A(p[i]);
		else cout << "NIE" << '\n', search_B(p[i]);
	}
	return 0;
}
/*

*/

题解：P5983 [PA 2019] Osady i warownie 2

文章操作

相关推荐

评论

题解：P5983 [PA 2019] Osady i warownie 2