CF2129A Double Perspective

给定一组区间对 $S = \{(a_1, b_1), (a_2, b_2), \ldots, (a_m, b_m)\}$，其中对于所有 $1 \le i \le m$，都有 $a_i < b_i$，我们定义 $f(S)$ 和 $g(S)$ 如下： - 将每个 $(a_i, b_i)$ 视为数轴上的一个区间，$f(S)$ 表示这些区间的并的长度。形式化地说，$f(S)$ 是满足存在某个 $i$（$1 \leq i \leq m$）使得 $[x, x+1] \subseteq [a_i, b_i]$ 的整数 $x$ 的个数。 - 将每个 $(a_i, b_i)$ 视为图中的一条无向边，$g(S)$ 表示在至少包含 $3$ 条边的简单环上的点的个数。形式化地说，$g(S)$ 是满足存在一条路径 $x_1 \to x_2 \to \ldots \to x_k \to x_1$（$k \geq 3$，且 $x_1, x_2, \ldots, x_k$ 两两不同）的点 $x_1$ 的个数。 例如，$S = \{(1,2), (2,4), (1,4), (4,5),(6,7)\}$，可以得到 $f(S) = 5$，$g(S) = 3$。 现在给定 $n$ 个不同的区间对。你的任务是从中选择一个子集 $S'$，使得 $f(S') - g(S')$ 最大。你需要输出被选中的区间对的下标。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的组数。 每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^3$）。 接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i < b_i \le 2n$），表示一个区间对。 保证同一测试用例内所有区间对均不同。 保证所有测试用例的 $n^2$ 之和不超过 $9 \cdot 10^6$。

对于每组测试用例，第一行输出一个整数 $k$（$0 \le k \le n$），表示选中的区间对的数量。 下一行输出 $k$ 个不同的整数 $i_1, i_2, \ldots, i_k$（$1 \le i_1, i_2, \ldots, i_k \le n$），表示被选中的区间对的下标。注意下标不能重复。

在第一个测试用例中，如果不选任何区间对（即 $S'=\varnothing$），则 $f(S')-g(S')=0-0=0$。如果只选第一个区间对，则 $f(S')-g(S')=1-0=1$。因此最优解是只选第一个区间对。 由 ChatGPT 4.1 翻译