[ZSUCPC2009pre Problem F : N Queens Puzzle]【300皇后】【随机构造】【贪心调整】

【题目大意】
输入n<=300和k<=20。
要求输出n皇后的k个可行解，并且这k个可行解互不相同。
每个方案以一个1~n的排列为格式输出来。
Special Judge
【算法分析】
搜索显然不可行。
于是乱搞。
我们设斜行里冲突的对数为估价函数f(state)
先随机一个1~n的排列。
然后算出估价函数f(state)。
如果函数值不为0，那么用爬山法。
具体就是交换两个皇后，看估价函数值是否下降，下降的话就接受。
如果到达一个情况，怎么交换函数值都不减少。。。那么就是陷进局部最优解了。我们就重新随机一个排列再搞。。。
【其它】
复杂度不好算= =。。。1TLE，1Y。
TLE是因为算估价函数过于暴力。
后来利用数组把一个O(n^2)的统计变成O(1)。于是AC。
最终通过所有数据的时间用clock函数测得是343MS。
【输入数据】
10
8 2
9 3
20 5
50 5
100 10
150 10
200 10
250 10
280 20
300 20
【CODE】
#include #include #include #include using namespace std;
const int N=305;
int n,Times,done;
int save[25][N];
int a[N],v[N],Num1[N*2],Num2[N*2];
bool change;

int Cal(){
int res=0,i,j;
for (i=1;i for (j=i+1;j<=n;j++)
if (i+a[i]==j+a[j] || i-a[i]==j-a[j]) res++;
return res;
}

void Random_List(){
int i,j,cnt,x;
for (i=1;i<=n;i++) v[i]=0;
for (i=n;i>=1;i–){
x=rand()%i+1;
cnt=0;
for (j=1;j<=n;j++)
if (!v[j]){
cnt++;
if (cnt==x){
a[i]=j;
v[j]=1;
break;
}
}
}
}

void Get(){
int now,i,j,tmp;
while (1){
Random_List();
now=Cal();
for (i=1;i<=2*n;i++) Num1[i]=Num2[i]=0;
for (i=1;i<=n;i++){ Num1[a[i]+i]++; Num2[a[i]-i+n]++; }
while (now){
change=false;
for (i=1;i for (j=i+1;j<=n;j++){
tmp=now;
Num1[a[i]+i]–; Num1[a[j]+j]–;
Num2[a[i]-i+n]–; Num2[a[j]-j+n]–;
tmp-=Num1[a[i]+i]; tmp-=Num1[a[j]+j];
tmp-=Num2[a[i]-i+n]; tmp-=Num2[a[j]-j+n];
swap(a[i],a[j]);
tmp+=Num1[a[i]+i]; tmp+=Num1[a[j]+j];
tmp+=Num2[a[i]-i+n]; tmp+=Num2[a[j]-j+n];
Num1[a[i]+i]++; Num1[a[j]+j]++;
Num2[a[i]-i+n]++; Num2[a[j]-j+n]++;
if (tmp now=tmp;
change=true;
}
else{
Num1[a[i]+i]–; Num1[a[j]+j]–;
Num2[a[i]-i+n]–; Num2[a[j]-j+n]–;
swap(a[i],a[j]);
Num1[a[i]+i]++; Num1[a[j]+j]++;
Num2[a[i]-i+n]++; Num2[a[j]-j+n]++;
}
}
if (!change) break;
}
if (!now) break;
}
}

bool check(){
int i,j;
bool res;
for (i=1;i<=done;i++){
res=false;
for (j=1;j<=n;j++)
if (a[j]!=save[i][j]) res=true;
if (!res) return false;
}
return true;
}

void push(){
done++;
for (int i=1;i<=n;i++) save[done][i]=a[i];
}

void output(){
for (int i=1;i<=Times;i++){
for (int j=1;j printf("%dn",save[i][n]);
}
}

int main(){
freopen("queen.in","r",stdin);
freopen("output.txt","w",stdout);
srand(‘e’+’d’+’w’+’a’+’r’+’d’+’_’+’m’+’j’+’n’+’R’+’P’+’+’+’+’);
int Tc,i;
scanf("%d",&Tc);
for (i=0;i scanf("%d%d",&n,&Times);
done=0;
while (done Get();
if (check()) push();
if (done==Times) output();
}
}
return 0;
}