C. Hidden Permutations

对于置换我们知道他是几个环
我们手动模拟之后发现 他的环的位置 和出现的数是一置的
只需要出现的顺序倒序 再往左移一即可
然后我们对于每一个位置询问多次 直到出现循环
最坏情况会每个位置询问2次 q=2n

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
const int M = 998244353;
const int mod = 1e9+7;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int query(int x){
    cout<<"? "<<x<<endl;
    fflush(stdout);
    int res;cin>>res;
    return res;
}
void solve(){
    int n;cin>>n;
    vector<bool>st(n+10);
    vector<int>ans(n+10);
    for(int i=1;i<=n;i++){
        if(!st[i]){
            vector<int>v;
            vector<int>stt(n+10);
            while(1) {
                int t = query(i);
                if (stt[t]) {
                    std::reverse(v.begin(), v.end());
                    for (int j = 1; j < v.size(); j++) {
                        ans[v[j]] = v[j-1];
                    }
                    ans[v[0]] = v.back();
                    break;
                }
                v.push_back(t);
                st[t]=stt[t]=1;
            }
        }
    }
    cout<<"! ";
    for(int i=1;i<=n;i++)cout<<ans[i]<<' ';cout<<endl;
}
signed main(){
    //fast
    int t;t=1;cin>>t;
    while(t--) {
        solve();
    }
    return ~~(0^_^0);
}

原文地址：http://www.cnblogs.com/ycllz/p/16814932.html