luogu P3936 Coloring

哈哈哈哈哈哈哈我TM终于过去了！！！

模拟退火真TM邪性！！！

传送门

就是随机两个位置交换，退火即可，但是出题人丧心病狂模拟退火题造这么强的数据，充分体会到了退火的玄学，随便加点东西都会WA。

心情变化：

刚写完：你看那个人连交了12页根本就没有掌握模拟退火的精髓。

第一发27分：小东西有点意思，看我调不死你。

改了一下变成64：我今天晚上绝对能A了它。

又改成了82：嘿嘿嘿等死吧

又改成了94：这TM有什么问题吗？

随后乱改参数连交五发，最高95分：晚自习就这么没了？

又改成了33：emmm。 又改成了55：出题人nmsl

又改成了98：想把出题人头拧下来。 又交一遍成了99：md随便来个神仙让我A了这个屑题吧

A了：哈哈哈哈哈哈哈（踢翻了奶茶杯）

然而我仍然想把出题人脑袋拧下来。

以上就是我素质崩坏怀疑人生的过程。

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#define random(x) (rand()%(x)+1)
#define re register
using namespace std;
const double eps=1e-13;
int dx[5]={0,0,1,0,-1},dy[5]={0,1,0,-1,0};
int m,a[21][21],d[21][21],p[51];
int n,c,ans,b[21][21],older;
inline int get_ans(){
    re int sum=0;
    for(re int i=1; i<n; i++)
        for(re int j=1; j<m; j++){
            if(a[i][j]!=a[i][j+1]) sum++;
            if(a[i][j]!=a[i+1][j]) sum++;
        }
    for(re int i=1;i<m;i++)
        if(a[n][i]!=a[n][i+1]) sum++;
    for(re int i=1;i<n;i++)
        if(a[i][m]!=a[i+1][m]) sum++;
    return sum;
}
inline void SA1(){
    double t=1,g=0.99999;//+(double)0.000001*k;
    if (n*m<50) g=0.999; re int x1,y1,x2,y2,num;
    while (t>eps){
        x1=random(n),y1=random(m);
        x2=random(n),y2=random(m);
        if (a[x1][y1]==a[x2][y2]) continue;
        swap(a[x1][y1],a[x2][y2]);
        num=get_ans();
        if (num<older||exp((double)(older-num)/t)*RAND_MAX>(rand()*100000.0)/100000.0){
            for (re int i=1; i<=n; i++)
                for (re int j=1; j<=m; j++)
                    b[i][j]=a[i][j];
            older=num;
        }
        else swap(a[x1][y1],a[x2][y2]);
        t*=g;
        if (older<ans){
            for (re int i=1; i<=n; i++)
                for (re int j=1; j<=m; j++)
                    d[i][j]=b[i][j];
            ans=older;
        }
    }
}
int main(){
    // freopen("0a.in","r",stdin);
    srand(19260817);// srand(rand());
    // srand(rand()); //srand(rand());
    scanf("%d%d%d",&n,&m,&c);
    for (re int i=1; i<=c; i++) scanf("%d",&p[i]);
    int x=1,y=1;
    for (re int i=1; i<=c; i++){
        for (re int j=1; j<=p[i]; j++){
            a[x][y]=i; y++;
            if (y>m) x++,y=1;
        }
    }
    older=ans=get_ans();
    for (re int i=1; i<=n; i++)
        for (re int j=1; j<=m; j++)
            d[i][j]=a[i][j];
    // for (re int k=1; k<=2; k++){
        // for (re int i=1; i<=n; i++)
        // 	for (re int j=1; j<=m; j++)
        // 		a[i][j]=b[i][j]=d[i][j];
        
        // if (ans<minn){
        // 	for (re int i=1; i<=n; i++)
        // 		for (re int j=1; j<=m; j++)
        // 			d[i][j]=b[i][j];
        // 	minn=ans; now=0;
        // }
        // else now++,ans=older=minn;
        // if (now>=2) break;
        // printf("%d\n",ans);
    // }
    SA1(); SA1(); //SA1();
    for (re int i=1; i<=n; i++){
        for (re int j=1; j<=m; j++)
            printf("%d ",d[i][j]);
        puts("");
    }
    // printf("%d\n",ans);
    return 0;
}