日记 - 伊埃斯的博客站

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

上午

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$ 的点集里最大的来替换。

放一下代码：

1
#include<bits/extc++.h>
2
using namespace std;
3
int n,m,k;
4
vector<bool>add;//被cf的MLE整怕了，全都用的vector
5
vector<int>in,ans;
6
vector<vector<int>>g;
7
priority_queue<int,vector<int>,greater<int>>q1;//显然入度为0的
8
priority_queue<int,vector<int>,less<int>>q2;//可能入度为0的
9
signed main()
10
{
11
    ios::sync_with_stdio(0);
12
    cin.tie(0);
13
    cout.tie(0);
14
    cin >> n >> m >> k;
15
    add.resize(n + 5),in.resize(n + 5),g.resize(n + 5);
16
    for (int i = 1,u,v; i <= m; i++)
17
    {
18
        cin >> u >> v;
19
        g[u].push_back(v);
20
        in[v]++;
21
    }
22
    for (int i = 1; i <= n; i++)
23
        if (!in[i])
24
            q1.push(i);
25
    int cnt = 0;
26
    while (ans.size() < n)
27
    {
28
        if (q1.empty())
29
        {
30
            int u = q2.top();
31
            q2.pop();
32
            for (auto v : g[u])
33
            {
34
                in[v]--;
35
                if (in[v] == 0)
36
                    q1.push(v);
37
            }
38
            ans.push_back(u);
39
            continue;
40
        }
41
        int u = q1.top();
42
        q1.pop();
43
        if (cnt == k)
44
        {
45
            for (auto v : g[u])
46
            {
47
                in[v]--;
48
                if (in[v] == 0)
49
                    q1.push(v);
50
            }
51
            ans.push_back(u);
52
            continue;
53
        }
54
        if (!q1.empty())
55
        {
56
            add[u] = 1;
57
            cnt++;
58
            q2.push(u);
59
            continue;
60
        }
61
        if (q2.empty())
62
        {
63
            for (auto v : g[u])
64
            {
65
                in[v]--;
66
                if (in[v] == 0)
67
                    q1.push(v);
68
            }
69
            ans.push_back(u);
70
            continue;
71
        }
72
        int v = q2.top();
73
        if (v < u)
74
        {
75
            for (auto v : g[u])
76
            {
77
                in[v]--;
78
                if (in[v] == 0)
79
                    q1.push(v);
80
            }
81
            ans.push_back(u);
82
            continue;
83
        }
84
        q2.pop();
85
        q2.push(u),q1.push(v);
86
        add[u] = 1,cnt++;
87
    }
88
    for (auto i : ans)
89
        cout << i << " ";
90
    cout << '\n' << cnt << '\n';
91
    for (auto i = ans.begin() + 1; i != ans.end(); i++)
92
        if (add[*i])
93
            cout << *(i - 1) << " " << *i << '\n';
94
    return 0;
95
}

T4

还没改呢。

晚上

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

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

不重要，反正过了。

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

愿再无周天上午模拟赛。

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

Thanks for reading!

日记

周日 1月 19 2025

1285 字 · 7 分钟

life 日记