P7368题解
这道题好像没有模拟退火题解，来水一个
思路是对于每个陨石，一定会轰炸其所在的一行或一列。
显而易见，如果行列都只存在这一个陨石，则同时轰炸行和列是不划算的。
所以我们得出了模拟退火的对象：一个长为
估价函数我使用的就是需要轰炸的总数（要记住相同的行和列只需要轰炸一次，所以要查重以避免总数算大）。
转移则是随机选择一个陨石并转换是轰炸所在的行还是轰炸所在的列。
调参有亿点点难调 我是不会告诉你我交了5页才调出来的
代码如下：
#include <cstdio>
#include <ctime>
#include <cmath>
#include <cstdlib>
#define N 510
#define K (N*N)
int n,k;
int x[K],y[K];
struct solu
{
//true:炸列
//false:炸行
bool vis[K];
}now,best,tmp;
//分别代表 best-cost now-cost temp-cost
int bc,nc,tc;
bool ver[N],hor[N];
int cost(solu &s)
{
//暴力模拟，存储每一行每一列是否需要轰炸
//最后统计所有需要炸的行列并求和
for(int i=0;i<n;i++)
ver[i]=hor[i]=false;
for(int i=0;i<k;i++)
if(s.vis[i]) ver[x[i]]=true;
else hor[y[i]]=true;
int ans=0;
for(int i=0;i<n;i++)
{
if(ver[i]) ans++;
if(hor[i]) ans++;
}
return ans;
}
solu turn(solu b)
{
//这里是在Windows上调大数据必须的
//因为RAND_MAX只有32767
//但是k最大能到250000
//所以不能直接取模，只能用这个Hack
int i=rand()/(double)RAND_MAX*k;
b.vis[i]=!b.vis[i];
return b;
}
void read()
{
scanf("%d%d",&n,&k);
for(int i=0;i<k;i++)
{
int a,b;
scanf("%d%d",&a,&b);
//转化成以0为开始的索引
x[i]=a-1;
y[i]=b-1;
}
}
//注下：由于线性同余法在一些计算机上的局限性
//使得最后一位始终为01交替
//所以此处使用rand()>(RAND_MAX/2)得到更高质量的随机数
void same(solu &a)
{
//随机设置为同一个值，初始化best时使用
bool val=rand()>(RAND_MAX/2);
for(int i=0;i<k;i++)
a.vis[i]=(val);
}
void rng(solu &a)
{
//全部设置为随机值，初始化now时使用
for(int i=0;i<k;i++)
a.vis[i]=(rand()>(RAND_MAX/2));
}
//Boltzmann常数
#define kb 1.38e-23
inline bool accept(int diff,double T)
{
return diff>=0||exp(diff/T/kb)>(rand()/(double)RAND_MAX);
}
void sa()
{
//每次调用srand保证不一样的随机种子
//玄学种子feel dead
srand(0xfee1dead*rand());
double T=1e7;
const double eps=1e-10;
const double cool=0.995;
rng(now);
nc=cost(now);
while(T>eps)
{
tc=cost(tmp=turn(now));
if(accept(nc-tc,T))
{
nc=tc;
now=tmp;
}
if(nc<bc)
{
bc=nc;
best=now;
}
T*=cool;
}
}
//反复执行直到0.8秒
const int LIMIT=CLOCKS_PER_SEC*0.8;
int main()
{
//srand(rand())保证高质量种子
//dead beef有规律性可能被卡
srand(0xdeadbeef);
srand(rand());
read();
same(best);
bc=cost(best);
while(clock()<LIMIT)
sa();
printf("%d",bc);
}注：因为 玄学 评测机波动，完全一样的代码会在
100分 82分