题解 CF706E 【Working routine】

Piwry · 2020-07-27 20:58:31 · 题解

神奇的链表题

想到链表就不难了

解析

题目要求我们交换两个矩阵

可以想到，交换后这两个矩阵内部元素的相对关系是不变的；变化的只有和矩阵边缘相邻的矩阵外元素

于是就可以想到维护一个十字链表，储存一个元素右方和下方邻接的元素地址。对于每次询问，只要遍历被交换的矩阵的边邻接的元素，交换它们的指针就可以了。实现细节可以看代码

每次询问的复杂度是 O(2(n+m))，总的复杂度是 O(2(n+m)q)

CODE

#include <cstdio>
#include <iostream>
using std::swap;

const int MAXN =1000+50;

struct qwq{
    int right, down;
    int val;
}list[MAXN*MAXN];

/*获取矩阵第 x 行第 y 列的元素*/
/*注意有下标为 0 的 index*/
inline int get(int x, int y){
    /*可以知道第一行是不会被修改的*/
    int nw =1;
    for(int i =0; i < y; ++i)
        ++nw;
    for(int i =0; i < x; ++i)
        nw =list[nw].down;
    return nw;
}

inline int read(){
    int x =0; char c =getchar();
    while(c < '0' || c > '9') c =getchar();
    while(c >= '0' && c <= '9') x = (x<<3) + (x<<1) + (48^c), c =getchar();
    return x;
}

int main(){
    int n =read(), m =read(), q =read();
    for(int i =1; i <= (n+1)*(m+1); ++i){
        if(i > m+1 && (i-1)%(m+1) != 0)
            list[i].val =read();
        if(i%(m+1) != 0)
            list[i].right =i+1;
        if(i <= n*(m+1))
            list[i].down =i+m+1;
    }
    /*保证交换的矩阵不共边不重合*/
    for(int k =0; k < q; ++k){
        int x1 =read(), y1 =read(), x2 =read(), y2 =read(), h =read(), w =read();
        /*h 行 w 列*/
        int ph1 =get(x1-1, y1-1), ph2 =get(x2-1, y2-1);
        int pw1 =list[ph1].right, pw2 =list[ph2].right;
        ph1 =list[ph1].down, ph2 =list[ph2].down;
        int ph3 =get(x1, y1+(w-1)), ph4 =get(x2, y2+(w-1));
        int pw3 =get(x1+(h-1), y1), pw4 =get(x2+(h-1), y2);
        for(int i =0; i < h; ++i){
            swap(list[ph1].right, list[ph2].right);
            ph1 =list[ph1].down, ph2 =list[ph2].down;
            swap(list[ph3].right, list[ph4].right);
            ph3 =list[ph3].down, ph4 =list[ph4].down;
        }
        for(int i =0; i < w; ++i){
            swap(list[pw1].down, list[pw2].down);
            pw1 =list[pw1].right, pw2 =list[pw2].right;
            swap(list[pw3].down, list[pw4].down);
            pw3 =list[pw3].right, pw4 =list[pw4].right;
        }
    }
    int p =1;
    for(int i =0; i < n; ++i){
        p =list[p].down;
        for(int j =0, nw =list[p].right; j < m; ++j){
            printf("%d ", list[nw].val);
            nw =list[nw].right;
        }
        putchar('\n');
    }
}