P7812 [JRKSJ R2] - Dark Forest 题解

Done

您已获得最佳的阅读体验！

题目地址：P7812

题目难度：省选/NOI-

题目类型：提交答案 Special Judge

本题为提交答案题。
给你一个长为的序列，定义的排列的权值为
你可以理解为这个排列是一个环，即。
请构造一个权值尽量大的的排列。
输入格式：
第一行一个整数。
第二行个整数表示序列。
输出格式：
一行个整数表示排列。
数据范围：
对于的数据，。
评分方式：
本题使用 Special Judge，每个测试点都有个参数。如果你的输出的权值，则该测试点您至少会获得分。
特别的，如果您的输出不是一个的排列，您会在该测试点获得分。
评分参数已经放至附件。
附件下载：

评分参数

输入数据

什么？提交答案题？直接打表！

首先我们需要明确如何才能构造出一个符合题意的排列，暴力枚举的复杂度是的，显然是不可取的做法。因此我们考虑随机化做法。

测试点 1-2#

提到随机化，我们有模拟退火。先随机一个的排列，再任意交换若干元素并与先前的序列权值进行比较，若更优则直接采纳，否则就依据准则概率接受，其余情况则恢复原状。

在本地跑没有时限，可以把参数调精一点。

1
#include <bits/stdc++.h>
2
#define N 1010
3
#define PRINT_TABLE
4
using namespace std;
5

6
typedef long long ll;
7

8
int n;
9
ll a[N], p[N], q[N];
10
random_device rd;
11
ll ans = 0;
12

13
double rand(double l, double r) {
14
    return (double) rd() / random_device::max() * (r - l) + l;
15
}
16

17
int rand(int l, int r) {
18
    return (int) (rd() % (r - l + 1)) + l;
19
}
20

21
ll calc() {
22
    // 计算权值
23
    ll sum = p[1] * a[p[n]] * a[p[1]] * a[p[2]];
24
    for (int i = 2; i < n; i++) sum += p[i] * a[p[i - 1]] * a[p[i]] * a[p[i + 1]];
25
    sum += p[n] * a[p[n - 1]] * a[p[n]] * a[p[1]];
26
    return sum;
27
}
28

29
void SA() {
30
    double T = 1e10;
31
    ans = max(ans, calc());
32
    while (T > 1e-17) {
33
        int a = rand(1, n), b = rand(1, n);
34
        swap(p[a], p[b]);
35
        ll now = calc();
36
        long double delta = now - ans;
37
        if (delta > 0) {
38
            memcpy(q, p, sizeof p);
39
            ans = now;
40
        } else if (exp(delta / T) <= (double) rd() / random_device::max()) swap(p[a], p[b]);
41
        T *= 0.99996;
42
    }
43
}
44

45
int main() {
46
    ios::sync_with_stdio(false);
47
    cin.tie(nullptr);
48
    cout.tie(nullptr);
49

50
    // Test Point #1 #2
51
    cin >> n;
52
    for (int i = 1; i <= n; i++) cin >> a[i];
53
    for (int i = 1; i <= n; i++) p[i] = i;
54
    shuffle(p + 1, p + 1 + n, mt19937(rd()));
55
    SA();
56
    clog << ans << endl;
57
// 打表格式化
58
#ifdef PRINT_TABLE
59
    cout << '{';
60
    for (int i = 1; i < n; i++) cout << q[i] << ", ";
61
    cout << q[n] << "},\n";
62
#else
63
    for (int i = 1; i <= n; i++) cout << q[i] << ' ';
64
#endif
65
    return 0;
66
}

一般来说一秒之内可以出答案。

测试点 3#

测试点 3 的数据很有意思，它是一个单调递增的排列。模拟退火跑了很久，得出的排列有两头大、中间小的特征。于是大胆构造一个特解——从左至右奇数递减、从右至左偶数递减。

测试点 4-10#

模拟退火调了半天参数就是过不去……同机房的大佬好像用加强版的模拟退火跑了几天才跑过？这里推荐一个叫“遗传算法”的解决方案。

遗传算法能通过模拟生物繁衍、自然选择等自然现象来实现求解全局最优解的功能。具体是让当前的优解进行变换，期望能得到一个更优的解。

1
#include <bits/stdc++.h>
2
#define N 1010
3
#define PRINT_TABLE
4
#define LIMIT 141473199965824ll // 每个测试点的最大值
5

6
#pragma optimize(3)
7

8
using namespace std;
9

10
typedef long long ll;
11

12
int n;
13
ll ans = 0, submax = 0;
14
random_device rd;
15
ll a[N], p[N], q[N], id[N];
16

17
ll calc(const ll arr[] = p) {
18
    ll sum = arr[1] * a[arr[n]] * a[arr[1]] * a[arr[2]];
19
    for (int i = 2; i < n; i++) sum += arr[i] * a[arr[i - 1]] * a[arr[i]] * a[arr[i + 1]];
20
    sum += arr[n] * a[arr[n - 1]] * a[arr[n]] * a[arr[1]];
21
    return sum;
22
}
23

24
ll d(int pos1, int pos2) {
25
    // 处理交换前后的变化量
26
    ll sum = 0;
27
    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]];
28
    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]];
29
    swap(p[pos1], p[pos2]);
30
    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]];
31
    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]];
32
    return sum;
33
}
34

35
int rand(int l, int r) {
36
    return (int) (rd() % (r - l + 1)) + l;
37
}
38

39
void GA() {
40
    while (ans < LIMIT) {
41
        for (int i = 1; i <= 20; i++) {
42
            int a = rand(1, n), b = rand(1, n);
43
            swap(p[a], p[b]);
44
        }
45
        submax = calc(); // 当前值
46
        shuffle(id + 1, id + 1 + n, mt19937(rd())); // 每次打乱枚举顺序
47
        bool flag;
48
        do { // 还能变得更优就继续下去
49
            flag = false;
50
            #pragma unroll 20
51
            for (int i = 1; i < n; i++) {
52
                for (int j = i + 1; j <= n; j++) {
53
                    ll cur;
54
                    int pos1 = id[i], pos2 = id[j];
55
                    if (abs(pos2 - pos1) <= 5 || abs(pos2 - pos1) >= n - 5) {
56
                        swap(p[pos1], p[pos2]);
57
                        cur = calc();
58
                    } else {
59
                        cur = submax + d(pos1, pos2);
60
                    }
61
                    if (cur > ans) {
62
                        ans = submax = cur;
63
                        memcpy(q, p, sizeof p);
64
                        if (ans > (ll) (LIMIT * 0.999)) cerr << ans << endl;
65
                        flag = true;
66
                        if (ans >= LIMIT) return;
67
                    } else if (cur > submax) {
68
                        submax = cur;
69
                        flag = true;
70
                    } else swap(p[pos1], p[pos2]);
71
                }
72
            }
73
        } while (flag);
74
    }
75
}
76

77
int main() {
78
    ios::sync_with_stdio(false);
79
    cin.tie(nullptr);
80
    cout.tie(nullptr);
81

82
    // Test Point #4 #5 #6 #7 #8 #9
83
    freopen("9.in", "r", stdin);
84
    freopen("9.out", "w", stdout);
85
    cin >> n;
86
    for (int i = 1; i <= n; i++) cin >> a[i];
87
    for (int i = 1; i <= n; i++) p[i] = i, id[i] = i;
88
    GA();
89
    clog << "Final Answer: " << calc(q) << " Overloaded: " << calc(q) - LIMIT << endl;
90
#ifdef PRINT_TABLE
91
    cout << '{';
92
    for (int i = 1; i < n; i++) cout << q[i] << ", ";
93
    cout << q[n] << "}\n";
94
#else
95
    for (int i = 1; i <= n; i++) cout << q[i] << ' ';
96
#endif
97
    return 0;
98
}

跑得稍久一些，但是还是比较快的。

音乐

音乐

测试点 1-2#

测试点 3#

测试点 4-10#

评论区

音乐

目录