原文链接www.cnblogs.com/zhouzhendong/p/CF1172D.html

前言

明哥神仙打cf方式真潇洒。45分钟切D后就不打了？

我当场爆肝D想错方向不会做自闭了。

题解

考虑增量法构造。

考虑我们要在第一行和第一列操作一下，使得需要到达第一行和需要到达第一列的行和列完成任务。

设 \(R[x] = 1, C[y] = 1\)。

如果 \(x = y = 1\)，那么我们不需要在第一行和第一列放任何传送门。

否则我们放一对传送门，位置分别是 \((1,y), (x,1)\)，这样，我们就可以完成第一行和第一列的传送。

然后，由于第一行进入后会到达第 x 行，所以我们使 \(R'[x] = R[1]\)，同理 \(C'[y] = C[1]\) 。

接下来执行 \(n' = n - 1\) 的构造方案即可。

最终当 \(n = 1\) 时，构造完毕，结束构造。

时间复杂度 \(O(n^2)\) 。

代码

#include <bits/stdc++.h>

#define clr(x) memset(x,0,sizeof x)

#define For(i,a,b) for (int i=(a);i<=(b);i++)

#define Fod(i,b,a) for (int i=(b);i>=(a);i--)

#define fi first

#define se second

#define pb(x) push_back(x)

#define mp(x,y) make_pair(x,y)

#define outval(x) cerr<<#x" = "<<x<<endl

#define outtag(x) cerr<<"---------------"#x"---------------"<<endl

#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\

						For(_x,L,R)cerr<<a[_x]<<" ";cerr<<endl;

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef vector <int> vi;

LL read(){

	LL x=0,f=0;

	char ch=getchar();

	while (!isdigit(ch))

		f|=ch=='-',ch=getchar();

	while (isdigit(ch))

		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

	return f?-x:x;

}

const int N=1005;

int n;

int r[N],c[N];

pair <int,int> p1[N],p2[N];

int cnt=0;

int main(){

	n=read();

	For(i,1,n)

		r[i]=read();

	For(i,1,n)

		c[i]=read();

	For(i,1,n-1){

		int pr,pc;

		For(j,1,n){

			if (r[j]==i)

				pr=j;

			if (c[j]==i)

				pc=j;

		}

		if (pr==i&&pc==i)

			continue;

		cnt++;

		p1[cnt]=mp(i,pc),swap(c[i],c[pc]);

		p2[cnt]=mp(pr,i),swap(r[i],r[pr]);

	}

	printf("%d\n",cnt);

	For(i,1,cnt)

		printf("%d %d %d %d\n",p1[i].fi,p1[i].se,p2[i].fi,p2[i].se);

	return 0;

}

巴特西

Codeforces 1172D. Nauuo and Portals 构造

前言

题解

代码

最新文章

热门文章