Codeforces Round 1080 (Div. 3)（CF-1080）——F. Parabola Independence（寻找传递性）（寻找最长链使用记忆化 dfs）（边的数量也会影响记忆化 DFS 的时间复杂度）（小心二次函数的退化） · znzryb
## 题目大意
**题意**
给定 $n$ 个二次函数 $F=\{f_1, f_2, \dots, f_n\}$，其中 $f_i(x) = a_i x^2 + b_i x + c_i$。
定义两个函数 $f$ 和 $g$ 是 **独立** 的，当且仅当对于所有的实数 $x \in \mathbb{R}$，都有 $f(x) \neq g(x)$（即两个函数的图像在平面上没有交点）。
定义一个函数集合 $G \subseteq F$ 是 **有序** 的，当且仅当 $G$ 中任意两个不同的函数都是独立的。
对于每一个 $i$ ($1 \le i \le n$)，请计算包含 $f_i$ 的最大有序子集的大小（即寻找一个最大的子集 $S \subseteq F$，使得 $f_i \in S$ 且 $S$ 是有序的，输出 $|S|$）。
**数据范围**
- $1 \le t \le 10^4$
- $1 \le n \le 3000$
- $-10^6 \le a_i, b_i, c_i \le 10^6, a_i \neq 0$
- 保证所有测试用例中 $n^2$ 的总和不超过 $3000^2$。
**输入格式**
第一行包含一个整数 $t$，表示测试用例的数量。
对于每个测试用例，第一行包含一个整数 $n$。
接下来的 $n$ 行，每行包含三个整数 $a_i, b_i, c_i$，描述第 $i$ 个二次函数。
**输出格式**
对于每个测试用例，输出一行 $n$ 个整数，第 $i$ 个整数表示包含 $f_i$ 的最大有序子集的大小。
**样例输入**
```
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
```
**样例输出**
```
3 2 3 3
3 3 2 2 3
3 3 3 1 2
```
**样例解释（第一组数据）**
给定的 4 个函数如下：
1. $f_1(x) = x^2 + 2x - 1$
1. $f_2(x) = -3x^2 - 3$
1. $f_3(x) = -x^2 + 4x - 5$
1. $f_4(x) = x^2 + 2x - 4$
各函数包含于其中的最大有序子集如下：
- 对于 $f_1$：集合 $\{f_1, f_3, f_4\}$ 是有序的（两两无交点），大小为 3。
- 对于 $f_2$：集合 $\{f_1, f_2\}$ 是有序的，大小为 2。
- 对于 $f_3$：集合 $\{f_1, f_3, f_4\}$ 是有序的，大小为 3。
- 对于 $f_4$：集合 $\{f_1, f_3, f_4\}$ 是有序的，大小为 3。
## 思路讲解
::: 官方题解（写的挺好的）
让我们考虑一个图$G$，其中$u\leftrightarrow v$是一条边，当且仅当$f_u$和$f_v$是独立的。那么，根据问题定义，一个有序子集是图$G$中的一个团（完全子图）。问题是，团问题众所周知是NP完全的。我们能否利用任何其他属性？
给定的函数是**连续**函数。也就是说，如果对于所有$x \in \mathbb{R}$，$f_i(x) \neq f_j(x)$，则以下任一条件成立：
- $f_i(x) \gt f_j(x)$对于所有$x \in \mathbb{R}$。
- $f_i(x) \lt f_j(x)$对于所有$x \in \mathbb{R}$。
让我们表示为$u \prec v$，如果对于所有$x \in \mathbb{R}$，$f_u(x) \lt f_v(x)$。我们将考虑该关系的独特属性。
- 关系$\prec$是传递的。也就是说，如果$a \prec b$和$b \prec c$，那么$a \prec c$。
- 如果$u \prec v$，那么显然$v \prec u$是不可能的。
- 不能存在任何$u$使得$u \prec u$成立。
这种关系在数学中也被称为[严格偏序](https://en.wikipedia.org/wiki/Partially_ordered_set#Strict_partial_orders)。
让我们构造一个有向图$D$，其中$u \to v$是一条边，当且仅当$u \prec v$。有序子集中的所有索引可以按$\prec$排序，因此大小为$k$的有序子集对应于$D$中$k$个顶点的路径。因此，现在我们将问题简化为$D$中的最长路径问题。
由于$\prec$的特性，图$D$不能有循环，这意味着图$D$是一个有向无环图（DAG）。正如我们已经知道的，DAG上的最长路径问题可以使用DP来解决。
让我们定义两个DP状态。$\mathtt{dp}_l[v]$定义为以$v$结尾的最长路径的长度（顶点数），$\mathtt{dp}_r[v]$定义为以$v$开始的最长路径的长度。那么包含顶点$v$的最长路径的长度恰好是$\mathtt{dp}_l[v]+\mathtt{dp}_r[v]-1$。我们可以在$\mathcal{O}(n^2)$时间内计算出$\mathtt{dp}_r[v]$和$\mathtt{dp}_r[v]$，问题得以解决。
:::
::: 错误的使用了 bfs 求解最长链
不应该使用这个 BFS，无论你怎么样 BFS 它都不太能够求解这个最长的问题，因为毕竟 BFS 是求最短路径。
```cpp
auto solve=[&](vector<ll> &mx_chain,const vector<vector<ll>> &g) -> void {
for (int i=1;i<=N;++i) {
queue<pair<ll,ll>> q;
vector<char> vis(N+2);
vis[i]=true;
q.push({i,0});
ll ans=0;
while (!q.empty()) {
auto [u,dis]=q.front();
q.pop();
ans=max(ans,dis);
for (auto to:g[u]) {
if (vis[to]) continue;
vis[to]=1;
q.push({to,dis+1});
}
}
mx_chain[i]=ans;
}
};
```
:::
2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025) 2025 英国 ICPC——J. Joust Sort（拓扑排序解决依赖排序问题）
那么我们实际上可以使用记忆化的 DFS 去解决这个问题。
实际上来说呢，如果这个图它是一个完全图，它没有任何其他的性质的话，实际上是一个 NP 问题，也就是团问题。因此呢，实际上这个关系之间具有严格偏序关系。因此这个图实际上是一个 DAG。我们是就是要在一个 DAG 上去求包含该节点的一个最长链。
那么其实不难想到，这个是真不难想到，就是你去求包含一个节点的最长链的话，直接去求是比较困难的。你可以求，先求以这个点为起点的最长链（长度），再去求以这个点为终点的最长链（长度）。
不过其实求以这个点为终点的最长链的长度，你可能会说，哎，我不会求啊，这个怎么求？哎，实际上很简单，你就**把图所有的边全部反向**，然后再用跑，这个求以这个点为起点的最长链长度再跑一遍就好了。
实际上来说，这个东西，这个记忆化 DFS 能跑，也是因为这张图具有 DAG 性质。你实在不放心，也可以用拓扑排序去跑一个 DP 也不难，反正。
```cpp
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);
```
::: \*\*遗漏了这个做差式二次函数退化的情况\*\*，导致这个 Q U A D 的小于号运算符出现了判断错误。
```cpp
struct Quad {
ll a,b,c;
bool operator< (const Quad &o) const {
ll a1=a-o.a,b1=b-o.b,c1=c-o.c;
// 这个 B 方减4AC 这个判别式只能应用于二次函数。虽然这看起来是一句废话，
// 但如果说 a1 等于0的时候，是不能够用这个判别式判判断是否有解的。
if (b1*b1-4*a1*c1>=0) return false;
return c<o.c;
}
};
```
:::
::: TLE ，注意⚠️，边的数量也会影响记忆化 DFS 的时间复杂度
[https://codeforces.com/contest/2195/submission/363305041](https://codeforces.com/contest/2195/submission/363305041)
```cpp
auto solve=[&](vector<ll> &mx_chain,const vector<vector<ll>> &g) -> void {
// 以 i 为根的，为链的起点的，记忆化 dfs 数组
vector<ll> dp(N+2);
vector<char> vis(N+2);
// O(V+E) 因为 E 是 O(n^2)，因此总的级别是 O(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) {
dp.assign(N+2,0);
vis.assign(N+2,0);
dfs(dfs,i);
mx_chain[i]=dp[i];
}
};
```
其实 TLE 的原因很简单，就是 DFS 实际上是 $O(V + E) = O(N^2)$，DFS 实际上是 ON 方的。那么我们跑了 N 遍 DFS，跑了 N 遍记忆化 DFS，那么实际上是 $O(N^3)$。DFS 还是不要去忽略这个边的影响。
样例全部正确。总结一下这个 TLE 的原因：
你的代码本身确实是记忆化搜索，**单次 DFS 是** $O(V + E) = O(N^2)$。但问题在于你在 `for` 循环里面每轮都 `dp.assign(N+2,0)` 和 `vis.assign(N+2,0)`，把之前所有记忆化结果全部清空了。这导致：
- 第 1 次从节点 1 出发做 DFS，算完所有可达节点的 dp 值
- 第 2 次**清空**，从节点 2 重新算一遍
- 第 3 次**清空**，从节点 3 重新算一遍
- ……共 $N$ 次，每次 $O(N^2)$，总共 $O(N^3)$
修复只需要把这两行初始化移到循环外面。这样第一个 `dfs(dfs,1)` 可能就把大部分节点的 dp 都算好了，后续的 `dfs(dfs,i)` 碰到已访问节点直接返回，总复杂度降为 $O(N^2)$。
- 原始文件：`src/F_Parabola_Independence.cpp`（未改动）
- 调试副本：`src/F_Parabola_Independence.debug2.cpp`
- 临时编译产物：`/tmp/cursor-algo-debug/`
:::
## AC代码
AC
[https://codeforces.com/contest/2195/submission/363306906](https://codeforces.com/contest/2195/submission/363306906)
::: 源代码
```cpp
/**
* Problem: F. Parabola Independence
* Contest: Codeforces Round 1080 (Div. 3)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2195/problem/F
* Created: 2026-02-16 00:44:38
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define debug3d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " [\n"; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
{ \
cerr << " ["; \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k]; \
cerr << "]\n"; \
} \
cerr << " ]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
struct Quad {
ll a,b,c;
bool operator< (const Quad &o) const {
ll a1=a-o.a,b1=b-o.b,c1=c-o.c;
// 是一个非常容易漏掉的情况，就是当 a1 为0的时候，做差式二次函数退化了，不能够使用下面的二次判别式。
if (a1==0) {
if (b1!=0) return false;
return c<o.c;
}
if (b1*b1-4*a1*c1>=0) return false;
// 上面相当于都是在判是否相交，相交，我们认为是等于情况，返回 false。。
return c<o.c;
}
};
void Solve() {
ll N;
cin >> N;
vector<Quad> A(N+2);
for (int i=1;i<=N;++i) {
cin>>A[i].a>>A[i].b>>A[i].c;
}
// 我们的思路是什么呢？我们思路就是首先我们给这个 Quad 整了一个这个小于号运算符。
vector<vector<ll>> org_g(N+2),rev_g(N+2);
for (int i=1;i<=N;++i) {
for (int j=1;j<=N;++j) {
if (i==j) continue;
if (A[i]<A[j]) {
// 建一张图，再建一张版图。
org_g[j].push_back(i);
rev_g[i].push_back(j);
}
}
}
// 正图和反图的一个 主要就是计算一个最长链。
vector<ll> mx_chain1(N+2),mx_chain2(N+2);
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);
for (int i=1;i<=N;++i) {
ll ans=mx_chain1[i]+mx_chain2[i]-1;
cout<<ans<<" ";
}
cout<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2195/submission/363306906
*/
```
:::
## 心路历程（WA，TLE，MLE……）