日记

Wed Apr 09 2025

6 分钟

896 字

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

Square Subsequences Link to

谁能给我讲讲 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 Link to

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

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

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

放下我的常数超大代码：

CPP

#include<bits/extc++.h>
#define int long long
using namespace std;
const int maxn = 3e5 + 5;
int n;
int a[maxn];
class two_set
{
    private:
    multiset<int,less<>> mx;// 小根堆维护最大的几个数
    multiset<int,greater<>> mi;// 大根堆维护最小的几个数。
    void balance()
    {
        if (mx.size() > mi.size() + 1)
        {
            _min += *mx.begin();
            _max -= *mx.begin();
            mi.insert(*mx.begin());
            mx.erase(mx.begin());
        }
        if (mi.size() > mx.size())
        {
            _max += *mi.begin();
            _min -= *mi.begin();
            mx.insert(*mi.begin());
            mi.erase(mi.begin());
        }
    }
    public:
    int _min,_max;// 分别表示最小的数的和，最大的数的和。
    void insert(int x)
    {
        if (mx.empty() || x >= *mx.begin())
        {
            _max += x;
            mx.insert(x);
        }
        else
        {
            _min += x;
            mi.insert(x);
        }
        balance();
    }
    void erase(int x)
    {
        auto it = mx.find(x);
        if (it != mx.end())
        {
            _max -= x;
            mx.erase(it);
        }
        else
        {
            _min -= x;
            it = mi.find(x);
            assert(it != mi.end());
            mi.erase(it);
        }
        balance();
    }
}s1,s2;
void solve1()// 起码这里挺简洁的
{
    for (int i = 1; i <= n; i++)
        s2.insert(a[i]);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        s2.erase(a[i]);
        if (i & 1)
            ans = max(ans,s1._max - s1._min + s2._max - s2._min);
        s1.insert(a[i]);
    }
    printf("%lld",ans);
}
void solve2()
{
    sort(a + 1,a + n + 1);
    int _max = 0,_min = 0;
    for (int i = 1; i <= n >> 1; i++)
        _min += a[i];
    for (int i = (n >> 1) + 1; i <= n; i++)
        _max += a[i];
    printf("%lld",_max - _min);
}
signed main()
{
    scanf("%lld",&n);
    for (int i = 1; i <= n; i++)
        scanf("%lld",a + i);
    if (n & 1)
        solve1();
    else
        solve2();
    return 0;
}

后日谈 Link to 后日谈

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

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

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

日记

Square Subsequences# Link to

Adjacent Delete# Link to

后日谈 # Link to 后日谈

日记

Square Subsequences Link to

Adjacent Delete Link to

后日谈 Link to 后日谈