题解：P12537 [XJTUPC 2025] 罗斯飞鸽

· · 题解

出题人题解。

这个题出的时候没想过还能三维偏序。我们先考察 v = 1 的情况：将判定点画在 xOt 平面上，从某个判定点出发，能到达的点的范围在它的左上 45 度到右上 45 度之间。

如下：

这是第一组样例对应的情况，如果判定了 F 点，下一步可判定的就是 A,B,C 之一。

这个画图似乎对解题没有帮助？并不！我们把整个图片旋转 45 度：

所以，此时每个点能到达的下一个点，就是位于右上方的点。这是一个“二维偏序最长链问题”，如果将所有点按照新的横坐标排序，就是在求新的纵坐标的最长不下降子序列。

形式化地，新的坐标是 (t + x, t - x)。

不过，完整的题目要考虑 v。所以实际上，一个点能到达的点是一个 \pm \arctan(v) 的角度范围。以 v=2 为例：

此时，我们在进行旋转运算的同时，还要向 t 轴方向做一个伸缩变换。感性理解，这两个变换显然不会改变可达点集。

形式话地说，得到的新坐标是 (vt+x, vt-x)，然后跑最长不下降子序列就好了。

题解 pdf 里那个证明更严谨一点。

代码：

#include <bits/stdc++.h>
using namespace std;

const int MAXN(5e5 + 5);

struct Node {
    long long ta, tb;
};

int n;
long long v;
Node a[MAXN], len[MAXN];

bool operator<(Node x, Node y) {
    return x.ta != y.ta ? x.ta < y.ta : x.tb < y.tb;
}

bool compare(Node x, Node y) {
    return x.tb != y.tb ? x.tb < y.tb : x.ta < y.ta;
}

void solve() {
    scanf("%d %lld", &n, &v);
    for (int i = 1; i <= n; i++) {
        long long t, x;
        scanf("%lld %lld", &t, &x);
        a[i].ta = v * t + x;
        a[i].tb = v * t - x;
    }
    sort(a + 1, a + n + 1, compare);
    int ans = 0;
    len[0].ta = len[0].tb = LLONG_MIN;
    for (int i = 1; i <= n; i++) {
        int p = lower_bound(len, len + ans + 1, a[i]) - len;
        len[p] = a[i];
        if (p > ans) ans++;
    }
    printf("%d\n", ans);
}

int main() {
    int _;
    scanf("%d", &_);
    while (_--) {
        solve();
    }
    return 0;
}