MnZn 求助模拟退火 64pts,被卡疯了
查看原帖
MnZn 求助模拟退火 64pts,被卡疯了
230580
Suzt_ilymtics楼主2021/6/12 22:24

本人的写法与题解略有不同。

题解区的写法大都是将四个方向分开判断的。

我这里的写法是最套路的在一个 for 循环里循环四个方向判断。

感觉思路上没有问题,或者说我没发现问题

求助为什么过不去 qq_emoji: kel

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<ctime>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;
const double d = 0.99996;
const double lim = 1e-15;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

int n, m, c, ans, now_;
int p[55], cnt[55], top = 1;
int col[22][22], acol[22][22];

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

bool check(int x, int y) { return x < 1 || y < 1 || x > n || y > m; }

int Dev(int sx, int sy) {
    int cnt = 0;
    for(int i = 0; i < 4; ++i) {
        int x = sx + dx[i], y = sy + dy[i]; // 找相邻的四个格子计算贡献 
        if(check(x, y) || check(sx, sy)) continue;
        if(col[sx][sy] != col[x][y]) cnt++; 
    }
    return cnt;
}

int calc(int sx, int sy, int ex, int ey) {
    int res = 0;
//    orz;
    res = res - Dev(sx, sy) - Dev(ex, ey); // 减去原来的贡献 
    swap(col[sx][sy], col[ex][ey]);
    res = res + Dev(sx, sy) + Dev(ex, ey); // 加上现在的贡献 
    return res;
}

void SA() {
//    orz;
    for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) col[i][j] = acol[i][j]; 
    double T = 50;
    while(T > lim) {
        int nowsx = rand() % n + 1;
        int nowsy = rand() % m + 1;
        int nowex = rand() % n + 1;
        int nowey = rand() % m + 1;
//        int pre = Calc();
//        swap(col[nowsx][nowsy], col[nowex][nowey]); // 先交换 
//        int now = Calc();
        int now = now_ + calc(nowsx, nowsy, nowex, nowey); // 再计算 
        int del = now - ans;
        if(del < 0) { // 更新这个解
            ans = now; now_ = now;
            for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) acol[i][j] = col[i][j];  
        } else if(exp(-del/T) > (double) rand() / RAND_MAX) {
            now_ = now; // 一定概率接受当前这个状态 
        } else {
            swap(col[nowsx][nowsy], col[nowex][nowey]); // 交换回去 
        }
        T *= d;
    }
}

void work() {
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            ans += Dev(i, j);
        }
    }
//    for(int i = 2; i <= n; ++i) 
//        for(int j = 1;j <= m; ++j) 
//            if(col[i][j] != col[i - 1][j]) ans++;
//    for(int i = 1; i <= n; ++i) 
//        for(int j = 2;j <= m; ++j) 
//            if(col[i][j] != col[i][j - 1]) ans++;
    ans /= 2;
    now_ = ans;
//    cout<<ans<<endl;
//    for(int i = 1; i <= 30; ++i) SA();
    while((double)clock() / CLOCKS_PER_SEC < 3.90) SA();//, cout<<ans<<endl;
}

int main()
{
    srand(998244353);
    n = read(), m = read(), c = read();
    for(int i = 1; i <= c; ++i) p[i] = read();
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(cnt[top] == p[top]) ++top;
            acol[i][j] = col[i][j] = top;
            ++cnt[top];
        }
    }
    work();
//    printf("%d\n", ans);
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            printf("%d ", acol[i][j]);
        }puts("");
    }
    return 0;
}
2021/6/12 22:24
加载中...