CF1773A Amazing Trick 题解

· · 题解

前言

感谢 HMZ 大佬在我 一直调不出 Test #5 时给了一些点拨，在经过 25 分钟的的调测后通过了本题。也算警示后人吧

解法

本题可以使用随机化做法。

记 m_i(1\le i\le n) 为 i 在排列 a 中的位置，那么容易观察到题目的要求 a_{p_{q_i}}=i 等价于 p_{q_i}=m_i。

又因为排列 p 需要满足 p_i\ne i，根据上面的转化，就可以得到 q_i\ne m_i。

这样，原问题就转化为了构造一个排列 q，使得 q_i\ne i 且 q_i\ne m_i，然后再根据 q 构造出 p 满足 p_{q_i}=m_i。

实现

先用一个 std::vector 顺序存储 1,2,\ldots,n，然后对于每个 i，从 vector 中随机选取一个数 k，如果 k_i\ne i 且 k_i\ne m_i，那么将 q_i 赋值为 k。如果找很多次还找不到满足条件的 k，那么就退出循环，重新回到开始再从头构造一遍 q。

如果找了非常多遍都没有合法的 q 序列，就可以判断为无解。可以证明，在构造次数足够多时，出错的概率可以忽略不计。

找到 q 序列后，将所有的 p_{q_{i}} 赋值为 m_i 即可。

放代码：

#include<bits/stdc++.h>
using namespace std;
mt19937 rng(time(0));
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin>>t;
  while(t--){
    int n; cin>>n;
    vector<int> a(n),m(n),q(n),p(n);
    for(auto &i:a)cin>>i,i--;
    for(int i=0;i<n;i++)
      m[a[i]]=i;
    bool w=false;
    for(int _=0;_<80;_++){ // 找 80 遍（这个数足够大）
      bool f=true;
      vector<int> v;
      iota(q.begin(),q.end(),0),v=q;
      for(int i=0;i<n;i++){
        for(int _=0;_<10;_++){
          int k=rng()%v.size();
          if(v[k]==i||v[k]==m[i])continue;
          else{q[i]=v[k],v.erase(v.begin()+k); break;}
          // 判断 k 的合法性
        }
        if(q[i]==i||q[i]==m[i]){f=false; break;}
      }
      if(f){w=true; break;} // 找到了
    }
    if(w){
      cout<<"Possible\n";
      for(int i=0;i<n;i++)
        p[q[i]]=m[i]; // 根据排列 q 构造排列 p
      for(int i:p)cout<<i+1<<' ';
      cout<<'\n';
      for(int i:q)cout<<i+1<<' ';
      cout<<'\n';
    }
    else cout<<"Impossible\n"; // 无解
  }
  return 0;
}