『题解』CodeForces CF222B Cosmic Tables

仙山有茗 · 2021-12-21 21:21:40 · 题解

题目传送门

题目大意

给定一个 n \times m 的矩阵 a，进行 k 次操作，有如下三种操作：

• 交换第 x_i 列与第 y_i 列。
• 交换第 x_i 行与第 y_i 行。
• 查询 a_{x_i,y_i} 的数。

思路

真的很让人震惊，3 秒的时限，暴力 + 快读 + 不用 endl = AC。

对于每次交换操作，只需 \mathcal{O}(n) 的时间复杂度即可：

• 对于交换第 x_i 列与第 y_i列：i 从 1 遍历到 n，每次交换第 i 行第 x_i 列与第 i 行第 y_i 列，就能完成这次操作。
• 对于交换第 x_i 行与第 y_i 行：同上，只不过 i 从 1 到 m，因为有 m 列，每次交换第 x_i 行第 i 列与第 y_i 行第 i 列即可。

暴力代码很好写，就是卡常太难了（doge。

我一向不太喜欢暴力，于是又想出一种操作 \mathcal{O}(1) 时间的方法：再定义两个数组 row 和 col，分别表示交换后的行和列对应原来的哪一行哪一列。row_i 表示交换后的第 i 行对应原来的第几行，col_i 也是同理，只不过是列。

来看具体操作如何进行：

• 初始化：row_i=i，col_i=i，因为刚开始每行每列对应的就是本身嘛。
• 交换第 x_i 列与第 y_i列：直接交换 col_{x_i} 和 col_{y_i} 即可，第 x_i 列和第 y_i 列直接交换为对方。
• 交换第 x_i 行与第 y_i 行：同上，交换 row_{x_i} 和 row_{y_i}。
• 查询 a_{x_i,y_i}：输出 a_{col_{x_i},row_{y_i}} 即可。

嗯，快多了，也不用卡常了。

代码

暴力解法

#include <iostream>
using namespace std;
int n,m,k,x,y,a[1005][1005];
char c;

// 没有快读，就会看到令人满意的TLE！暴力竟然卡过去了/jk
inline int read(){
    int X=0; bool flag=1; char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+ch-'0',ch=getchar();
    if(flag) return X;
    return ~(X-1);
}

int main(){
    cin >> n >> m >> k;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            a[i][j]=read();
        }
    }
    while(k--){
        c=getchar(); // 这里 cin 也会 TLE（暴力好难卡过去/kk）
        x=read(),y=read();
        switch(c){
            case 'c': // 交换 x 列与 y 列
                for(int i=1; i<=n; i++){
                    swap(a[i][x],a[i][y]); // 直接交换第 i 行第 x 个数与第 i 行第 x 个数
                }
                break;
            case 'r': // 交换 x 行与 y 行
                for(int i=1; i<=m; i++){ // 注意是 1~m 而不是 1~n
                    swap(a[x][i],a[y][i]); // 直接交换第 x 行第 i 个数与第 y 行第 i 个数
                }
                break;
            case 'g': // 查询
                cout << a[x][y];
                puts(""); // 换行用 endl 太慢了/kk又不想在cout后面接'\n'所以...
                break;
            default: break;
        }
    }
    return 0;
}

快速解法

#include <iostream>
using namespace std;
int n,m,k,x,y,a[1005][1005];
int row[1005],col[1005]; // row 表示对应的行，col 表示对应的列
char c;

inline int read(){
    int X=0; bool flag=1; char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+ch-'0',ch=getchar();
    if(flag) return X;
    return ~(X-1);
}

int main(){
    // 前面输入什么的懒得改了/kk
    cin >> n >> m >> k;
    for(int i=1; i<=n; i++) row[i]=i; // 初始化行和列
    for(int i=1; i<=m; i++) col[i]=i;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            a[i][j]=read();
        }
    }
    while(k--){
        c=getchar();
        x=read(),y=read();
        switch(c){
            case 'c': // 交换 x 列与 y 列
                swap(col[x],col[y]);
                break;
            case 'r': // 交换 x 行与 y 行
                swap(row[x],row[y]);
                break;
            case 'g': // 查询
                cout << a[row[x]][col[y]];
                puts("");
                break;
            default: break;
        }
    }
    return 0;
}