Codeforces Round 1080 (Div. 3)（CF-1080）——F. Parabola Independence（寻找传递性）（寻找最长链使用记忆化 dfs）（边的数量也会影响记忆化 DFS 的时间复杂度）（小心二次函数的退化）

题目大意

题意

给定 $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

样例输出

1
2
3

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

样例解释（第一组数据）

给定的 4 个函数如下：

$f_1(x) = x^2 + 2x - 1$
$f_2(x) = -3x^2 - 3$
$f_3(x) = -x^2 + 4x - 5$
$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$ 成立。
这种关系在数学中也被称为严格偏序。
让我们构造一个有向图 $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 是求最短路径。

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 也不难，反正。

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 的小于号运算符出现了判断错误。

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

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

源代码

/**
 * 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

*/

Znzryb's Blog

Codeforces Round 1080 (Div. 3)（CF-1080）——F. Parabola Independence（寻找传递性）（寻找最长链使用记忆化 dfs）（边的数量也会影响记忆化 DFS 的时间复杂度）（小心二次函数的退化）

题目大意

思路讲解

AC代码

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