日记

Sun Jan 19 2025

7 分钟

life 日记

1329 字

闲的无聊所以来写日记了。

上午#

C组模拟赛没有发题解

什么叫 C组呢，也许是往题里塞两道黑题就叫 C组了吧。

T1#

赛时想法： $\mathcal{O}(n^{2})$ 暴力。

T2#

赛时想法： $\empty$

T3#

赛时想法：对于特殊性质 $1$ ，也就是加不了边的情况，我们直接输出字典序最小的拓扑序就可以了。对于特殊性质 $2$ ，我的部分分打挂了，这里就不说了。

T4#

赛时想法：还是 $\empty$ 。

总分 $60$ 。究其原因是今天是周天，生物钟没调过来，于是上午一整个上午都是晕乎乎的，根本做不了题。

下午#

T1#

source

设 $a_{i}$ 为原来的第 $i$ 个字符串，然后对 $a_{i}$ 排序， $b_{i}$ 是 $\operatorname{reverse}(a_{i})$ 。对 $b_{i}$ 离散化，那么答案就是最长上升子序列长度。设 $dp_{i,0/1}$ 表示到结尾为 $i$ 个串的最长上升子序列的长度，那么明显有 $dp_{i,j} = \max\limits_{x = 1}^{i - 1}dp_{x,\neg j} + 1$ 。发现是一段带更新的前缀最大值，直接用树状数组就可以了。

T2#

source

我们至今也不知道林夕的做法（也是我的）到底错在了哪里。

别的不重要，重要的是你得知道这是一个差分约束，可以通过 $a_{i}$ 和 $b_{i}$ 推出 $114514$ 个约束，于是我们就可以愉快的开始 spfa。时间复杂度 $\mathcal{O}(n^{2})$ 。

但是，spfa 似了，不是 T， $n \le 5000$ ，T 不了一点，它 WA 了。然而这个可恶的 Gym，不让我看数据，于是我只能尝试造一组 Hack 出来。于是，造了一下午，成功的造出了两组不合法的数据。浪费了我一个下午。

但是我还是不知道这个差分约束做法假在了哪里。

T3#

谁家好人从 T3 开始就放黑题啊。

有一个结论：如果最初的拓扑序是 $p$ ，那么肯定存在一种最优方案是 $p_{i} \rightarrow p_{i + 1}$ 。感性理解就行，~~因为我不会证~~。我们有贪心策略：把所有入度为 $0$ 的点取出，其中编号最小的点是 $u$ 。

如果 $u$ 不是唯一的入度为 $0$ 的点，那么我们肯定想加一条边让 $u$ 滚到后面去。具体加哪条边不重要，我们算出拓扑序之后根据拓扑序去推出来就行。
如果 $u$ 是唯一的，那么就只能让 $u$ 为当前元素，然后删除 $u$ 。

但是这么做，我们就忘记了考虑那些通过新加的边连接到 $u$ 的点了，他们的入度就永远为 $1$ 了。正因如此，我们应该维护两个集合，一个是显然入度为 $0$ 的，另一个是可能入度为 $0$ 的。

那么改正后的贪心策略就是这个样子的：

如果 $u$ 不是唯一的入度为 $0$ 的点，那么我们肯定想加一条边让 $u$ 滚到后面去。具体加哪条边不重要，我们算出拓扑序之后根据拓扑序去推出来就行。
如果 $u$ 是唯一的，那么就让可能入度为 $0$ 的点集里最大的来替换。

放一下代码：

CPP

#include<bits/extc++.h>
using namespace std;
int n,m,k;
vector<bool>add;//被cf的MLE整怕了，全都用的vector
vector<int>in,ans;
vector<vector<int>>g;
priority_queue<int,vector<int>,greater<int>>q1;//显然入度为0的
priority_queue<int,vector<int>,less<int>>q2;//可能入度为0的
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    add.resize(n + 5),in.resize(n + 5),g.resize(n + 5);
    for (int i = 1,u,v; i <= m; i++)
    {
        cin >> u >> v;
        g[u].push_back(v);
        in[v]++;
    }
    for (int i = 1; i <= n; i++)
        if (!in[i])
            q1.push(i);
    int cnt = 0;
    while (ans.size() < n)
    {
        if (q1.empty())
        {
            int u = q2.top();
            q2.pop();
            for (auto v : g[u])
            {
                in[v]--;
                if (in[v] == 0)
                    q1.push(v);
            }
            ans.push_back(u);
            continue;
        }
        int u = q1.top();
        q1.pop();
        if (cnt == k)
        {
            for (auto v : g[u])
            {
                in[v]--;
                if (in[v] == 0)
                    q1.push(v);
            }
            ans.push_back(u);
            continue;
        }
        if (!q1.empty())
        {
            add[u] = 1;
            cnt++;
            q2.push(u);
            continue;
        }
        if (q2.empty())
        {
            for (auto v : g[u])
            {
                in[v]--;
                if (in[v] == 0)
                    q1.push(v);
            }
            ans.push_back(u);
            continue;
        }
        int v = q2.top();
        if (v < u)
        {
            for (auto v : g[u])
            {
                in[v]--;
                if (in[v] == 0)
                    q1.push(v);
            }
            ans.push_back(u);
            continue;
        }
        q2.pop();
        q2.push(u),q1.push(v);
        add[u] = 1,cnt++;
    }
    for (auto i : ans)
        cout << i << " ";
    cout << '\n' << cnt << '\n';
    for (auto i = ans.begin() + 1; i != ans.end(); i++)
        if (add[*i])
            cout << *(i - 1) << " " << *i << '\n';
    return 0;
}

T4#

还没改呢。

晚上#

生物的节律行为：烷螈砷。

然后就是晚上的颓废写题时间。看到 xguagua_Firefly 发的树套树求助帖，于是去看了一眼题目，直接分块喵过去了。题面里说树套树是 $1000$ 毫秒多的，我的分块跑了 $2.5$ 秒，时限 $3$ 秒，好像有点劣哈。

不重要，反正过了。

因为晚上闲的没事干（不是你题改完了吗你就闲的没事干）所以就来写日记了。

愿再无周天上午模拟赛。

昨天晚上的 abc，切了 $4$ 题，但是 rating 只从 $230$ 涨到了 $360$ ，还是菜啊，究其原因是码力不行，第五题想到了疑似正解，但是码力不行，没能在 $20$ min 打出，不然应该还能再加点。

日记

https://nahida.cfd/blog/2025-01-19日记/