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

题目传送门Description给定行列的矩形初始全为白色。存在次操作每次操作可以将一整行或一整列覆盖成任意颜色。求最终矩形上每个点的颜色。Solution容易想到矩形最终的状态是多次操作叠加而成而靠前的操作可能会全被后面的操作给完全覆盖所以这次操作显然对答案没有任何贡献。由此我们可以考虑如何剪掉这次操作让程序只会计算真正有贡献的操作。我们可以选择离线倒序处理所有操作这样就可以避免覆盖的操作。设为当前行或当前列是否已经涂上了最新的颜色用以剪枝来优化复杂度。要注意矩阵的存储必须用因为数据范围实在是过大普通一定会的。时间复杂度但是实际复杂度远远不到 空间复杂度AC Code#include bits/stdc.h using namespace std; constexpr int MAXN1e610; 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); cinT;while(T--){ cinnmq; for(int i1;imax(m,n);i) ext[i][0]ext[i][1]0; for(int i1;in;i) g[i].clear(),g[i].resize(m1); for(int i1;in;i) for(int j1;jm;j) g[i][j]-1; for(int i1;iq;i) cino[i].opo[i].xo[i].c; for(int iq;i1;i--) { if(ext[o[i].x][o[i].op]0) { ext[o[i].x][o[i].op]1; if(o[i].op0) { for(int j1;jm;j) if(g[o[i].x][j]-1) g[o[i].x][j]o[i].c; } else { for(int j1;jn;j) if(g[j][o[i].x]-1) g[j][o[i].x]o[i].c; } } } for(int i1;in;i){ for(int j1;jm;j) cout(g[i][j]-1?0:g[i][j]) ; cout\n; } } return 0; }