RenaMoe's Blog

念念不忘，必有回响

0%

题解 P7078 贪吃蛇

发表于 更新于 分类于 Valine：

给出 n 条蛇，最大的蛇可以选择吃或不吃最小蛇，若某一轮中只剩一条蛇或者最大蛇不吃时停止，每条蛇都想活着并吃最多的蛇，求最后剩下的条数。

\(n\le 10^6,T\le 10\)。

博弈论+单调性优化。

CSP2020 T4，考场上压根没看。

思路

这题有 20 分白给，即 3 条蛇的情况，如果最大蛇吃完之后不是最小蛇肯定要吃。（博主这个煞笔 20 分都没有。）

推广到 n 条蛇，也是同样的道理，这样吃一直下去，直到最大蛇吃完后会变为最小蛇：

这种情况下，最大蛇吃了是有风险的，变成最小蛇时能不能活着要看下一条最大蛇，这种有风险的情况可能会递归下去。

于是现在有三种情况：

  • Case 1：最大蛇吃完之后不是最小蛇；
  • Case 2：最大蛇吃完之后是最小蛇；
  • Case 3：只剩 2 条蛇。

模拟整个过程：

第一个阶段是 Case 1，最大蛇会放心的吃；

第二个阶段是 Case 2，最大蛇吃后有风险，那么就先假定她吃，递归下去，会有两个边界：遇到 Case 1 或者 Case 3，这两种情况中最大蛇都肯定会吃，那么上一轮的最大蛇（此时为最小蛇）也就挂了，上一轮的最大蛇也就不会选择吃。

再往回退一层，上上轮的最大蛇知道会在下一轮停止，那么她也就会放心去吃。

可以发现 Case 2 吃不吃取决于递归层数的奇偶性。

如果没有经过 Case 2 就到了第三个阶段，最后就会只剩 1 条。

70 分实现

我们可以直接模拟，用 set 维护蛇，注意记录进入第二个阶段时的条数，这样 \(\mathcal O(Tn\log n)\) 可以拿到 70 分。

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
const int N = 1e6 + 9;

struct Snake {
    int val, id;
    Snake() {}
    Snake(int _val, int _id) : val(_val), id(_id) {}
    bool operator <(const Snake &t) const {
        return val == t.val ? id > t.id : val > t.val;
    }
};

int T, n, k;
int a[N];
set<Snake> s;

inline void main() {
    read(T);
    for (int c = 1; c <= T; ++c) {
        s.clear();
        if (c == 1) {
            read(n);
            for (int i = 1, x; i <= n; ++i)
                read(a[i]);
        }
        else {
            read(k);
            for (int i = 1, x, y; i <= k; ++i)
                read(x), read(y), a[x] = y;
        }
        for (int i = 1; i <= n; ++i)
            s.insert(Snake(a[i], i));
        int ans = 0, flag = 0;
        while (true) {
            if (s.size() == 2) {
                s.erase(--s.end());
                if (flag) {
                    if ((flag - s.size()) % 2) ans = flag + 1;
                    else ans = flag;
                }
                else ans = 1;
                break;
            }
            set<Snake>::iterator ma = s.begin(), mi = --s.end();
            int val = ma -> val - mi -> val, id = ma -> id;
            s.erase(ma), s.erase(mi);
            s.insert(Snake(val, id));
            if ((--s.end()) -> id == id) {
                if (!flag) flag = s.size();
            }
            else {
                if (flag) {
                    if ((flag - s.size()) % 2) ans = flag + 1;
                    else ans = flag;
                    break;
                }
            }
        }
        printf("%d\n", ans);
    }
}

优化

怎么搞到 \(\mathcal O(n)\) 啊，还能吃出个单调性？

联系到往届 NOIP 真题 蚯蚓，并观察发现，新加入的蛇是单调不升的。

因为后一轮的最大蛇比前一轮最大蛇小，后一轮最小蛇比前一轮最小蛇大。

那么 set 就不必了，开两个双端队列即可，一个维护原来的蛇，一个维护新加入的蛇。

100 分实现

复杂度 \(\mathcal O(Tn)\)。

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
const int N = 1e6 + 9;

struct Snake {
    int val, id;
    Snake() {}
    Snake(int _val, int _id) : val(_val), id(_id) {}
    bool operator <(const Snake &t) const {
        return val == t.val ? id < t.id : val < t.val;
    }
};

int T, n, k;
int a[N];
deque<Snake> q1, q2;

inline Snake get_max() {
    Snake res;
    if (q1.empty()) res = q2.back(), q2.pop_back();
    else if (q2.empty()) res = q1.back(), q1.pop_back();
    else {
        if (q1.back() < q2.back()) res = q2.back(), q2.pop_back();
        else res = q1.back(), q1.pop_back();
    }
    return res;
}

inline Snake get_min() {
    Snake res;
    if (q1.empty()) res = q2.front(), q2.pop_front();
    else if (q2.empty()) res = q1.front(), q1.pop_front();
    else {
        if (q1.front() < q2.front()) res = q1.front(), q1.pop_front();
        else res = q2.front(), q2.pop_front();
    }
    return res;
}

inline void main() {
    read(T);
    for (int c = 1; c <= T; ++c) {
        if (c == 1) {
            read(n);
            for (int i = 1, x; i <= n; ++i)
                read(a[i]);
        }
        else {
            read(k);
            for (int i = 1, x, y; i <= k; ++i)
                read(x), read(y), a[x] = y;
        }
        q1.clear(), q2.clear();
        for (int i = 1; i <= n; ++i)
            q1.push_back(Snake(a[i], i));
        int ans = 0, flag = 0;
        while (true) {
            if (q1.size() + q2.size() == 2) {
                if (flag) {
                    if ((flag - 1) % 2) ans = flag + 1;
                    else ans = flag;
                }
                else ans = 1;
                break;
            }
            Snake ma = get_max(), mi = get_min(), u(ma.val - mi.val, ma.id);
            if ((q1.empty() || u < q1.front()) && (q2.empty() || u < q2.front())) {
                if (!flag) flag = q1.size() + q2.size() + 1;
            }
            else {
                if (flag) {
                    if ((flag - (q1.size() + q2.size() + 1)) % 2) ans = flag + 1;
                    else ans = flag;
                    break;
                }
            }
            q2.push_front(u);
        }
        printf("%d\n", ans);
    }
}