P12537 [XJTUPC 2025] 罗斯飞鸽题解

awapwq233 · 2025-05-21 21:25:16 · 题解

P12537 [XJTUPC 2025] 罗斯飞鸽题解

是的，我就是题面里的 awa。

你的意思是，我作为选手，在赛场上做到了以自己为背景的题？还在玩 Phigros？

出题人 @ShwStone 我喜欢你。

朴素 dp 是显然的，f_i=\max\limits_{t_i>t_j;\left|x_i-x_j\right|\leq v \left(t_i-t_j\right)} \left\{f_j\right\} + 1。时间复杂度 O(n^2)，考虑优化。

可以尝试把这 n 个点 (x_i,t_i) 画在平面直角坐标系上。

容易发现，能转移到当前点的节点都在过当前点的斜率为 \pm v 的两条直线围成的区域下方。我们是否能对于每个点找到它的范围内的最大 f_j 呢？

考虑 f_j 可以转移到 f_i，有

\begin{cases}x_i-x_j\leq v(t_i-t_j)\Longrightarrow x_i-vt_i\leq x_j-vt_j &(x_i\geq x_j)\\x_j-x_i\leq v(t_i-t_j)\Longrightarrow x_i+vt_i\geq x_j+vt_j &(x_i< x_j)\end{cases}

于是，我们在赛场上就真的分别写了两颗线段树来维护最大值。

然后发现假了。因为在第一棵树上的只能保证一边满足条件（例如上图 (-2,2) 或者 (3,3) 的点会被选到），而这个需要两边同时满足，所以寄了。

诶！但是我们灵机一动，可以把 x_i 与 x_j 的大小关系分开讨论，然后再用一维数据结构套上去不就可以维护了吗！

但是因为我犯唐了，没时间写完树套树了，只能遗憾离场。

时间复杂度 O(n\log^2 n)。卡常。

但是你发现你维护两个这个东西不如直接维护 x_i-vt_i 和 x_i+vt_i 啊！这样就一次查询就行了。同样的，时间复杂度 O(n\log^2 n)。卡常。

但是你又发现，按 t 转移不如按 x_i-vt_i 转移啊！因为满足转移条件的这部分点（见上图）一定满足 t_j<t_i，也就是说 t 这个维度是无意义的，于是我们可以在对 x_i-vt_i 排序的情况下仅对 x_i+vt_i 做限制即可。

考虑 x_i+vt_i 特别大，离散化后在线段树上统计答案即可。时间复杂度 O(n\log n)。

#define int ll
typedef long long ll;
typedef pair<int, int> pii;

int n, v;
const int maxn = 5e5 + 10;
pii a[maxn];

int v1(pii &p) {return p.first - v * p.second;}
int v2(pii &p) {return p.first + v * p.second;}

bool cmp1(pii &x, pii &y) {return v1(x) == v1(y) ? v2(x) < v2(y) : v1(x) > v1(y);}
bool cmp2(pii &x, pii &y) {return v2(x) == v2(y) ? v1(x) < v1(y) : v2(x) < v2(y);}

// 代码省略了线段树的部分。

signed main()
{
    int T;
    cin >> T;
    while(T --)
    {
        cin >> n >> v;
        F(i, 1, n)
            cin >> a[i].second >> a[i].first;
        sort(a + 1, a + n + 1, cmp2);
        map<int, int> mp;
        F(i, 1, n)
            mp[v2(a[i])] = i;
        int ans = 0;
        sort(a + 1, a + n + 1, cmp1);
        Tr.clear(1, n, 1);
        F(i, 1, n)
        {
            int f = Tr.query(1, n, 1, 0, mp[v2(a[i])]) + 1;
            ans = max(ans, f);
            Tr.update(1, n, 1, mp[v2(a[i])], f);
        }
        cout << ans << endl;
    }
    return 0;
}

其实还可以转化为 最长不下降子序列，因为其本质就是找到这样一个不下降序列，每个点对 dp 值的贡献都是 1。这也是出题人正解的写法，就不放代码了。

P12537 [XJTUPC 2025] 罗斯飞鸽 题解