2020 CCPC 秦皇岛 B.Bounding Wall @ Wings            分类 ACM
发布于 星期五, 十二月 11 日, 2020 年
更新于 星期二, 七月 20 日, 2021 年

题目

题意

$T$组测试. 给出$n \times m$的$01$矩阵$M$. $q$次操作.

  • 1 x y 将矩阵中$(x, y)$取反
  • 2 x y 表示查询

查询如下:

找一个面积最大的矩形边框(平行与坐标轴), 满足:

  1. 边框上的点都是$0$
  2. $(x, y)$在边框上

$1 \le T, n, m, q \le 10^3$

题解

先来看询问.

首先很容易发现, 我们可以枚举$(x, y)$在矩阵的哪一条边上, 这样只需要做$4$次同样的算法即可.

下面仅仅考虑$(x, y)$在下边的做法.

通过$O(n^2)$的预处理, 可以很快知道$(x, y)$左右两边最近的$1$. 设为$L$和$R$

然后考虑枚举上边所在的行$u$. 现在只需要知道两根竖直边在哪一列上即可. $j$列能够作为竖直边的充要条件是$j \in (L, R), \forall i \in [u, x], M_{i, j} = 0$. 显然要使面积最大, 应该要让左竖直边的下标$j_l$尽量小, 右竖直边的下标$j_r$尽量大.

对于一个$1$, 只要他行$(u, x]$中, 他的行号其实是不重要的. 如果$i(i \in[u, x])$行在$(L, R)$之间出现了$1$, 我们其实可以直接认为这个$1$在$u+1$行. 一种考虑方式是尝试从大到小枚举$u$, 让$u+1$以下的行的信息"压"到$u+1$上, 如下图:

压到u+1上

然后在$u$行找左右两边最近的$1$, 见上图(右), 然后看$u+1$行对应的左右位置, 如果是$0$(右图右箭头下方), 那么就找到了一侧的竖直边, 上图即$c_2$; 如果是$1$(右图左箭头下方), 那么还得找$u+1$行$c_1 + 1$所在"连通块"的最右端(或最左端, 看情况)

“连通块"都出来了, 还不知道用并查集吗? 并查集维护一下每个连通块最左边和最右边的点的下标即可, 详见代码.

不过, 我们不能直接枚举每行的$1$, 否则复杂度会是$O(n^2)$, 加上查询总复杂度有$O(n^3)$, 过不了.

从大到小做的话, 可以发现, 如果一列上有多个$1$, 只需考虑低的$1$即可. 可以在$O(n^2)$内预处理出在$(x, y)$上方离$(x, y)$最近的$1$的位置. 只考虑这些$1$, 就可以在$O(n + m) = O(n)$的时间完成了.

具体来说, 对每一行开一个池子(vector) pool[] , 对于每一个在$(L, R)$中的$j$, 快速查询到$(x, j)$点上方的$1$的行号$i$, 然后把$j$压入pool[i]. 当枚举到$i$行的时候, 把 pool[i] 中的$j$拿出来处理就行.

到这里, 询问的关键算法就结束了. 复杂度$O(n^2)$

然后需要把矩阵旋转$3$次, 每一次跑一遍, 答案取最大即可.

但是! 不能"在线"旋转, 否则每查询一次, 都要花$O(n^2)$的时间旋转, 这样总复杂度就是$O(n^3)$了. 可以离线, 即对每个方向的矩阵跑一遍所有询问, 记录答案. 转了以后重新跑一遍所有询问, 更新答案. 这样总共只需要转$3$下, 旋转的复杂度$O(n^2)$不会加在询问$O(n)$上.

注意旋转了以后, 操作中的$(x, y)$也需要旋转到相应的点$(x', y')$上

每次旋转了以后, 也可以用$O(n^2)$的时间重新预处理数组l[][], r[][], up[][]了.

最后看简单一点的修改.

矩阵中的值直接取反, 一个点的值改变, 只会改变$x'$行的l[][], r[][]和$y'$列的up[][], 直接花$O(n)$重新处理该行或列即可.

总复杂度$O(n^2)$

代码
const int maxn = 1e3+10;

struct Question {
	int op, x, y;
};

int t, n, m, q, N, M;
char str[maxn][maxn];
int layout[maxn][maxn], ans[maxn];
int l[maxn][maxn], r[maxn][maxn], up[maxn][maxn];
int fa[maxn], mark[maxn], mx[maxn], mn[maxn];
vector<int> pool[maxn];
vector<Question> qs;

void UpdAns(int id, int a) {
	ans[id] = max(ans[id], a);
}

int Find(int x) {
	return x == fa[x] ? x : fa[x] = Find(fa[x]);
}

void Union(int x, int y) {
	x = Find(x), y = Find(y);
	fa[x] = y;
	mn[y] = min(mn[y], mn[x]);
	mx[y] = max(mx[y], mx[x]);
}

void sol(int id, int rot) {
	int op = qs[id].op, x = qs[id].x, y = qs[id].y;
	if (rot == 1) {
		int xx = x, yy = y;
		x = yy, y = N - xx + 1;
	}
	else if (rot == 2) {
		x = N - x + 1, y = M - y + 1;
	}
	else if (rot == 3) {
		int xx = x, yy = y;
		x = M - yy + 1, y = xx;
	}
	if (op == 1) {
		layout[x][y] ^= 1;
		//只需要维护当前行或者列的值
		for (int j = 1; j <= m; j++)
			l[x][j] = layout[x][j] ? j : l[x][j-1];
		for (int j = m; j; j--)
			r[x][j] = layout[x][j] ? j : r[x][j+1];
		for (int i = 1; i <= n; i++)
			up[i][y] = layout[i][y] ? i : up[i-1][y];
	}
	else {
		if (!layout[x][y]) {
			//L, R是最左, 最右的不可放置点
			int L = l[x][y], R = r[x][y];
			UpdAns(id, R - L - 1);
			//清空pool
			for (int i = 1; i < x; i++)
				pool[i].clear();
			//计算pool, 初始化fa, mark
			for (int j = L + 1; j <= R - 1; j++)
				pool[up[x][j]].push_back(j);
			for (int j = L; j <= R; j++) {
				mark[j] = 0;
				fa[j] = mn[j] = mx[j] = j;
			}
			mark[L] = mark[R] = 1;

			//枚举上边
			for (int i = x - 1; i; i--) {
				//更新并查集, 加入当前行的不可放置点
				for (auto j : pool[i]) if (!mark[j]) {
					mark[j] = 1;
					if (mark[j-1])
						Union(j, j-1);
					if (mark[j+1])
						Union(j, j+1);
				}
				int cur_L = max(L, l[i][y]);
				cur_L = Find(cur_L);
				cur_L = mx[cur_L];
				int cur_R = min(R, r[i][y]);
				cur_R = Find(cur_R);
				cur_R = mn[cur_R];
				if (cur_L < y && y < cur_R)
					UpdAns(id, (cur_R - cur_L - 1) * (x - i + 1));
			}
		}
	}
}

//初始化l, r, up
void Init() {
	for (int i = 1; i <= n; i++) {
		l[i][0] = 0;
		for (int j = 1; j <= m; j++)
			l[i][j] = layout[i][j] ? j : l[i][j-1];
	}
	for (int i = 1; i <= n; i++) {
		r[i][m+1] = m+1;
		for (int j = m; j; j--)
			r[i][j] = layout[i][j] ? j : r[i][j+1];
	}
	for (int j = 1; j <= m; j++) {
		up[0][j] = 0;
		for (int i = 1; i <= n; i++)
			up[i][j] = layout[i][j] ? i : up[i-1][j];
	}
}

//旋转layout
void Rotate(int rot) {
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++) {
			if (rot == 1)
				layout[j][N - i + 1] = str[i][j] == '.';
			else if (rot == 2)
				layout[N - i + 1][M - j + 1] = str[i][j] == '.';
			else if (rot == 3)
				layout[M - j + 1][i] = str[i][j] == '.';
		}
	swap(n, m);
}

int main() {
	scanf("%d", &t);
	for (int kase = 1; kase <= t; kase++) {
		scanf("%d%d%d", &n, &m, &q);
		N = n, M = m;
		for (int i = 1; i <= n; i++)
			scanf("%s", str[i] + 1);
		qs.clear();
		for (int qq = 1; qq <= q; qq++) {
			int op, x, y;
			scanf("%d%d%d", &op, &x, &y);
			qs.push_back(Question{op, x, y});
		}
		int sz = qs.size();
		for (int i = 0; i < sz; i++)
			ans[i] = 0;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				layout[i][j] = str[i][j] == '.';
		Init();
		for (int i = 0; i < sz; i++)
			sol(i, 0);
		for (int cnt = 1; cnt <= 3; cnt++) {
			Rotate(cnt);
			Init();
			for (int i = 0; i < sz; i++)
				sol(i, cnt);
		}
		printf("Case #%d:\n", kase);
		for (int i = 0; i < sz; i++) if (qs[i].op == 2)
			printf("%d\n", ans[i]);
	}
	return 0;
}
留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了
  15. 2021团体程序设计天体赛(CCCC) 个人二等奖
  16. 2021 西电 miniL CTF 优胜奖
  17. 2021 西电ACM校赛 第9名 金牌
  18. 2021 西电数模校赛 二等奖
  19. 2021 第15届IEEE 第48名
  20. 2021 CCPC 桂林站 打星

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch