美妙的模拟退火

· · 题解

骗分还得是模拟退火

思路

了解了模拟退火算法后，本题几乎成为了一道板子题，但是还有一些细节需要去解决一下。

模拟退火算法本来是用来求最值的，所以对于本题来说其中退火的环节确实有点多余，所以我们为了本人更好地偷懒解法的正确性，我们要舍去多余的退火。

舍去了退火之后会发现，如何解决是否交换的问题呢？其实只需要全部交换就可以了，因为异或这种运算没什么太大的规律。

之后是我们总体的思路，首先预处理一下要用的 lg 数组，然后对于每一个 n 准备好的原数组和它的前 m 个异或和，还有要比较的数。之后跑模拟退火直到出结果或者无解就好了。

更多的代码细节还是直接看代码吧。

Code

#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
    long long s=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') {
        s=(s<<3)+(s<<1)+(ch^48);
        ch=getchar();
    }
    return s;
}
inline void write(long long x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int flag=0,lg[1000005];
int a[1000005],n,m,t,pos=1,sum;
void SA(){
    for(int i=1;i<=10000;i++){
        int l=rand()%m+1,r=m+rand()%(n-m)+1;
        sum^=a[l];
        sum^=a[r];
        swap(a[l],a[r]);
        if(sum==pos){
            flag=1;
            return ;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    srand(time(0));
    cin>>t;
    for(int i=1;i<=1000000;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    while(t--){
        cin>>n>>m;
        if(n==m){
            for(int i=1;i<=n;i++) a[i]=i;
            flag=sum=0;
            for(int i=1;i<=m;i++) sum^=i;
            pos=1;
            for(int i=1;i<=lg[n];i++) pos*=2;
            pos--;
            if(sum==pos) {
                for(int i=1;i<=n;i++) cout<<i<<" ";
                cout<<"\n";
                continue;
            }
            else {
                cout<<"-1\n";
                continue;
            }
        }
        for(int i=1;i<=n;i++) a[i]=i;
        flag=sum=0;
        for(int i=1;i<=m;i++) sum^=i;
        pos=1;
        for(int i=1;i<=lg[n];i++) pos*=2;
        pos--;
        for(int i=1;i<=90;i++){
            SA();
            if(flag){
                for(int j=1;j<=m;j++){
                    cout<<a[j]<<" ";
                }
                cout<<"\n";
                break;
            }
        }
        if(!flag){
            cout<<"-1\n";
        }           
    }
    return 0;
}

温馨提示

本代码不一定可以一遍过，如果答案错误的话，多提交几遍就可以了。