题目描述
Link
Solution
真是goushi！
这道题让我看出了我是有多非。。。。
提交了整整6页啊，整整6页！（不过我开小号提交不怕）
其实这道题本身没什么难的，就是随机交换两数，然后在进行判断进行退火的过程就好了。
为那些处在水深火热的提交中发几个我AC时的参数（估计没啥用）：
$T:1.0$
$\Delta T:0.99998$
随机数种子：$19* * * *17$这玩意我不说你们也知道
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
| #pragma GCC optimize(3)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#define delta 0.99998
#define MAXN 100010
#define random(a, b) ((rand() % (b - a + 1)) + (a))
int n, m, c, p[MAXN], G[100][100], tot, nowG[100][100], _p, chG[100][100];
template <typename Tp>
void swap(Tp &a, Tp &b) {
Tp t = a;
a = b;
b = t;
}
int Q() {
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (nowG[i][j] != nowG[i][j - 1]) ans++;
if (nowG[i][j] != nowG[i - 1][j]) ans++;
if (nowG[i][j] != nowG[i][j + 1]) ans++;
if (nowG[i][j] != nowG[i + 1][j]) ans++;
}
}
return ans;
}
void copy(bool flag) {
if (flag) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
chG[i][j] = nowG[i][j];
}
}
return;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
G[i][j] = chG[i][j];
}
}
return;
}
void SA() {
long double t = 1.0;
_p = tot;
while (t > 1e-14) {
int x1 = random(1, n);
int y1 = random(1, m);
int x2 = random(1, n);
int y2 = random(1, m);
if (nowG[x1][y1] == nowG[x2][y2]) continue;
std::swap(nowG[x1][y1], nowG[x2][y2]);
int now = Q();
int dt = now - _p;
if (dt < 0 || (exp(-dt * 1.0 / t) * RAND_MAX > ((rand() % 1000000) / 1000000.0))) {
copy(1);
_p = now;
}
else {
std::swap(nowG[x1][y1], nowG[x2][y2]);
}
if (_p <= tot) {
tot = _p;
copy(0);
}
t *= delta;
}
}
int main() {
srand(19260817);
scanf("%d%d%d", &n, &m, &c);
for (int i = 1; i <= c; i++) {
scanf("%d", &p[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int col = rand() % c + 1;
while (!p[col]) col = rand() % c + 1;
G[i][j] = col;
nowG[i][j] = col;
p[col]--;
}
}
tot = Q();
_p = tot;
SA();
SA();
SA();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
printf("%d ", G[i][j]);
}
puts("");
}
return 0;
}
|
