洛谷P9117 [春季测试 2023] 涂色游戏 题解

题目传送门

Description

给定  行  列的矩形，初始全为白色。存在 次操作，每次操作可以将一整行或一整列覆盖成任意颜色。求最终矩形上每个点的颜色。

Solution

容易想到，矩形最终的状态是多次操作叠加而成，而靠前的操作可能会全被后面的操作给完全覆盖，所以这次操作显然对答案没有任何贡献。由此我们可以考虑如何剪掉这次操作，让程序只会计算真正有贡献的操作。

我们可以选择离线倒序处理所有操作，这样就可以避免覆盖的操作。设  为当前行或当前列是否已经涂上了最新的颜色，用以剪枝来优化复杂度。

要注意矩阵的存储必须用 ，因为数据范围实在是过大，普通  一定会  的。

时间复杂度  （但是实际复杂度远远不到）  空间复杂度 

AC Code

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN=1e6+10;
int T,m,n,q;
vector <int> g[MAXN];
int ext[MAXN][2];
struct operation{
int op,x,c;
}o[MAXN];
int main()
{
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
cin>>T;while(T–){
cin>>n>>m>>q;
for(int i=1;i<=max(m,n);i++) ext[i][0]=ext[i][1]=0;
for(int i=1;i<=n;i++) g[i].clear(),g[i].resize(m+1);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) g[i][j]=-1;
for(int i=1;i<=q;i++) cin>>o[i].op>>o[i].x>>o[i].c;
for(int i=q;i>=1;i–)
{
if(ext[o[i].x][o[i].op]==0)
{
ext[o[i].x][o[i].op]=1;
if(o[i].op==0)
{
for(int j=1;j<=m;j++) if(g[o[i].x][j]==-1) g[o[i].x][j]=o[i].c;
}
else
{
for(int j=1;j<=n;j++) if(g[j][o[i].x]==-1) g[j][o[i].x]=o[i].c;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cout<<(g[i][j]==-1?0:g[i][j])<<' ';
cout<<'\\n';
}
}
return 0;
}