CF1682B 题解

听取MLE声一片 · 2022-05-26 23:01:49 · 题解

update：修改逻辑问题。

直接送我 -83 的一道题。

首先不难看出所有不在原位置的所有数都要进行交换，还有 & 满足结合律，所以所有不在位置上的数 & 起来即可。

我们来证明一下一定有解，排列一定有一个 0，将它和所有不在位置的数交换，& 显然结果都为 0，就能证明出一定有解。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int N=2e5+10;
int n,a[N];
int main()
{
    int t=read();
    while(t--){
        n=read();
        vector<int>b;
        for(int i=0;i<n;i++){
            a[i]=read();
            if(a[i]!=i)
                b.push_back(i);
        }
        //cout<<b.size()<<' ';
        int ans=b[0];
        for(int i=1;i<b.size();i++)
            ans&=b[i];
        cout<<ans<<endl;
    }
    return 0;
}