小澳的方阵
(matrix.cpp/c/pas)
【题目描述】
小澳最近迷上了考古，他发现秦始皇的兵马俑布局十分有特点，热爱钻研的小澳打算在电脑上还原这个伟大的布局。
他努力钻研，发现秦始皇布置兵马俑是有一定规律的。兵马俑阵总共有n行m列，秦始皇在布置的时候每次会指定一行或一列，然后指定一个兵种，使得这一行或者这一列上全部放上这一个兵种。如果这一行上以前放过其它的兵种，那么他会拔掉以前的兵种改成现在他命令的兵种。
小澳从秦朝的文献中找到了布置这个方阵的操作顺序，他希望你能告诉他布局完成后整个兵马俑阵是什么样子的。
【输入格式】
输入文件为matrix.in。
输入文件共q+1行。
输入文件第1行包括三个正整数n，m，q，分别表示兵马俑阵的行数和列数以及秦始皇总的操作数。
接下来q行，每行三个正整数，x,y,z，x表示操作种类，若x=1表示给第y行(y<=n)全部放上z这个兵种，若x=2，则表示给第y列(y<=m)全部放上z这个兵种，数据保证z<=2^31-1。
【输出格式】
输出文件名为matrix.out。
输出文件共n行，每行m个整数，分别用空格隔开。表示最后方阵上每个位置放的兵种，如果某个位置没有被操作过输出0。
【输入输出样例1】
|
matrix.in |
matrix.out |
|
3 3 3 1 1 3 2 2 1 1 2 2 |
3 1 3 2 2 2 0 1 0 |
【输入输出样例1说明】
【输入输出样例2】
|
matrix.in |
matrix.out |
|
5 3 5 1 1 1 1 3 1 1 5 1 2 1 1 2 3 1 |
1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 |
【数据规模与约定】
对于前20%的数据，n*m<=25。
对于前30%的数据，q<=2000。
对于100%的数据，n,m<=1000,n*m<=10^5,q<=10^6。
【提示】
因为本题输入文件较大，使用c++的选手可能会因为使用cin和cout导致超时。
解决方法是可以加<cstdio>库后使用scanf()函数和printf()来避免这种问题的出现。如果有不会使用上面两个输入输出函数的选手可以向在场的工作人员或监考老师求助。
————————————————————————分割线——————————————————————
分析：
因为放兵种和染色十分相似，所以后面就称为染色好了。
【algorithm1】 模拟。每次涂色对矩阵的一行或者一列操作。最后输出时输出矩阵即可。 时间复杂度 O(k*n)，空间复杂度(n*m)。可以通过 123 的数据点。
【algorithm2】 注意到每次只染色一行或者一列，那么我们最后输出第 i 行第 j 列的数字是 多少的时候只需要看一下最后一次 i 行和第 j 行被染了什么颜色，所以我们需要 对每一行和一列记录最后一次染色的颜色。 但是我们也需要比较是行比列后染色还是列比行后染色，所以我们还需要记 录一下每行每列染色的最后时间。 综上，我们只需要对每一行和每一列开两个记录的值：一个记录最后一次染 色的时间，一个记录最后一次染色的颜色，然后比较 i 行和 j 列的时间大小即可 确定这个位置的颜色了。 时间复杂度 O(k+m*n)，空间复杂度(n+m)。可以通过所有数据点。
原题来自 codeforces: http://codeforces.com/problemset/problem/631/B
代码：
1 #include "bits/stdc++.h" 2 3 using namespace std ; 4 const int maxN = 11000 ; 5 const int INF = 2147483647 ; 6 struct Matrix { int col , time ;}; 7 8 Matrix hang[ maxN ] , lie[ maxN ] ; 9 10 int main ( ) { 11 int N , M , Q ; 12 freopen("sbsb.out","w",stdout); 13 scanf ( "%d%d%d" , &N , &M , &Q ) ; 14 for ( int i=1 ; i<=Q ; ++i ) { 15 int op , target , col_num ; 16 scanf ( "%d" , &op ) ; 17 if ( op==1 ) { 18 scanf ( "%d %d" , &target , &col_num ) ; 19 hang[ target ].col = col_num ; 20 hang[ target ].time = i ; 21 } 22 else if ( op==2 ) { 23 scanf ( "%d %d" , &target , &col_num ) ; 24 lie[ target ].col = col_num ; 25 lie[ target ].time = i ; 26 } 27 } 28 for ( int i=1 ; i<=N ; ++i ) { 29 for ( int j=1 ; j<=M ; ++j ) { 30 if ( lie[ j ].time > hang[ i ].time ) { 31 printf ( "%d " , lie[ j ].col ); 32 } 33 else { 34 printf ( "%d " , hang[ i ].col ); 35 } 36 } 37 printf ( " " ) ; 38 } 39 return 0 ; 40 }
2016-10-03 20:22:14
(完)