P14148 错觉题解

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

于是直接模拟退火！令

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

的时间跑出一组解，足以通过此题。

代码如下：

CPP

#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 错觉题解