P7812 [JRKSJ R2] - Dark Forest 题解
题目地址：P7812
题目难度：省选/NOI-
题目类型：提交答案 Special Judge
本题为提交答案题。
给你一个长为 的序列 ，定义 的排列 的权值为
你可以理解为这个排列是一个环，即 。
请构造一个权值尽量大的 的排列。
输入格式：
第一行一个整数 。
第二行 个整数表示序列 。
输出格式：
一行 个整数表示排列。
数据范围：
对于 的数据，。
评分方式：
本题使用 Special Judge，每个测试点都有 个参数 。如果你的输出的权值
，则该测试点您至少会获得
分。
特别的，如果您的输出不是一个 的排列，您会在该测试点获得 分。
评分参数已经放至附件。
附件下载：
- 评分参数
- 输入数据
什么？提交答案题？直接打表！
首先我们需要明确如何才能构造出一个符合题意的排列，暴力枚举的复杂度是
的，显然是不可取的做法。因此我们考虑随机化做法。
测试点 1-2
提到随机化，我们有模拟退火。先随机一个
的排列，再任意交换若干元素并与先前的序列权值进行比较，若更优则直接采纳，否则就依据
准则概率接受，其余情况则恢复原状。
在本地跑没有时限，可以把参数调精一点。
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
| #include <bits/stdc++.h>
#define N 1010
#define PRINT_TABLE
using namespace std;
typedef long long ll;
int n;
ll a[N], p[N], q[N];
random_device rd;
ll ans = 0;
double rand(double l, double r) {
return (double) rd() / random_device::max() * (r - l) + l;
}
int rand(int l, int r) {
return (int) (rd() % (r - l + 1)) + l;
}
ll calc() {
ll sum = p[1] * a[p[n]] * a[p[1]] * a[p[2]];
for (int i = 2; i < n; i++) sum += p[i] * a[p[i - 1]] * a[p[i]] * a[p[i + 1]];
sum += p[n] * a[p[n - 1]] * a[p[n]] * a[p[1]];
return sum;
}
void SA() {
double T = 1e10;
ans = max(ans, calc());
while (T > 1e-17) {
int a = rand(1, n), b = rand(1, n);
swap(p[a], p[b]);
ll now = calc();
long double delta = now - ans;
if (delta > 0) {
memcpy(q, p, sizeof p);
ans = now;
} else if (exp(delta / T) <= (double) rd() / random_device::max()) swap(p[a], p[b]);
T *= 0.99996;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) p[i] = i;
shuffle(p + 1, p + 1 + n, mt19937(rd()));
SA();
clog << ans << endl;
#ifdef PRINT_TABLE
cout << '{';
for (int i = 1; i < n; i++) cout << q[i] << ", ";
cout << q[n] << "},\n";
#else
for (int i = 1; i <= n; i++) cout << q[i] << ' ';
#endif
return 0;
}
|
一般来说一秒之内可以出答案。
测试点 3
测试点 3
的数据很有意思，它是一个单调递增的排列。模拟退火跑了很久，得出的排列有两头大、中间小的特征。于是大胆构造一个特解——从左至右奇数递减、从右至左偶数递减。
测试点 4-10
模拟退火调了半天参数就是过不去……同机房的大佬好像用加强版的模拟退火跑了几天才跑过？这里推荐一个叫“遗传算法”的解决方案。
遗传算法能通过模拟生物繁衍、自然选择等自然现象来实现求解全局最优解的功能。具体是让当前的优解进行变换，期望能得到一个更优的解。
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
| #include <bits/stdc++.h>
#define N 1010
#define PRINT_TABLE
#define LIMIT 141473199965824ll
#pragma optimize(3)
using namespace std;
typedef long long ll;
int n;
ll ans = 0, submax = 0;
random_device rd;
ll a[N], p[N], q[N], id[N];
ll calc(const ll arr[] = p) {
ll sum = arr[1] * a[arr[n]] * a[arr[1]] * a[arr[2]];
for (int i = 2; i < n; i++) sum += arr[i] * a[arr[i - 1]] * a[arr[i]] * a[arr[i + 1]];
sum += arr[n] * a[arr[n - 1]] * a[arr[n]] * a[arr[1]];
return sum;
}
ll d(int pos1, int pos2) {
ll sum = 0;
sum -= p[pos1] * a[p[pos1 - 1]] * a[p[pos1]] * a[p[pos1 + 1]] + p[pos1 + 1] * a[p[pos1]] * a[p[pos1 + 1]] * a[p[pos1 + 2]] + p[pos1 - 1] * a[p[pos1 - 2]] * a[p[pos1 - 1]] * a[p[pos1]];
sum -= p[pos2] * a[p[pos2 - 1]] * a[p[pos2]] * a[p[pos2 + 1]] + p[pos2 + 1] * a[p[pos2]] * a[p[pos2 + 1]] * a[p[pos2 + 2]] + p[pos2 - 1] * a[p[pos2 - 2]] * a[p[pos2 - 1]] * a[p[pos2]];
swap(p[pos1], p[pos2]);
sum += p[pos1] * a[p[pos1 - 1]] * a[p[pos1]] * a[p[pos1 + 1]] + p[pos1 + 1] * a[p[pos1]] * a[p[pos1 + 1]] * a[p[pos1 + 2]] + p[pos1 - 1] * a[p[pos1 - 2]] * a[p[pos1 - 1]] * a[p[pos1]];
sum += p[pos2] * a[p[pos2 - 1]] * a[p[pos2]] * a[p[pos2 + 1]] + p[pos2 + 1] * a[p[pos2]] * a[p[pos2 + 1]] * a[p[pos2 + 2]] + p[pos2 - 1] * a[p[pos2 - 2]] * a[p[pos2 - 1]] * a[p[pos2]];
return sum;
}
int rand(int l, int r) {
return (int) (rd() % (r - l + 1)) + l;
}
void GA() {
while (ans < LIMIT) {
for (int i = 1; i <= 20; i++) {
int a = rand(1, n), b = rand(1, n);
swap(p[a], p[b]);
}
submax = calc();
shuffle(id + 1, id + 1 + n, mt19937(rd()));
bool flag;
do {
flag = false;
#pragma unroll 20
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
ll cur;
int pos1 = id[i], pos2 = id[j];
if (abs(pos2 - pos1) <= 5 || abs(pos2 - pos1) >= n - 5) {
swap(p[pos1], p[pos2]);
cur = calc();
} else {
cur = submax + d(pos1, pos2);
}
if (cur > ans) {
ans = submax = cur;
memcpy(q, p, sizeof p);
if (ans > (ll) (LIMIT * 0.999)) cerr << ans << endl;
flag = true;
if (ans >= LIMIT) return;
} else if (cur > submax) {
submax = cur;
flag = true;
} else swap(p[pos1], p[pos2]);
}
}
} while (flag);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
freopen("9.in", "r", stdin);
freopen("9.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) p[i] = i, id[i] = i;
GA();
clog << "Final Answer: " << calc(q) << " Overloaded: " << calc(q) - LIMIT << endl;
#ifdef PRINT_TABLE
cout << '{';
for (int i = 1; i < n; i++) cout << q[i] << ", ";
cout << q[n] << "}\n";
#else
for (int i = 1; i <= n; i++) cout << q[i] << ' ';
#endif
return 0;
}
|
跑得稍久一些，但是还是比较快的。
