当前位置：首页 > article >正文

【题解】AT_abc386_d AtCoder Beginner Contest 386 D Diagonal Separation

article 2025/1/4 15:26:07

题目传送门

原题面链接

题目大意

给你一个 $\times N$ 的二维矩阵，矩阵里有三类元素：黑（B）、白（W）以及不确定。有 $M$ 个格子的颜色已给出，剩余的 $N^2-M$ 个格子都是不确定，现在要给它们涂颜色，自然是黑白任选其一。要求格子满足以下条件：

对于每一行，存在整数 $i$ 满足 $\le i \le N$ 且这一行前 $i$ 个格子都是黑格，其余均为白格。
对于每一列，存在整数 $i$ 满足 $\le i \le N$ 且这一列前 $i$ 个格子都是黑格，其余均为白格。

已经有颜色的格子不能修改颜色，请判断这样可不可行。

思路

看一眼数据范围，蒙了： $\le 1e9$ 是给人做的吗？？时间空间都会炸啊！别急，咱们想个 $O (M)$ 或者 $O(M*\log M)$ 时间复杂度的做法，然后用 C++ std::map 来存储不就好了吗？！~~C党P党对不起，你们手写离散化吧，后面二分什么的自己看着办，这篇题解主要使用STL。~~

大家思考一个问题：如果在某一行某一位置有一个白格，那么请问要是它后面还有一个黑格时，是否可行？（对于“列”也是一样的）。答案显然是否定的，这个没什么争议吧，不明白的看题。好的，接下来要是就写这一点点，那么恭喜你，样例四过不了。

Sample Input 4

2289 10
1700 1083 W
528 967 B
1789 211 W
518 1708 W
1036 779 B
136 657 B
759 1497 B
902 1309 B
1814 712 B
936 763 B

Sample Output 4

No

咦？根据前面的推论，这里一点问题也没有啊？！

数据真大，咱们画个简单的图解释一下。

请问这个图是否可行？答案是否定的，原因见下图。

好的，所以如果某个白格身后的某一列的这一行及以下有黑格（好像绕口令，自己理解一下），那么它也是不可行的。 列也是一样的。这一堆东西让我们想到了二分和二维map处理（详见代码）。

代码

/*
fx[x][y]=1 fy[y][x]=1 代表 (x, y) 有一个黑格
不懂迭代器的请自学，本文限于篇幅不再讲解
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

int n, m;
map<int, map<int, int> > fx, fy;

struct node
{
	int x, y;
	char c;
} ;

node p[200010];

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		char c;
		cin >> x >> y >> c;
		p[i] = (node){x, y, c};
		if (c == 'B')
		{
			fx[x][y] = 1;
			fy[y][x] = 1;
		}
	}
	for (int i = 1; i <= m; i++)
	{
		int x = p[i].x;
		int y = p[i].y;
		if (p[i].c == 'B')
			continue;
		map<int, map<int, int> >::iterator po = fx.lower_bound(x);
		map<int, int>::iterator pos;
		if (po != fx.end()) pos = fx[po->first].lower_bound(y);
		if (po != fx.end() && pos != fx[po->first].end())
		{
			cout << "No" << endl;
			return 0;
		}
		po = fy.lower_bound(y);
		if (po != fy.end()) pos = fy[po->first].lower_bound(x);
		if (po != fy.end() && pos != fy[po->first].end())
		{
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}