M_sea

CF1172D Nauuo and Portals
CodeforcesLuogu分析思想很妙的构造题。考虑把一个 $n\times n$ 的问题削成一个 $(n-1...
扫描右侧二维码阅读全文
01
2019/08

CF1172D Nauuo and Portals

Codeforces

Luogu

分析

思想很妙的构造题。

考虑把一个 $n\times n$ 的问题削成一个 $(n-1)\times (n-1)$ 的问题。

那么我们只要满足掉第一行和第一列即可。

如果已经满足了,什么都不要做;如果没有满足,在对应位置放一对传送门让第一行、第一列满足即可。

如果懒的话时间复杂度 $O(n^2)$ ,如果不懒的话时间复杂度 $O(n)$ 。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000+10;

int n;
int r[N],pr[N];
int c[N],pc[N];
struct data { int a,b,c,d; };
vector<data> ans;

int main() {
    n=read();
    for (re int i=1;i<=n;++i) r[i]=read();
    for (re int i=1;i<=n;++i) c[i]=read();
    for (re int i=1;i<n;++i) {
        int pr,pc;
        for (re int j=1;j<=n;++j) {
            if (r[j]==i) pr=j;
            if (c[j]==i) pc=j;
        }
        if (pr==i&&pc==i) continue;
        ans.push_back((data){i,pc,pr,i});
        swap(r[i],r[pr]),swap(c[i],c[pc]);
    }
    printf("%d\n",ans.size());
    for (re auto i:ans) printf("%d %d %d %d\n",i.a,i.b,i.c,i.d);
    return 0;
}
最后修改:2019 年 08 月 01 日 10 : 05 PM

发表评论