日记 - 伊埃斯的博客站

弄懂每一题。~~然而我太蠢了~~

Square Subsequences↗

谁能给我讲讲 bitset 优化 LCS 啊？

简而言之就是枚举中间的分界点，然后对于两边的子串跑 bitset 优化 LCS。记录最大的 LCS 长度与其对应的 bitset。然后通过 bitset 反推 dp 数组，从而反推方案。时间复杂度 $O(\frac{n^3}{\omega} + n^2)$ ，时限 $2$ s，在 CF 神机上跑了 $1.5$ s，换别的 OJ 还不一定跑的完。

然而我太蠢了没弄懂 bitset 优化 LCS。

Adjacent Delete↗

自从学了 C# 和 Java 以来，代码风格愈发面向对象了。与之而来的还有更大的常数。希望不要搞出在赛场上因为常数太大而 TLE 的事。

考虑没有相邻的限制如何做。显然是最大的 $\frac{n}{2}$ 个减去最小的 $\frac{n}{2}$ 个。现在考虑相邻的限制，这个上界也是可行的。我们把每个最大的 $\frac{n}{2}$ 的标成 +，最小的那几个标成 -。显然无论如何都会有一对 + 和 - 相邻。

对于偶数 $n$ 显然就是那个上界。对于奇数 $n$ ，因为会留下一个，留下的这个会将 $a$ 数组分成两半，而两边都会取完，所以两边的长度肯定都是偶数。所以留下的只能是 $a_1,a_3,a_5,\dots$ ，对于两边，就是上文的上界。我们可以用两个 multiset 维护。一个小根的维护大的那几个数，大根的维护小的那那几个数。每次如果插入的 $x$ 大于等于小根堆的堆顶，就插入小根堆。否则插入大根堆。并维护一个堆内和。

放下我的常数超大代码：

1
#include<bits/extc++.h>
2
#define int long long
3
using namespace std;
4
const int maxn = 3e5 + 5;
5
int n;
6
int a[maxn];
7
class two_set
8
{
9
    private:
10
    multiset<int,less<>> mx;// 小根堆维护最大的几个数
11
    multiset<int,greater<>> mi;// 大根堆维护最小的几个数。
12
    void balance()
13
    {
14
        if (mx.size() > mi.size() + 1)
15
        {
16
            _min += *mx.begin();
17
            _max -= *mx.begin();
18
            mi.insert(*mx.begin());
19
            mx.erase(mx.begin());
20
        }
21
        if (mi.size() > mx.size())
22
        {
23
            _max += *mi.begin();
24
            _min -= *mi.begin();
25
            mx.insert(*mi.begin());
26
            mi.erase(mi.begin());
27
        }
28
    }
29
    public:
30
    int _min,_max;// 分别表示最小的数的和，最大的数的和。
31
    void insert(int x)
32
    {
33
        if (mx.empty() || x >= *mx.begin())
34
        {
35
            _max += x;
36
            mx.insert(x);
37
        }
38
        else
39
        {
40
            _min += x;
41
            mi.insert(x);
42
        }
43
        balance();
44
    }
45
    void erase(int x)
46
    {
47
        auto it = mx.find(x);
48
        if (it != mx.end())
49
        {
50
            _max -= x;
51
            mx.erase(it);
52
        }
53
        else
54
        {
55
            _min -= x;
56
            it = mi.find(x);
57
            assert(it != mi.end());
58
            mi.erase(it);
59
        }
60
        balance();
61
    }
62
}s1,s2;
63
void solve1()// 起码这里挺简洁的
64
{
65
    for (int i = 1; i <= n; i++)
66
        s2.insert(a[i]);
67
    int ans = 0;
68
    for (int i = 1; i <= n; i++)
69
    {
70
        s2.erase(a[i]);
71
        if (i & 1)
72
            ans = max(ans,s1._max - s1._min + s2._max - s2._min);
73
        s1.insert(a[i]);
74
    }
75
    printf("%lld",ans);
76
}
77
void solve2()
78
{
79
    sort(a + 1,a + n + 1);
80
    int _max = 0,_min = 0;
81
    for (int i = 1; i <= n >> 1; i++)
82
        _min += a[i];
83
    for (int i = (n >> 1) + 1; i <= n; i++)
84
        _max += a[i];
85
    printf("%lld",_max - _min);
86
}
87
signed main()
88
{
89
    scanf("%lld",&n);
90
    for (int i = 1; i <= n; i++)
91
        scanf("%lld",a + i);
92
    if (n & 1)
93
        solve1();
94
    else
95
        solve2();
96
    return 0;
97
}

后日谈

yzp 因为鞋子没垫鞋垫导致他极其不舒服。然后今天也是十分颓废，只做了 $3$ 题。

yzp 说他想回家，我的评价是：住校生是这样的。

不过住校生不开心还可以逃回家，走读生逃回家也没用，因为天天回家，对家已经无感了。不开心的时候只能畅想去到异世界。~~中二病~~

Thanks for reading!

日记

周三 4月 09 2025

848 字 · 6 分钟

life 日记