给定一个长 ,值域 的数组 ,定义 的排列(任意打乱元素顺序后的数组) 的价值为最小的操作次数使得 ,一次操作可以:
- 选定两个 ,交换 和 ;
F1:给定 ,构造价值最大的 ;
F2:给定 和 ,判断 的价值是否最大;
。
F1 的做法很简单,先考虑 各不相同的情况。那么对于一个 ,设 个点的有向图 构造方法如下:
- 从 向 在 中的位置 连一条有向边;
那么 的价值即为 。
考虑 会相同的情况,那么无非就是 和 之间的 条有向边可以任意确定,只要保证 中的每个点都有出边, 中的每个点都有入边即可。
注意到若 中的两个点 在同一个环中且满足 ,则可以通过交换 的出边来把这个环分裂成两个环,这显然不花费操作次数。所以价值最大的 一定满足 相同的 不在同一个环内,那么直接乱构造就行了。
代码如下:
int n,m,a[S];
vector<int> vec[S],cir[S];
int ans[S];
inline void slove()
{
read(n);
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=n;i++) vec[i].clear(),cir[i].clear();
for(int i=1;i<=n;i++) vec[a[i]].pb(i);
m=0;
for(int i=1;i<=n;i++)
{
int id=0;
for(int v:vec[i]) cir[++id].pb(v);
m=max(m,id);
}
for(int i=1;i<=m;i++)
{
int ct=cir[i].size();
for(int j=0;j<ct;j++)
{
int u=cir[i][j],v=cir[i][(j+1)%ct];
ans[u]=a[v];
}
}
for(int i=1;i<=n;i++) write(ans[i],' ');
write('\n');
}
F2 其实也挺简单的,注意到合法的 对应 中环的个数一定等于 中出现次数最多的数的出现次数,那么把出现次数最多的数删掉,如果剩下的数能构成环,则 不合法。
判环直接弄个虚点 ,建 ,,然后拓扑判环集可。
代码如下:
int n,a[S],b[S];
vector<int> va[S],vb[S];
int cnt[S];
vector<int> g[S];
int ind[S];
queue<int> q;
inline void slove()
{
read(n);
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=n;i++) read(b[i]);
for(int i=1;i<=n;i++) va[i].clear(),vb[i].clear();
for(int i=1;i<=n;i++) va[a[i]].pb(i),vb[b[i]].pb(i);
for(int i=1;i<=n;i++) cnt[i]=0;
int mx=0;
for(int i=1;i<=n;i++) mx=max(mx,++cnt[a[i]]);
for(int i=1;i<=n;i++)
{
if(cnt[i]==mx)
{
va[i].clear(),vb[i].clear();
break;
}
}
for(int i=1;i<=n+n;i++) g[i].clear(),ind[i]=0;
int cnt=n;
for(int i=1;i<=n;i++)
{
cnt++;
for(int id:vb[i]) g[id].pb(cnt),ind[cnt]++;
for(int id:va[i]) g[cnt].pb(id),ind[id]++;
}
while(!q.empty()) q.pop();
for(int i=1;i<=n+n;i++) if(ind[i]==0) q.push(i);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int v:g[u]) if(--ind[v]==0) q.push(v);
}
for(int i=1;i<=n+n;i++) if(ind[i]!=0) return puts("WA"),void();
puts("AC");
}