The secret of being a bore is to tell everything

0%

[CF1286A] Garland

题意

有一个由$1-n(n\leq 100)$构成的数列,其中部分被删除(删除的元素由$0$代替),请用被删除的元素补全这个数列,使这个数列中相邻元素奇偶性不同的对数最少。

解题思路

这种又像贪心又像dp的题当然是要使用随机化算法了(其实是dp太难想了)。

首先先明确这道题要求的是什么,其实是这个式子:

$
f(a)=\sum\limits_{i=2}^{n} parity(a_{i-1}) \oplus parity(a_i)
$

由于缺失的数字要么是奇数,要么是偶数,所以问题转化为如何将这些奇数和偶数填进数组使得相邻两数之间的奇偶性不同的对数最少。

由于没有什么明显的性质,dp式子也不好推,看一下数据范围$n\leq100$,那么我们显然可以用爬山/模拟退火等随机化算法搞一搞。

我们先从估价函数开始分析,对于这道题估价函数只需要$O(n)$的复杂度,完全可以接受。

接下来我们考虑枚举后继状态的转移,运用爬山的思想,我们只需要选择后继状态里面$f(a’)$比当前状态小且最小的那个$a’$就行了。如果发现没有任何后继状态比这个状态更好我们就可以退出爬山了。具体的枚举方式可以是交换两个奇偶性不同的填充数字,形成一个新的排列。

我第一次尝试的就是随机化爬山算法。一般来说,使用随机爬山算法足以应付大部分随机化题目,但是发现爬山在本题有一个致命的缺陷。设状态$x$为当前最优状态,当$f(a’)=f(x)$的时候爬山算法是不会转移到$a’$的。但是这题的函数是可以长这个样子的

于是随机爬山算法的很多起始点都会被这块平原阻挡,无法到达全局最优解。此时我们就需要对$f(a’)=f(x)$状态的转移进行优化,引入模拟退火的温度概念。每次遇到与当前最优解相同的状态都用一个概率$e^{-\frac{1}{T}}$去接受它,接受的概率会随着文读的下降而下降,而与模拟退火不同的是我们不接受任何不优的$a’$。因为这题的特殊性质,$f(a’)<f(x)$基本上是不会产生更优解,反而会浪费计算资源的。

加入了这个优化以后就能以相当高的几率得到最优解,同时我并没有对运行时间进行什么优化,这个算法实际上还可以更快。具体实现可以参考我的代码:

时间复杂度

$O(n^2 \times 玄学)$

参考代码

1
mt19937 mt(15784371);
2
int a[MAXN], b[MAXN], p[MAXN];
3
int bin[MAXN];
4
5
// 估价函数
6
int eval() {
7
    int cnt = 0;
8
    for (int i = 0; i < m; i++) a[b[i]] = p[i];
9
    for (int i = 1; i < n; i++) cnt += (a[i - 1] & 1) ^ (a[i] & 1);
10
    return cnt;
11
}
12
int hill_climbing() {
13
    bool swp;
14
    int ans = eval();
15
    double T = 100;
16
    int cnt = 0;
17
    do {
18
        swp = false;
19
        for (int i = 0; i < m; i++) {
20
            for (int j = i + 1; j < m; j++) {
21
                if (p[i] == p[j]) continue;
22
                swap(p[i], p[j]);
23
                int e = eval();
24
                if (e < ans) {
25
                    // 遇到更优解一定转移
26
                    swp = true, ans = e;
27
                } else if (e == ans) {
28
                    // 如果解状态并不优,则机率接受它
29
                    double p = exp(-1 / T);
30
                    if (mt.max() * p > mt()) swp = true, ans = e;
31
                } else {
32
                    // 否则回退状态
33
                    swap(p[i], p[j]);
34
                }
35
            }
36
        }
37
        T *= 0.85;
38
        cnt++;
39
        // 结合了爬山算法和模拟退火,要么局部最优解跳出,要么温度过低跳出
40
    } while (swp && T > 1e-6);
41
    return ans;
42
}
43
44
void shuffle(int* a, int sz) {
45
    for (int i = sz - 1; i >= 0; i--) {
46
        int j = mt() % (i + 1);
47
        swap(a[i], a[j]);
48
    }
49
}
50
int search() {
51
    int ans = INF2;
52
    for (int t = 0; t < 20; t++) {
53
        shuffle(p, m);
54
        ans = min(ans, hill_climbing());
55
    }
56
    return ans;
57
}
58
int main() {
59
#ifdef LOCALLL
60
    freopen("in", "r", stdin);
61
    freopen("out", "w", stdout);
62
#endif
63
    scanf("%d", &n);
64
    for (int i = 0; i < n; i++) {
65
        scanf("%d", &a[i]);
66
        // b数组代表第i个空是a数组的第几个元素
67
        if (!a[i]) b[m++] = i;
68
        bin[a[i]] = true;
69
    }
70
    int odd = 0;
71
    for (int i = 1; i <= n; i++)
72
        if (!bin[i])
73
            if (i & 1) odd++;
74
    // p数组代表第i个空是奇数还是偶数
75
    for (int i = 0; i < odd; i++) p[i] = 1;
76
    for (int i = odd + 1; i < m; i++) p[i] = 0;
77
    printf("%d\n", search());
78
    return 0;
79
}