专栏文章

P12537 [XJTUPC 2025] 罗斯飞鸽 题解

aawapwq233
P12537题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip8gaz4
此快照首次捕获于
2025/12/03 07:52
3 个月前
此快照最后确认于
2025/12/03 07:52
3 个月前
查看原文

P12537 [XJTUPC 2025] 罗斯飞鸽 题解

是的，我就是题面里的 awa。
你的意思是，我作为选手，在赛场上做到了以自己为背景的题？还在玩 Phigros？
出题人 @ShwStone 我喜欢你。
题意：给定 nn 个点 (xi,ti)(x_i,t_i) 和 vv，选取 kk 个点，使这些点内任意两个点满足 ∣xi−xj∣≤v∣ti−tj∣\left|x_i-x_j\right|\leq v \left|t_i-t_j\right|。要求最大化 kk 的值。n≤5×105,0≤v,ti,∣xi∣≤109n\leq 5\times 10^5, 0\leq v,t_i,\left|x_i\right|\leq 10^9。
朴素 dp 是显然的，fi=max⁡ti>tj;∣xi−xj∣≤v(ti−tj){fj}+1f_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(n2)O(n^2)，考虑优化。
可以尝试把这 nn 个点 (xi,ti)(x_i,t_i) 画在平面直角坐标系上。
容易发现，能转移到当前点的节点都在过当前点的斜率为 ±v\pm v 的两条直线围成的区域下方。我们是否能对于每个点找到它的范围内的最大 fjf_j 呢？
考虑 fjf_j 可以转移到 fif_i，有
{xi−xj≤v(ti−tj)⟹xi−vti≤xj−vtj(xi≥xj)xj−xi≤v(ti−tj)⟹xi+vti≥xj+vtj(xi<xj)\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)(-2,2) 或者 (3,3)(3,3) 的点会被选到），而这个需要两边同时满足，所以寄了。
诶！但是我们灵机一动，可以把 xix_i 与 xjx_j 的大小关系分开讨论，然后再用一维数据结构套上去不就可以维护了吗！
但是因为我犯唐了，没时间写完树套树了，只能遗憾离场。
时间复杂度 O(nlog⁡2n)O(n\log^2 n)。卡常。
但是你发现你维护两个这个东西不如直接维护 xi−vtix_i-vt_i 和 xi+vtix_i+vt_i 啊！这样就一次查询就行了。同样的，时间复杂度 O(nlog⁡2n)O(n\log^2 n)。卡常。
但是你又发现，按 tt 转移不如按 xi−vtix_i-vt_i 转移啊！因为满足转移条件的这部分点（见上图）一定满足 tj<tit_j<t_i，也就是说 tt 这个维度是无意义的，于是我们可以在对 xi−vtix_i-vt_i 排序的情况下仅对 xi+vtix_i+vt_i 做限制即可。
考虑 xi+vtix_i+vt_i 特别大，离散化后在线段树上统计答案即可。时间复杂度 O(nlog⁡n)O(n\log n)。
CPP
#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 值的贡献都是 11。这也是出题人正解的写法，就不放代码了。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...