罗伯特清崎说的网络营销是什么_制作官网的公司推荐_成长电影在线观看免费_百度官网认证多少钱一年

题目传送门

• 原题面链接

题目大意

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

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

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

思路

看一眼数据范围，蒙了：$N\le 1e9$ 是给人做的吗？？时间空间都会炸啊！别急，咱们想个 $O(M)$ 或者 $O(M\ast \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;
}

总结

是的，这一堆乱七八糟的东西居然 AC 了。

显然这不是什么最优解，时间复杂度也令人不悦，如果您有其他做法或优化请在评论区留言或私信，谢谢。

参考资料及文献

https://zh.cppreference.com/w/cpp/container/map