今早 CF F 题解
2026-02-16 09:27:32
发布于：浙江
A-E 的题解应该 trq 都会写掉，我感觉 F 特别好玩所以专门写了 F 的题解。
Codeforces Round 1080 (Div. 3) F 题解
谁懂作为一个只懂一点图论皮毛其它一窍不通的人来说，发现具备传递性后首先想到了建图的救赎感。
题目分析
这题其实大可以分为两部分做，一部分数学，一部分图论，两者似乎并不相干。说句闲话，我并不是很理解为何出题人要把数学性这么强的东西放在一道 OI 题里，也没有做一个特殊说明，或许是因为出题人觉得二次函数太简单了大家都会（？）
Part.1 数学
首先我们要考虑怎么从代数的角度去判断两个二次函数有没有交点。
对于两个二次函数 ，若函数 无实根，则两个二次函数无交点。
这个其实很好想。
两个二次函数存在交点意味着必然存在一个实数 ，使得 ，移项一下，就可以得到 ，也就是只要这个方程有实根，两个二次函数就存在交点。
反之可得无交点的情况。
::::
知道两个函数无交点后还要再想到一个性质（似乎不能说是性质），就是两个函数既然无交点，就必然存在严格大于/严格小于的关系。
这个真的很好证，读者完全可以自己思考。
这么看感觉数学部分也不是很难。
Part.2 图论
既然有严格大于/严格小于的关系，那就可以建图了。我们对所有严格大于的关系建一条有向边，很显然这个是具备传递性的，且建出的图一定是一张 DAG。
建好之后，试想如果我们从图中任意挑出一个链（假设上面的元素分别是 ），它们必然是“有序”（我不确定大家的翻译给的是不是这个，原文是 organized），因为链中的所有元素都保持着严格大于的关系，都不可能存在交点。
然后就很简单了，对于每一个 ，我们只需要找出经过它的最长链的长度即可。
我一直以为这个应该有一个原题的，但找了 5min 没找到。唯一最像的就是 P1137。P1137 是以该点为终点的最长路径长度，而我们要求的是经过该点的最长链长度，也就是分别以该点为起点，终点的最长路径长度和减一（减去自身重复）。
终点会求了起点建一个反图也可以求。
一些坑点
- 判断两个函数有无交点时，算出 函数解析式后不可以直接代 判别式，一定要先讨论二次项系数。
- 不可以直接用并查集来维护两个函数是否有交点，因为这个并不具备传递性。
多测要清空。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 10;
int T, n, a[maxn], b[maxn], c[maxn];
vector<int> out[maxn], in[maxn];
int dp_out[maxn], dp_in[maxn];
int dfs_out(int u) {
if (dp_out[u] != -1) return dp_out[u];
int res = 1;
for (int v : out[u]) res = max(res, 1 + dfs_out(v));
return dp_out[u] = res;
}
int dfs_in(int u) {
if (dp_in[u] != -1) return dp_in[u];
int res = 1;
for (int v : in[u]) res = max(res, 1 + dfs_in(v));
return dp_in[u] = res;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i] >> c[i];
out[i].clear(), in[i].clear();
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
int da = a[j] - a[i], db = b[j] - b[i], dc = c[j] - c[i];
if (da != 0) {//一定别忘记
int disc = db * db - 4LL * da * dc;
if (disc < 0) {
if (da > 0) {
out[i].push_back(j);
in[j].push_back(i);
} else {
out[j].push_back(i);
in[i].push_back(j);
}
}
} else if (db == 0) {
if (dc > 0) {
out[i].push_back(j);
in[j].push_back(i);
} else if (dc < 0) {
out[j].push_back(i);
in[i].push_back(j);
}
}
}
}
for (int i = 1; i <= n; i++) dp_out[i] = dp_in[i] = -1;
for (int i = 1; i <= n; i++) {
if (dp_out[i] == -1) dfs_out(i);
if (dp_in[i] == -1) dfs_in(i);
}//算出分别作为起点/重点的最长路径长度
for (int i = 1; i <= n; i++) cout << dp_in[i] + dp_out[i] - 1 << " \n"[i == n];
}
return 0;
}
全部评论 3
支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持支持
4天前 来自 北京
0
有帮助，赞一个