考虑搜索,发现复杂度爆炸
       贪心,正确性过低(~~实测爆炸~~)

于是,~~发现~~这题是模拟退火

这里不讲解退火的定义了,初学退火可以去平衡点

退火本身维护一个答案图像,答案的q,当前图像,当前的q
暴力根据计算图像计算q即可

关于这题我们发现如果任由其随机,可能会导致偏差太大
但如果过多修正偏差,可能导致其跃出局部最优解的能力降低
于是我加了这么一句话

if (curq - ansq >= (temp * 90)){
  for (ri i = 1; i <= n; ++i)
    for (ri j = 1; j <= m; ++j)
      cur_map[i][j] = ans_map[i][j];
  curq = ansq;
}

  

即根据当前温度及时修正偏差,温度越高,偏差容忍度越高

最后放个代码(不保证一直AC)

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ll long long
#define ri register int const double DEL = 0.00001;
const double DELTA = 0.99999; inline ll read(){
  ll x = 0; int zf = 1; char ch = ' ';
  while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
  if (ch == '-') zf = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;
} int n, m, c;
int ansq;
int ans_map[25][25];
int curq;
int cur_map[25][25];
int p[25]; inline void swp(int x1, int y1, int x2, int y2){
  int t = cur_map[x1][y1];
  cur_map[x1][y1] = cur_map[x2][y2];
  cur_map[x2][y2] = t;
} inline int getQ(int x1, int y1, int x2, int y2){
  int res = 0;
  swp(x1, y1, x2, y2);
  for (ri i = 1; i <= n; ++i)
    for (ri j = 1; j <= m; ++j){
      if (i < n)
        if (cur_map[i][j] != cur_map[i+1][j])
          ++res;
      if (j < m)
        if (cur_map[i][j] != cur_map[i][j+1])
          ++res;
    }
  swp(x1, y1, x2, y2);
  return res;
} void SA(){
  register double temp = 10000.0;
  int x1, y1, x2, y2;
  int excq;
  while (temp >= DEL){
    x1 = (rand() % n) + 1, y1 = (rand() % m) + 1, x2 = (rand() % n) + 1, y2 = (rand() % m) + 1;
    srand(rand());
    excq = getQ(x1, y1, x2, y2);
    if (excq < ansq){
      curq = ansq = excq;
      swp(x1, y1, x2, y2);
      for (ri i = 1; i <= n; ++i)
        for (ri j = 1; j <= m; ++j)
          ans_map[i][j] = cur_map[i][j];
    }
    else if (exp(-(excq - ansq) / temp) * RAND_MAX > ((rand() % 1000000) / 1000000.0)){
      curq = excq;
      swp(x1, y1, x2, y2);
    }
    else{
      if (curq - ansq >= (temp * 90)){
        for (ri i = 1; i <= n; ++i)
          for (ri j = 1; j <= m; ++j)
            cur_map[i][j] = ans_map[i][j];
      curq = ansq;       }     }
    temp *= DELTA;
  }
} int main(){
  srand(19260817);
  srand(rand()); srand(rand()); srand(rand());
  n = read(), m = read(), c = read();
  for (ri i = 1; i <= c; ++i)
    p[i] = read();
  int k1 = 1, k2 = 1;
  for (ri i = 1; i <= n; ++i)
    for (ri j = 1; j <= m; ++j){
      ans_map[i][j] = cur_map[i][j] = k1;
      ++k2;
      if (k2 > p[k1]){
        ++k1;
      k2 = 1;
      }
    }
  ansq = 0;
  for (ri i = 1; i <= n; ++i)
    for (ri j = 1; j <= m; ++j){
      if (i < n)
        if (cur_map[i][j] != cur_map[i+1][j])
      ++ansq;
    if (j < m)
      if (cur_map[i][j] != cur_map[i][j+1])
    ++ansq;
    }
  SA();
  for (ri i = 1; i <= n; ++i)
    for (ri j = 1; j <= m; ++j){
      printf("%d", ans_map[i][j]);
      if (j < m)
        printf(" ");
      else
        printf("\n");
    }
  return 0;
}

  

05-11 22:00