Znzryb's Blog
0%

Posted on

题目大意

题目归纳

给定一个数组大小 nn (1≤n≤1041 \le n \le 10^4)，需要构建并按特定格式可视化一个线段树。

线段树构建规则

  • 根节点：对应半开区间 [0,n)[0, n)。

  • 分裂规则：对于非叶子节点 [L,R)[L, R)，其中点为 M=⌊(L+R)/2⌋M = \lfloor (L+R)/2 \rfloor。左子节点为 [L,M)[L, M)，右子节点为 [M,R)[M, R)。

  • 叶子节点：对应区间长度为 1 的节点 [i,i+1)[i, i+1)。

可视化输出规则

  • 分层输出：树的根在第一行，子节点在下一行，以此类推。

  • 节点格式：显示为 [L;R)。

  • 分隔竖线：如果节点 [L,R)[L, R) 不是叶子，必须在其分号 ; 的正下方（即同一列），从该节点的下一行开始直到整个图形的最后一行，绘制竖线 |。这表示左右子树的物理分隔。

  • 排版约束：

    • 同一行内的元素（节点文本或竖线）之间至少保留 1 个空格。
    • 在满足对齐条件的前提下，空格数量应尽可能少。
    • 整个图形靠左对齐（即至少有一行的行首没有空格）。
    • 行末不得有多余空格。

样例展示与解释

样例 1 (n=3n=3)

1
2
3
    [0;3)
[0;1) |     [1;3)
      | [1;2) | [2;3)

解释：

  • 第 1 行：根节点 [0,3)[0, 3)。其中点为 1，分号 ; 所在列决定了后续行的主分隔线位置。

  • 第 2 行：

    • 左子节点 [0,1)[0, 1)。
    • 中间是根节点 [0,3)[0, 3) 延伸下来的竖线 |。
    • 右子节点 [1,3)[1, 3)。

  • 第 3 行：

    • 左侧空位（因为 [0,1)[0, 1) 是叶子）。
    • 根节点的竖线 | 继续延伸。
    • [1,3)[1, 3) 分裂为 [1,2)[1, 2) 和 [2,3)[2, 3)，中间由 [1,3)[1, 3) 的分号 ; 延伸出的竖线 | 分隔。

  • 对齐：所有竖线 | 都严格位于其父节点 ; 的正下方，且元素间距最小化。

样例 2 (n=7n=7)

1
2
3
4
                    [0;7)
    [0;3)             |             [3;7)
[0;1) |     [1;3)     |     [3;5)     |     [5;7)
      | [1;2) | [2;3) | [3;4) | [4;5) | [5;6) | [6;7)

解释：

  • 展示了更深层的结构。每一层新产生的分支节点都会在其 ; 下方产生一条新的竖线，一直延伸到底部。

  • 例如，根节点 [0,7)[0, 7) 的竖线贯穿了第 2、3、4 行。

  • 第 2 行的节点 [0,3)[0, 3) 和 [3,7)[3, 7) 的竖线分别贯穿了第 3、4 行。

思路讲解

这道题目主要就是考验你的一个实现的这个能力。比较建议的实现方法呢，就是这个宽度的计算呢，先使用一个函数进行总的宽度的计算。然后需要注意啊，这道题目不允许出现后导空格，就是它不会自动忽略后导空格。所以你需要在输出的时候把所有的后导空格给 pop back 给 pop 掉。

https://codeforces.com/gym/106169/submission/363482617 因为后导空格 WA 的一发。

然后还有一个点呢，就是这道题目它使用的是左臂右开，0 base 的，那么你最好也仿照它使用左臂右开0 base 的，不要把它，不要用1 base 的做这道题目，1 base 的做这道题目。是会有问题的，因为因为这个嗯，因为一加一个数，然后再 向下整除二，和0加一个数再向下整除二，它其实这个区间是会有不同的。

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
void visualize() {
    widths.resize(4 * N + 2);
    cal_visual_w(1, 1);
    grid.resize(mx_layer + 2, string(widths[1], ' '));
    visualize(1, 0, 1);
    for (int i = 1; i <= mx_layer; ++i) {
        while (!grid[i].empty() && grid[i].back()==' ') {
            grid[i].pop_back();
        }
        cout << grid[i] << "\n";
    }
}

void cal_visual_w(ll u, ll layer) {
    mx_layer = max(mx_layer, layer);
    if (infos[u].l == infos[u].r-1) {
        widths[u] = infos[u].to_string().size();
        return;
    }
    cal_visual_w(u << 1, layer + 1);
    widths[u] = widths[u << 1] + 3;
    cal_visual_w(u << 1 | 1, layer + 1);
    widths[u] += widths[u << 1 | 1];
}

// 可视化线段树
void visualize(ll u, ll sc, ll layer) {
    if (infos[u].l == infos[u].r-1) {
        string label = infos[u].to_string();
        for (ll i = 0; i < label.size(); ++i) {
            grid[layer][sc + i] = label[i];
        }
        return;
    }
    visualize(u << 1, sc, layer + 1);
    string label = infos[u].to_string();
    ll pos = label.find(';');
    ll labStart = sc + widths[u << 1] + 1 - pos;
    for (int i=1;i<=mx_layer;++i) {
        if (layer+i>mx_layer) break;
        grid[layer + i][sc + widths[u << 1] + 1] = '|';
    }
    // grid[layer + 1][sc + widths[u << 1] + 1] = '|';
    // if (layer+2 <= mx_layer) {
    //     grid[layer+2][sc + widths[u << 1] + 1]='|';
    // }
    for (ll i = 0; i < label.size(); ++i) {
        grid[layer][labStart + i] = label[i];
    }
    visualize(u << 1 | 1, sc + widths[u << 1] + 3, layer + 1);
}

AC代码

AC
https://codeforces.com/gym/106169/submission/363483057

Posted on Edited on

基本情况

https://codeforces.com/contest/2195

做出来5道题目，总体上来说也算是打爽了。

image

因为是用小号嘛，因为是用小号，所以说也不算说是特别急吼拉吼的写吧，不算特别急吼拉吼的。这个意义哇的一发是因为这个忘记取模了，忘记取模了。

这个 E 的时间应该还是有一定的优化空间，应该有一定优化空间。B 当时稍微卡了一下，因为是没有考虑到它有一些它是可以互相的，就是它虽然乘二，但是它没有跨越中间那道坎，那么实际上可以互相换。啊，可以互相换。不过 B 因为它是一个排列吧，所以说就用一个删除式 set 就可以解决。

你比较神秘啊。我发现就是我输出的答案，所有的输出的答案都比那个答案多了一个固定的数，然后我一眼看出来这个固定的数大概是多少。这个修正项就是我在红框当中那个式子的减法部分，就是我们的这个修正项。这个也是比较离谱啊，运气比较好，就被我一下子就看出来了。具体的原理我也不知道是什么，只能说可能就是和正确答案就是差的也不多吧，可能稍微多算了一些。然后这样子就能搞出来了。

image

不过也因为比较激动吧，也因为比较激动忘记取模了，绷不住了。

心得感悟

只能说激动归激动吧，不要忘记进行取模运算，绷不住了。

Posted on Edited on

题目大意

题意

给定 nn 个二次函数 F={f1,f2,…,fn}F=\{f_1, f_2, \dots, f_n\}，其中 fi(x)=aix2+bix+cif_i(x) = a_i x^2 + b_i x + c_i。

定义两个函数 ff 和 gg 是 独立 的，当且仅当对于所有的实数 x∈Rx \in \mathbb{R}，都有 f(x)≠g(x)f(x) \neq g(x)（即两个函数的图像在平面上没有交点）。

定义一个函数集合 G⊆FG \subseteq F 是 有序 的，当且仅当 GG 中任意两个不同的函数都是独立的。

对于每一个 ii (1≤i≤n1 \le i \le n)，请计算包含 fif_i 的最大有序子集的大小（即寻找一个最大的子集 S⊆FS \subseteq F，使得 fi∈Sf_i \in S 且 SS 是有序的，输出 ∣S∣|S|）。

数据范围

  • 1≤t≤1041 \le t \le 10^4

  • 1≤n≤30001 \le n \le 3000

  • −106≤ai,bi,ci≤106,ai≠0-10^6 \le a_i, b_i, c_i \le 10^6, a_i \neq 0

  • 保证所有测试用例中 n2n^2 的总和不超过 300023000^2。

输入格式

第一行包含一个整数 tt，表示测试用例的数量。
对于每个测试用例，第一行包含一个整数 nn。
接下来的 nn 行，每行包含三个整数 ai,bi,cia_i, b_i, c_i，描述第 ii 个二次函数。

输出格式

对于每个测试用例，输出一行 nn 个整数，第 ii 个整数表示包含 fif_i 的最大有序子集的大小。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
3
4
1 2 -1
-3 0 -3
-1 4 -5
1 2 -4
5
3 0 0
1 0 -5
-3 0 0
-1 0 10
1 0 -10
5
884 -667 497
680 -973 213
23 -548 -412
826 359 -333
773 212 218

样例输出

1
2
3
3 2 3 3
3 3 2 2 3
3 3 3 1 2

样例解释（第一组数据）

给定的 4 个函数如下：

  1. f1(x)=x2+2x−1f_1(x) = x^2 + 2x - 1

  2. f2(x)=−3x2−3f_2(x) = -3x^2 - 3

  3. f3(x)=−x2+4x−5f_3(x) = -x^2 + 4x - 5

  4. f4(x)=x2+2x−4f_4(x) = x^2 + 2x - 4

各函数包含于其中的最大有序子集如下：

  • 对于 f1f_1：集合 {f1,f3,f4}\{f_1, f_3, f_4\} 是有序的（两两无交点），大小为 3。

  • 对于 f2f_2：集合 {f1,f2}\{f_1, f_2\} 是有序的，大小为 2。

  • 对于 f3f_3：集合 {f1,f3,f4}\{f_1, f_3, f_4\} 是有序的，大小为 3。

  • 对于 f4f_4：集合 {f1,f3,f4}\{f_1, f_3, f_4\} 是有序的，大小为 3。

image

思路讲解

2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025) 2025 英国 ICPC——J. Joust Sort（拓扑排序解决依赖排序问题）

那么我们实际上可以使用记忆化的 DFS 去解决这个问题。

实际上来说呢，如果这个图它是一个完全图，它没有任何其他的性质的话，实际上是一个 NP 问题，也就是团问题。因此呢，实际上这个关系之间具有严格偏序关系。因此这个图实际上是一个 DAG。我们是就是要在一个 DAG 上去求包含该节点的一个最长链。

那么其实不难想到，这个是真不难想到，就是你去求包含一个节点的最长链的话，直接去求是比较困难的。你可以求，先求以这个点为起点的最长链（长度），再去求以这个点为终点的最长链（长度）。

不过其实求以这个点为终点的最长链的长度，你可能会说，哎，我不会求啊，这个怎么求？哎，实际上很简单，你就把图所有的边全部反向，然后再用跑，这个求以这个点为起点的最长链长度再跑一遍就好了。

实际上来说，这个东西，这个记忆化 DFS 能跑，也是因为这张图具有 DAG 性质。你实在不放心，也可以用拓扑排序去跑一个 DP 也不难，反正。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
auto solve=[&](vector<ll> &mx_chain,const vector<vector<ll>> &g) -> void {
    // 以 i 为根的，为链的起点的，记忆化 dfs 数组
    vector<ll> dp(N+2);
    vector<char> vis(N+2);
    auto dfs=[&](auto && self,ll u) -> void {
        if (vis[u]) {
            return;
        }
        vis[u]=true;
        for (auto to:g[u]) {
            // if (vis[to]) continue;
            self(self,to);
            dp[u]=max(dp[u],dp[to]);
        }
        dp[u]+=1;
    };
    for (int i=1;i<=N;++i) {
        dfs(dfs,i);
        mx_chain[i]=dp[i];
    }
};
solve(mx_chain1,org_g);
solve(mx_chain2,rev_g);

AC代码

AC
https://codeforces.com/contest/2195/submission/363306906

心路历程（WA，TLE，MLE……）

Posted on

我们建议啊，就是如果说你要作为 Priority queue 的话，那么建议使用 structure。这个是因为 C 加加的 priority queue 默认是大根堆，那么我们有的时候还是会使用小根堆嘛。对，而且这个 pair 它说白了它这个比较运算符和我们想的可能不是很一样嘛，所以说 priority queue 它这个比较也是比较奇怪的，所以我们建议你还是使用 structure。

如果说比较清楚的话，如果说比较清楚，就是没有什么比较复杂的情况，那我们就用 pair 就行了。因为 pair 的话，它 虽然可能有些时候它会慢那么一点点啊，但是有的时候可能它也会快，所以这个也有的时候也讲不清楚。它可能和这个机子也有关系，和这个编译器也有关系。

如果说元素超过了三个以上，是元素呢超过三个及以上，那么还是用 Structure 因为 Tuple 有点太奇怪了。你用 Tuple 的话，有的时候有点有点奇怪了。

Posted on Edited on

题目大意

题目总结

实验室里悬挂着 nn 个激光器，每个激光器的位置坐标为 xi=ix_i = i，初始距离天花板的高度为 aia_i。所有激光器朝向屏幕发射光线。

规则如下：

  1. 如果多个激光器处于同一高度（aia_i 相同），则坐标较小的激光器发出的光线会被阻挡，只有该高度下坐标最大的那个激光器能被屏幕接收。

  2. 你可以进行操作：选定任意一个激光器，将其高度增加 1（即 ai←ai+1a_i \leftarrow a_i + 1）。

  3. 最多可以进行 kk 次操作。

  4. 高度只能增加，不能减少。

你的目标是确定在不超过 kk 次操作的情况下，屏幕上最多能接收到多少个激光器的光线。

输入格式

第一行包含一个整数 tt (1≤t≤1041 \le t \le 10^4)，表示测试用例的数量。
每个测试用例的第一行包含两个整数 nn 和 kk (1≤n≤2⋅105,1≤k≤1091 \le n \le 2 \cdot 10^5, 1 \le k \le 10^9)，分别表示激光器的总数和最大操作次数。
第二行包含 nn 个整数 aia_i (1≤ai≤1091 \le a_i \le 10^9)，表示每个激光器的初始高度。

输出格式

对于每个测试用例，输出一个整数，表示最大可能的可见激光器数量。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
Input
3
4 4
1 2 3 4
4 5
1 1 1 1
9 2
4 3 3 10 5 5 5 99 11

Output
4
3
7

样例解释

  • 测试用例 1：所有激光器初始高度均不相同，没有遮挡，因此 4 个激光器全部可见。

  • 测试用例 2：初始所有 4 个激光器高度均为 1，只有坐标最大的第 4 个激光器可见。

    • 可以将第 2 个激光器高度增加 1（变 2），消耗 1 次操作。
    • 将第 3 个激光器高度增加 2（变 3），消耗 2 次操作。
    • 最终高度变为 [1, 2, 3, 1]。高度 1 的激光器中第 4 个可见，高度 2 的第 2 个可见，高度 3 的第 3 个可见。总共 3 个可见。

image

  • 测试用例 3：初始有 3 个高度为 5 的激光器，其中仅 1 个可见。可以将其中一个高度为 5 的激光器移动到高度 6（消耗 1 次操作），从而增加 1 个可见数量，总可见数达到 7。

思路讲解

由于不能够使用删除式 set 实现查找最靠近的点的这个操作。

Asia EC Online 2025 (I)——Canvas Painting （ 使用 dsu on next 实现大值域未涂色点的快速查找）

我们使用 DSU on next 实现未涂色点的快速查找。

然后我们会发现这个 dsu on next 配合 priority queue 进行懒更新会导致这个问题，它会导致出现这个 TLE。

使用这样子的一个更新，它的问题在于，比如说，如果说所有的高度都为一的话，那么其实会被反复的插入。说白了就是如果说是同样的这个值的话，如果说是同样值的话，实际上它是会被反复操作的。哎，不过其实啊，这个叫什么？我们其实就同一个值，我们操作一次即可。

TLE 的根本原因在于：当前的 DSU + 优先队列方案中，元素会被反复弹出再塞回优先队列。以所有 ai=1a_i = 1、N=2×105N = 2 \times 10^5 为例，每个元素平均会被重新插入 O(N)O(N) 次，总复杂度退化到 O(N2)O(N^2)。

上面是 AI 告诉我们的，你稍微想一下，你就会知道，确实是这样子的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
while (!pq.empty()) {
    auto [dis,u]=pq.top();
    pq.pop();
    ll to=u+dis;
    if (op_num-dis<0) {
        break;
    }
    if (fa_mp.contains(to)) {
        to=find(find,to);
        pq.push({to-u,u});
    }else {
        op_num-=dis;
        fa_mp[to]=to+1;
        ++ans;
    }
}

https://codeforces.com/gym/106169/submission/363034637

解决 DSU on Next 加 Priority Queue 懒更新的 TLE 问题。

那么我们上面已经说了，问题的关键在于重复值，它会非常傻的继续去全部都操作一遍。那么其实就是重复值我们一起操作就行了。

我们就给这个往 Priority Queue 里面塞的这个结构体啊，再加一个属性。这个结构体我们加一个属性，加一个属性 cnt 然后进行一起操作，懒操作就好了。

1
2
3
4
5
6
7
8
struct Dis_u_cnt{
    ll dis,u,cnt;
    bool operator<(const Dis_u_cnt &o) const {
        if (dis!=o.dis) return dis>o.dis;
        // 随便又写了一个这个东西，随便写了一个比较，其实无所谓。
        return u<o.u;
    }
};

我们的懒操作其实也很好写，其实就加一个 cnt 属性。你把它弹出来以后，如果 cnt 还大于一，你就减一。如果 cnt 已经是小于等于一了，那你 pop 掉了以后，其实这东西就没有了嘛，对吧？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
while (!pq.empty()) {
    auto [dis,u,cnt]=pq.top();
    pq.pop();
    ll to=u+dis;
    if (op_num-dis<0) {
        break;
    }
    if (fa_mp.contains(to)) {
        to=find(find,to);
        pq.push({to-u,u,cnt});
    }else {
        op_num-=dis;
        fa_mp[to]=to+1;
        ++ans;
        if (cnt>1) {
            to=find(find,to);
            pq.push({to-u,u,cnt-1});
        }
    }
}

AC代码

AC

https://codeforces.com/gym/106169/submission/363039919

心路历程（WA，TLE，MLE……）