Znzryb's Blog
0%

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 Edited 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……）

Posted on Edited on

题目大意

题目描述

给定 nn 个秘密单词组成的列表，以及一个目标文本 TT。
目标文本 TT 由小写英文字母和符号 ? 组成。其中 ? 是通配符，可以匹配秘密单词中的任意一个字母。
你需要求出有多少种方法，可以将整个文本 TT 完全拆分为列表中的单词。
每个单词可以使用任意多次。
输出方案数对 109+710^9 + 7 取模的结果。

输入格式

第一行包含一个整数 nn (1≤n≤1001 \le n \le 100)。
接下来 nn 行，每行一个字符串 WiW_i (1≤∣Wi∣≤101 \le |W_i| \le 10)，保证所有单词互不相同。
最后一行包含一个字符串 TT (1≤∣T∣≤1001 \le |T| \le 100)。

样例 1

1
2
3
4
5
6
7
8
9
7
a
b
c
d
ab
bc
cd
ab?d

输出 1

1
11

样例 1 解释

目标文本为 ab?d。? 可以匹配任意字符，即此处的 ? 需要根据选用的单词被“填充”。
可能的拆分方式包括：

  1. [a, b, a, d] （第三个单词为 a，此时 ? 匹配 a）

  2. [a, b, b, d] （? 匹配 b）

  3. [a, b, c, d] （? 匹配 c）

  4. [a, b, d, d] （? 匹配 d）

  5. [ab, a, d]

  6. [ab, b, d]

  7. [ab, c, d]

  8. [ab, d, d]

  9. [a, bc, d]

  10. [a, b, cd]

  11. [ab, cd]

样例 2

1
2
3
4
2
a
b
??

输出 2

1
4

样例 2 解释

目标文本为 ??。
可能的拆分方式包括：

  1. [a, a]

  2. [a, b]

  3. [b, a]

  4. [b, b]

思路讲解

采用线性 DP 的方式啊，采用线性 DP 的方式。

这题的陷阱就是啊，至少是我踩中的陷阱啊。就是采用了区间 DP 的方式，因为毕竟这个数据范围比较小嘛，很容易想到区间 DP 啊。不过区间 DP 它会，虽然说二叉分裂是不同的，但是划分方式是相同的，是会有这种情况的发生。

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
for (int i=0;i<N;++i) {
    for (int len=1;len<=10;++len) {
        if (i-len+1<0) {
            break;
        }
        // 一个 string view 啊，这个 view 就是从 i 减 len 加一开始，长度为 len 的一个 view。
        string_view s_view(s.data()+i-len+1,len);
        ll valid_num=0;
        // 这个循环就是计算 valid num 的数量。说白了就是长度为 len 的合法单一划分数量。
        for (auto &ls:len_words_mtx[len]) {
            bool ok=true;
            for (int j=0;j<SZ(ls);++j) {
                if (ls[j]==s_view[j] || s_view[j]=='?') {

                }else {
                    ok=false;
                }
            }
            if (ok) {
                 valid_num++;
            }
        }
        // 从 i - len 处转移，一共有 valid num 种转移方法，所以说是乘法原理。
     // 注意 i - len 为小于零的时候是空，也是 1 种合法的方案。
        dp[i]+=(i-len<0?1:dp[i-len])*valid_num;
        dp[i]%=mod;
    }
}

AC代码

AC

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

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