有2n个士兵站成两排，他们需要被重新排列，以保证每一排里没有同样高的士兵——这样我们就说，士兵们被合理地安排了位置。 每次操作可以交换两个在同一位置（但不在同一排）的士兵。你的任务是用最少的操作来确保士兵们被合理地安排了位置。 例如： 有18个士兵站成两排，箭头标明了重新安排士兵位置的正确方式（图飞了?）。 写一个这样的程序： 读入n与士兵的身高，以及他们最初所站的位置，确保以最小的交换（站在同一位置的不同排的士兵）的次数来合理地安排士兵的位置，输出操作数。
Solution
我最菜了。
听一些dalao说要染色，于是我就有了一些NAIVE的想法，把每一列的两个点之间连一条边，既然每个点的度数最多为2，那么它最后一定是一堆环，我们要么全部正着走，要么都反着走，所以我们对每个联通块都做一遍就可以了。
Code
#include<iostream>
#include<cstdio>
#define N 100002
using namespace std;
int head[N],tot,a[N],b[N],ans,pos[],n,ma;
bool vis[N];
struct edge{
int n,to,tag;
}e[N<<];
inline void add(int u,int v,int tag){
e[++tot].n=head[u];
e[tot].to=v;
e[tot].tag=tag;
head[u]=tot;
}
void dfs(int u,int fa){
vis[u]=;
for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){
int v=e[i].to;
pos[e[i].tag]++;
if(!vis[v])dfs(v,u);
break;
}
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;++i)scanf("%d",&a[i]),ma=max(ma,a[i]);
for(int i=;i<=n;++i)scanf("%d",&b[i]),add(a[i],b[i],),add(b[i],a[i],),ma=max(ma,b[i]);
for(int i=;i<=ma;++i)if(!vis[i]){
pos[]=pos[]=;
dfs(i,);
ans+=min(pos[],pos[]); ;
}
cout<<ans;
return ;
}
获得了40pts
emmm
有一个问题就是说有些数会出现一次，因为每个点度数最多为2，不可能是基环树，只能是一条链，那么GG了。
我们把每列看成一个点，如果两列必须一样连0边，否则连1边，染色即可。
真·Code
#include<iostream>
#include<cstdio>
#define N 100002
using namespace std;
int head[N],tot,x,ans,pos[],n,pre[N],co[N];
bool vis[N];
struct edge{
int n,to,tag;
}e[N<<];
inline void add(int u,int v,int tag){
e[++tot].n=head[u];
e[tot].to=v;
e[tot].tag=tag;
head[u]=tot;
}
void dfs(int u,int c){
vis[u]=;pos[c]++;
for(int i=head[u];i;i=e[i].n)if(!vis[e[i].to]){
int v=e[i].to;
dfs(v,c^e[i].tag);
}
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;++i){
scanf("%d",&x);
if(pre[x]){
add(i,pre[x],);
add(pre[x],i,);
}
else pre[x]=i;
}
for(int i=;i<=n;++i){
scanf("%d",&x);
if(pre[x]){
add(i,pre[x],co[x]);
add(pre[x],i,co[x]);
}
else pre[x]=i,co[x]=;
}
for(int i=;i<=n;++i)if(!vis[i]){
pos[]=pos[]=;
dfs(i,);
ans+=min(pos[],pos[]);
}
cout<<ans;
return ;
}