mydcwfy's Blog

Luogu P7812 Dark Forest

Posted on
Symbols count in article: 2.7k Reading time ≈ 6 mins.

哈哈，没事就做提答题。

题意：给定长度为 $n$ 的序列 $a$，定义一个排列 $p$ 的权值为：

请给出一个排列，使得该权值尽量大。$n, a_i\leq 10 ^ 3$。已给出所有数据点。

显然考虑乱搞。

有一个比较神秘的思路就是你每次随机交换两个数，然后计算答案。但是有一个问题就是你很容易陷入一个局部最优解，导致怎么都跳不出来。可以考虑类似模拟退火的做法，随机一定概率接受新解。

这里需要优化复杂度（？）的地方是你需要 $O(1)$ 计算 $val$ 的变化量，可以暴力推式子，如果像我一样懒的人可以把所有影响到的位置重新算一遍，可能略慢一些。

然后通过 Luogu 题解区我们发现退火后面几个点几乎跑不出来，于是可以考虑固定一个次数， 每多少次直接 std::shuffle 一下，从头计算。这样大概能多过一些点，具体记不太清楚了。

你会发现你每次 std::shuffle 把前面的功夫全部弃掉，这样也不好，于是可以固定次数时，随机交换一些位置。这时 $n = 1000$，你取 $B = 2\times 10 ^ 7$ 随机交换一些位置，大概可以在 2.5min 通过 Test #10，得到 99 pts 的好成绩，Test #3 跑不过去。

注意 Test #3 的情况，$a_i = i$，考虑构造，将最大的那一个数 $x$ 放在 $x - 1$ 和 $x - 2$ 中间。这样一定是最大的（也不一定，反正过了）。这样就可以通过。

另外，你如果中间变量输出比较多的话，你会发现其实 $B = 2\times 10 ^ 7$ 过大，随便取小一点，大概 30s 即能跑过 Test #10，1min 多一点即可通过 Test #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
const int N = 1e3 + 10;
int n, a[N], p[N];
LL val, score[11];
std::mt19937 rnd;

inline int pre(int x) { return (x + n - 2) % n + 1; }
inline int nxt(int x) { return x % n + 1; }

LL getval(int i) { return (LL) p[i] * a[p[i]] * a[p[pre(i)]] * a[p[nxt(i)]]; }

LL calc(int l, int r)
{
    LL res = 0;
    for (int i = l; i <= r; ++ i)
        res += getval(i);
    return res;
}

void SA()
{
    int x = rnd() % n + 1, y = rnd() % n + 1;
    if (x == y) return;
    LL nw = val;
    std::vector<int> v{pre(x), x, nxt(x)};
    if (std::find(v.begin(), v.end(), pre(y)) == v.end()) v.push_back(pre(y));
    if (std::find(v.begin(), v.end(), y) == v.end()) v.push_back(y);
    if (std::find(v.begin(), v.end(), nxt(y)) == v.end()) v.push_back(nxt(y));
    for (int x : v) nw -= getval(x);
    std::swap(p[x], p[y]);
    for (int x : v) nw += getval(x);
    if (nw < val) std::swap(p[x], p[y]);
    else val = nw;
}

struct Timer {
    ~Timer() { std::cout << clock() / 1000000. << " s used" << std::endl; }
} timer;

int main(int argc, char *argv[])
{
    std::ifstream fin(argv[1]), fans(argv[2]);
    fin >> n;
    rnd.seed((long long) new char);
    for (int i = 1; i <= n; ++ i) fin >> a[i];
    std::vector<int> curp{1, 2, 3};
    for (int i = 4; i <= n; ++ i)
    {
        for (int j = 0; j < i - 1; ++ j)
            if (curp[j] == i - 2 || curp[j] == i - 1) {
                curp.insert(curp.begin() + j + 1, i);
                break;
            }
    }
    for (int i = 0; i < n; ++ i) p[i + 1] = curp[i];
    for (int i = 0; i < 10; ++ i) fans >> score[i];
    fin.close(), fans.close();
    LL cnt = 0;
    val = calc(1, n);
    while (++ cnt)
    {
        SA();
        if (cnt % 1000000 == 0) {
            int curscore = 0;
            for (int i = 0; i < 10; ++ i) curscore += val >= score[i];
            if (cnt % 2000000 == 0) {
                printf("SA cnt : %lld   Val : %lld   Score : %d   Goal val : %lld   Delta : %.10lf\n",
                    cnt, val, curscore, score[9], (val - score[9]) * 1. / score[9]);
                std::ofstream fout("test.out");
                for (int i = 1; i <= n; ++ i) fout << p[i] << ' ';
                fout.close();
            }
            if (cnt % 6000000 == 0) {
                int T = 25;
                while (T --) std::swap(p[rnd() % n + 1], p[rnd() % n + 1]);
                val = calc(1, n);
            }
        }
    }
    return 0;
}