hdu_5671 矩阵行列移动等

超、凢脫俗 2022-08-21 10:39 161阅读 0赞

有一个nn行mm列的矩阵(1 \leq n \leq 1000 ,1 \leq m \leq 1000 )(1≤n≤1000,1≤m≤1000)，在这个矩阵上进行qq  (1 \leq q \leq 100,000)(1≤q≤100,000) 个操作：
    
    1 x y: 交换矩阵MM的第xx行和第yy行(1 \leq x,y \leq n)(1≤x,y≤n);
    2 x y: 交换矩阵MM的第xx列和第yy列(1 \leq x,y \leq m)(1≤x,y≤m);
    3 x y: 对矩阵MM的第xx行的每一个数加上y(1 \leq x \leq n,1 \leq y \leq 10,000)y(1≤x≤n,1≤y≤10,000);
    4 x y: 对矩阵MM的第xx列的每一个数加上y(1 \leq x \leq m,1 \leq y \leq 10,000)y(1≤x≤m,1≤y≤10,000);

官方题解：

对于交换行、交换列的操作，分别记录当前状态下每一行、每一列是原始数组的哪一行、哪一列即可。

对每一行、每一列加一个数的操作，也可以两个数组分别记录。注意当交换行、列的同时，也要交换增量数组。

输出时通过索引找到原矩阵中的值，再加上行、列的增量。

复杂度O(q+mn)*O*(*q*\+*m**n*)

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <string>
    #include <cmath>
    #include <algorithm>
    
    using namespace std ;
    
    const int maxn = 1005 ; 
    
    int t ; 
    int a[maxn],b[maxn] ;
    long long c[maxn],d[maxn] ;
    long long arr[maxn][maxn] ; 
    int n , m ,q  ; 
    
    int main()
    {
    
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d%d%d",&n,&m,&q) ; 
    		int maxx = max(n,m) ; 
    		for(int i = 1 ; i <= maxx ; i++)
    		{
    			a[i] = i ; b[i] = i ;
    			c[i] = 0 ; d[i] = 0 ; 
    		}
    
    		for(int i = 1 ; i <= n ; i++)
    		{
    			for(int j = 1 ; j <= m ; j++)
    			{
    				scanf("%I64d",&arr[i][j]) ; 
    			}
    		}
    
    		while(q--)
    		{
    			int i , j , k ; 
    			scanf("%d%d%d",&i,&j,&k);
    			if(i==1)
    			{
    				swap(a[j],a[k]) ;
    			}
    			else if(i==2)
    			{
    				swap(b[j],b[k]) ;
    			}
    			else if(i==3)
    			{
    				c[a[j]] += k ; 
    			}
    			else 
    			{
    				d[b[j]] += k ; 
    			}
    		}
    		for(int i = 1 ; i <= n ; i++)
    		{
    			for(int j = 1 ; j <= m ; j++)
    			{
    				printf("%I64d",arr[a[i]][b[j]]+c[a[i]]+d[b[j]]) ;
    				if(j!=m)printf(" ");
    			}
    			printf("\n");
    		}
    	}
    	return  0 ; 
    }