题解 CF1172D 【Nauuo and Portals】
skydogli
2020-11-16 22:30:30
有点震撼的构造题……
如果考虑整体构造的话非常难办，所以我们考虑能否一层层处理，每次处理之后转化成一个子问题。
假设我们当前处理到第 $i$ 行第 $i$ 列，我们显然要把 $r_j=i$ 及 $c_k=i$ 的光线转过来（如果 $j=i$ 且 $k=i$ 的话不管就好了）。我们在第 $i$ 行第 $j$ 列放一个，第 $k$ 行第 $i$ 列放一个，这样的话这一行这一列的限制就满足了，而且传送门都放在第 $i$ 行与第 $i$ 列，不会对其它光线造成影响，只是原本在这一行/列的光线到了别的地方，交换一下即可。我为了方便，直接用了 $O(n^2)$ 的实现方式。
~~构造题怎么做啊/ll~~
```cpp#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define piii pair<pii,pii >
#define mp make_pair
#define x first
#define y second
#define MN 1005
int n,a[MN],b[MN];
vector<piii >ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;++i){
scanf("%d",&b[i]);
}
for(int i=1;i<n;++i){
if(a[i]==i&&b[i]==i)continue;
int ma=0,mb=0;
for(int j=i;j<=n;++j)
if(a[j]==i)ma=j;
for(int j=i;j<=n;++j)
if(b[j]==i)mb=j;
assert(ma&&mb);
assert(i!=mb||i!=ma);
ans.push_back(mp(mp(i,mb),mp(ma,i)));
swap(a[ma],a[i]);
swap(b[mb],b[i]);
}
printf("%d\n",(int)ans.size());
for(int i=0;i<ans.size();++i){
printf("%d %d %d %d\n",ans[i].x.x,ans[i].x.y,ans[i].y.x,ans[i].y.y);
}
return 0;
}
```