ABC347G题解

我不会，但是我会退火！

第一眼，\(n\le 20\)。

退火，启动！

大致思路就是随机选一个初始为 0 的数置为 \(1\sim 5\) 中的某个数，显然图中没有 0 一定不比有 0 劣（把所有 0 改成同一个数一定不劣）。

然后把单次计算的复杂度从 \(O(n^2)\) 变成 \(O(1)\)：更新有变化位置的值就行了。

瞎调调参数就有概率能过了，吃了 8 发。

自己赛时的参数是 \(k=0.99993,T_{start}=10^{10},T_{end}=10^{-15}\)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

using D = long double;

const int N = 25;
int a[N][N], b[N][N], ans = 1e9;
pair<int, int> pos[N * N];
int h, n;

mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());

inline int p2(int x) {return x * x;}

int calc(int r, int x, int y, int v)
{
    for(int i = max(x - 1, 1); i <= min(x, n); i ++)
    for(int j = max(y - 1, 1); j <= min(y, n - 1); j ++)
        r -= p2(a[i][j] - a[i][j + 1]);
    for(int i = max(x - 1, 1); i <= min(x, n - 1); i ++)
    for(int j = max(y - 1, 1); j <= min(y, n); j ++)
        r -= p2(a[i][j] - a[i + 1][j]);
    a[x][y] = v;
    for(int i = max(x - 1, 1); i <= min(x, n); i ++)
    for(int j = max(y - 1, 1); j <= min(y, n - 1); j ++)
        r += p2(a[i][j] - a[i][j + 1]);
    for(int i = max(x - 1, 1); i <= min(x, n - 1); i ++)
    for(int j = max(y - 1, 1); j <= min(y, n); j ++)
        r += p2(a[i][j] - a[i + 1][j]);
    return r;
}

int init()
{
    int tans = 0;
    for(int i = 1; i <= n; i ++)
    for(int j = 1; j < n; j ++)
        tans += p2(a[i][j] - a[i][j + 1]);
    for(int i = 1; i < n; i ++)
    for(int j = 1; j <= n; j ++)
        tans += p2(a[i][j] - a[i + 1][j]);
    return tans;
}

D rnd01() {return rnd() * 1.L / UINT_MAX;}

void SA()
{
    int res = ans; memcpy(a, b, sizeof a);
    D T = 1e10, ed = 1e-15, k = 0.99993;
    while(T > ed)
    {
        int u = rnd() % h + 1;
        int v = rnd() % 5 + 1;
        int v0 = a[pos[u].first][pos[u].second];
        int now = calc(res, pos[u].first, pos[u].second, v);
        if(now <= ans)
        {
            ans = res = now;
            memcpy(b, a, sizeof a);
        }
        else if(rnd01() < exp((res - now) / T)) res = now;
        else a[pos[u].first][pos[u].second] = v0;
        T *= k;
    }
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= n; j ++)
        {
            cin >> b[i][j];
            if(b[i][j] == 0) pos[++h] = {i, j}, b[i][j] = 1;
        }
    }
    memcpy(a, b, sizeof a);
    ans = init();
    // cerr << calc() << endl;
    if(h) while(clock() * 1000.0 / CLOCKS_PER_SEC < 1780) SA();
    cerr << ans;
    for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= n; j ++)    
        cout << b[i][j] << " \n"[j == n];

    return 0;
}