题目大意
小澳最近迷上了考古，他发现秦始皇的兵马俑布局十分有特点，热爱钻研的小澳打算在电脑上还原这个伟大的布局。
他努力钻研，发现秦始皇布置兵马俑是有一定规律的。兵马俑阵总共有n行m列，秦始皇在布置的时候每次会指定一行或一列，然后指定一个兵种，使得这一行或者这一列上全部放上这一个兵种。如果这一行上以前放过其它的兵种，那么他会拔掉以前的兵种改成现在他命令的兵种。
小澳从秦朝的文献中找到了布置这个方阵的操作顺序，他希望你能告诉他布局完成后整个兵马俑阵是什么样子的。
题目分析
记录一下每一行每一列最后更新的时间与数值，然后最后判断一下最后更新的是行还是列。
时间复杂度$O(q+n^2)$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int n,m,q,Row[1005],Rowpos[1005],Line[1005],Linepos[1005];
int main() {
n=Get_Int();
m=Get_Int();
q=Get_Int();
for(int i=1; i<=q; i++) {
int opt=Get_Int(),x=Get_Int(),v=Get_Int();
if(opt==1)Row[x]=v,Rowpos[x]=i;
else Line[x]=v,Linepos[x]=i;
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++)
if(Rowpos[i]>Linepos[j])printf("%d ",Row[i]);
else printf("%d ",Line[j]);
putchar('\n');
}
return 0;
}
|
