题解：P8695 [蓝桥杯 2019 国 AC] 轨道炮

andrew_201 · 2026-08-05 20:28:55 · 题解

题目传送门

题目大意

在二维平面上有 N 个敌方单位，每个单位从初始坐标（X_i,Y_i）出发，沿上下左右四个方向之一以速度 V_i 做匀速直线运动。你可以在任意一个非负整数时刻发射一次轨道炮，炮弹会消灭一条平行于坐标轴（水平或竖直）的直线上的所有敌方单位。请计算一次发射最多能消灭多少个敌方单位。

解题思路

第一步先把问题拆开：水平炮（打同一 y 值的水平线）和竖直炮（打同一 x 值的竖直线）是完全独立的两件事，分开算各自的最大值，最后取更大的结果就行，不用混在一起考虑。

先单独想水平方向的情况：每个敌人的 y 坐标随时间变化的公式很好写，就是 y = 速度 \times t + 初始 y。往上走速度取正，往下走速度取负，左右移动的敌人 y 坐标不变，速度就是 0。现在问题就转化成了：找一个非负整数 t，让最多的敌人 y 值相等。

最开始我先想直接枚举所有 t，但马上就反应过来不行，那就是 t 没有明确上限，坐标和速度都是百万级，总不能无限枚举下去。于是我换了个思路：什么时候会有多个敌人刚好在同一条水平线上？肯定是两两相遇的时刻。也就是说，所有可能打出高命中数的时刻，一定是某两个敌人刚好走到同一 y 坐标的时刻，不会平白无故出现大量敌人共线的情况。

这样一来候选时刻就有限了，最多就是每对敌人对应一个时刻，N = 1000 的话也就 100 万对，计算量完全扛得住。

接下来逻辑就顺了，固定一个敌人 i，挨个看其他敌人 j：

• 如果两者速度相同：初始 y 也一样的话，那这俩永远在同一水平线上，不管什么时候开炮都算在一起，先把这种 “永久共线” 的数量记下来；初始 y 不一样的话，永远碰不到，直接跳过。

• 如果速度不同：列方程求两者 y 相等的时刻，也就是 vy_i \times t + y0_i = vy_j \times t + y0_j，整理得 t = (y0_j - y0_i) / (vy_i - vy_j)。这时候要卡两个条件：一是必须能整除，保证 t 是整数；二是算出来的 t 必须 \ge 0，毕竟时间不能是负数。满足条件的话，就给这个时刻 t 记一次数，说明这个时刻 i 和 j 也会共线。

遍历完所有 j 之后，对于敌人 i 来说，基础命中数是永久共线的个数，再加上每个 t 时刻额外凑过来的敌人数量，就是这个时刻的总命中数。取其中最大的，就是以 i 为基准的最优解。

把所有敌人都当作基准算一遍，得到的最大值就是水平方向的答案。竖直方向是完全一样的逻辑，把 y 坐标换成 x 坐标、速度换成 x 方向的速度就行。

最后把水平和竖直两个方向的最大值取个 \max，就是最终答案。

另外要注意所有计算都要用 long long，坐标和速度的数值都不小，差值、乘积很容易爆 int，这点必须留意。

::::success[AC code]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1005;
int n;
ll x[MAXN],y[MAXN];
ll x2[MAXN],y2[MAXN];
int sp()
{
    int ans=1;
    for(int i=0;i<n;i++)
    {
        vector<ll> tim;
        int same=1;
        for(int j=0;j<n;j++)
        {
            if(i==j)
            {
                continue;
            }
            ll dy=y2[i]-y2[j];
            ll dy2=y[j]-y[i];
            if(dy==0)
            {
                if(dy2==0)
                {
                    same++;
                }
                continue;
            }
            if(dy2%dy!=0)
            {
                continue;
            }
            ll t=dy2/dy;
            if(t>=0)
            {
                tim.push_back(t);
            }
        }
        ans=max(ans,same);
        sort(tim.begin(),tim.end());
        if(!tim.empty())
        {
            int cnt=1;
            ans=max(ans,same+cnt);
            for(int k=1;k<tim.size();k++)
            {
                if(tim[k]==tim[k-1])
                {
                    cnt++;
                }
                else
                {
                    cnt=1;
                }
                ans=max(ans,same+cnt);
            }
        }
    }
    return ans;
}
int sz()
{
    int ans=1;
    for(int i=0;i<n;i++)
    {
        vector<ll> tim;
        int same=1;
        for(int j=0;j<n;j++)
        {
            if(i==j)
            {
                continue;
            }
            ll dx=x2[i]-x2[j];
            ll dx2=x[j]-x[i];
            if(dx==0)
            {
                if(dx2==0)
                {
                    same++;
                }
                continue;
            }
            if(dx2%dx!=0)
            {
                continue;
            }
            ll t=dx2/dx;
            if(t>=0)
            {
                tim.push_back(t);
            }
        }
        ans=max(ans,same);
        sort(tim.begin(),tim.end());
        if(!tim.empty())
        {
            int cnt=1;
            ans=max(ans,same+cnt);
            for(int k=1;k<tim.size();k++)
            {
                if(tim[k]==tim[k-1])
                {
                    cnt++;
                }
                else
                {
                    cnt=1;
                }
                ans=max(ans,same+cnt);
            }
        }
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        ll x1,y1,v;
        char dir;
        cin>>x1>>y1>>v>>dir;
        x[i]=x1;
        y[i]=y1;
        x2[i]=0;
        y2[i]=0;
        if(dir=='U')
        {
            y2[i]=v;
        }
        else if(dir=='D')
        {
            y2[i]=-v;
        }
        else if(dir=='R')
        {
            x2[i]=v;
        }
        else if(dir=='L')
        {
            x2[i]=-v;
        }
    }
    int yy=sp();
    int xx=sz();
    cout<<max(yy,xx)<<endl;
    return 0;
}

::::

有人可能会问我直接把两个函数封装在一个函数里面不香吗？实际上是我懒得做。

AC 记录

给个赞再走呗~~

完结撒花~~

本文章使用豆包 AI 大模型进行文章润色，且保证笔者的贡献大于 AI。