CF1365F Swaps Again(思维)

观察到如果两个位置是对称的,那么他们永远是对称的,这种输出yes和no并且没啥其他性质的,看和猜结论比较有用

因此只要把对称位置的变成一组,比较两个数组的所有组是否相等,如果相等就可以

具体证明可以看官方题解

#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>
#include<cstring>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
const int N=3e5+10;
const int inf=0x3f3f3f3f;
int a[N],b[N];
pair<int,int> x[N];
pair<int,int> y[N];
bool cmp(pair<int,int> a,pair<int,int> b){
    if(a.first==b.first){
        return a.second<b.second;
    }
    return a.first<b.first;
}
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int i;
        for(i=1;i<=n;i++)
            cin>>a[i];
        for(i=1;i<=n;i++)
            cin>>b[i];
        if(n%2&&a[n/2+1]!=b[n/2+1]){
                cout<<"NO"<<endl;
                continue;
        }
        else{
            for(i=1;i<=n/2;i++){
                x[i].first=a[i];
                x[i].second=a[n-i+1];
                if(x[i].first>x[i].second)
                    swap(x[i].first,x[i].second);
                y[i].first=b[i];
                y[i].second=b[n-i+1];
                if(y[i].first>y[i].second)
                    swap(y[i].first,y[i].second);
            }
            sort(x+1,x+1+n/2,cmp);
            sort(y+1,y+1+n/2,cmp);
            int sign=0;
            for(i=1;i<=n/2;i++){
                if(x[i].first==y[i].first&&x[i].second==y[i].second)
                    continue;
                sign=1;
                break;
            }
            if(sign==1){
                cout<<"NO"<<endl;
            }
            else{
                cout<<"YES"<<endl;
            }
        }
    }
}
View Code
原文地址:https://www.cnblogs.com/ctyakwf/p/13279368.html