P14148 错觉题解

TimSwn090306 · 2025-10-05 20:45:27 · 题解

跑个暴力发现有解情况下，解的数量是比较多的。

于是直接模拟退火！令 S=\bigoplus\limits_{i=1}^n (p_i+k\times i)，定义一个局面 \{p_n\} 的函数值为 E(p)=popcount(S)。初始温度、结束温度、退火系数随便设，我取的是 T_{st}=10^4,T_{ed}=10^{-9},down=0.9997。比较好的初始解是 p_i=n-i+1。

对于有解的情况，上述参数的模拟退火可以在本题数据中以不到 70ms 的时间跑出一组解，足以通过此题。

代码如下：

#include <bits/stdc++.h>
#define fin(str) freopen(str,"r",stdin)
#define fout(str) freopen(str,"w",stdout)
#define ll long long
using namespace std;

bool MEM_beg;

const int maxn=1e6+5;
const double down=0.9997;
const double eps=1e-9;

int n,k,res,p[maxn];

inline int val(int x){
    int cur=0;
    for (int i=23;~i;i--){
        if ((x>>i)&1) cur++;
    }
    return cur;
}
inline void SA(){
    double T=10000;
    while (T>eps && res){
        int x=rand()%n+1,y=rand()%n+1;
        while (n>1 && x==y) y=rand()%n+1;
        int res2=res;
        res2^=((p[x]+k*x)^(p[y]+k*y));
        res2^=((p[y]+k*x)^(p[x]+k*y));
        if (val(res2)<=val(res) || (exp(-T/(val(res2)-val(res)))*RAND_MAX>rand())){
            swap(p[x],p[y]);
            swap(res,res2);
        }
        T*=down;
    }
}

bool MEM_end;
int main(){
    srand(time(0));

    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++) p[i]=n-i+1;
    for (int i=1;i<=n;i++) res^=(p[i]+k*i);

    clock_t st=clock();
    while (res && (double)(clock()-st)/CLOCKS_PER_SEC<=0.08) SA();

    if (!res) for (int i=1;i<=n;i++) printf("%d ",p[i]);
    else printf("-1\n");

    cerr<<"\nMemory : "<<1.0*abs(&MEM_end-&MEM_beg)/1048576<<" MB\n";
    return 0;
}

比较有趣的是，令 E(p)=S，仍能以不到 400ms 的时间跑出一组解。

P14148 错觉 题解

P14148 错觉题解