P8777 [蓝桥杯 2022 省 A] 扫描游戏 题解

· · 题解

题目传送门

题目简意

输出被顺时针旋转的棒碰到的排名顺序。

分析

首先我们需要知道棒被碰到的顺序与什么有关，显然，和该点与原点连线与 x 轴夹角 \theta 有关。仔细思考我们就会发现如果只考虑转一圈，那么 \theta 从 \frac{\pi}{2} 减小到 -\frac{3\pi}{2}，这里我没有直接求解角度，因为容易发现这正好是 \tan\theta 的两个周期，而由于 \tan\theta 在每个周期内都是增函数，故可以考虑将一个整圈拆成两个半圈，即 \theta 从 \frac{\pi}{2} 减小到 -\frac{\pi}{2} 和从 -\frac{\pi}{2} 减小到 -\frac{3\pi}{2} 这两个阶段，并且每个阶段 \tan\theta 都随着 \theta 的减小而减小，这里为了方便记 y 轴上的点 \tan\theta=\infty。其次我们需要求出每个点到原点的距离 d，因为只有当棒的长度大于等于 d 的时候该点才可能被扫到。

那么如何判断两个点的排名是否相同呢？当且仅当这两个点所对应的 \theta 相等且在同一圈被扫到时排名才可能相同。而当一个点不能被扫到，那么与该点 \theta 相同且 d 更大的点一定在此圈中无法被扫到。故我们可以开一个结构体，求出每个点的 \theta 和 d。以 \theta 为第一关键词降序，d 为第二关键词升序。然后按顺序遍历每个点，若能扫到则记录排名否则跳过。

几点注意事项：

一、数据量很大建议使用 long long 或者 double 存储。

二、对于每一个不同的 \theta 才修改排名，否则如果能扫到视为排名相同，具体请见代码。

三、因为遍历的是两个周期的 \theta，故判断 \theta 是否被遍历过的数组一定要每周期清空一次（我才不会告诉你我是因为这个卡了十几次 90分）。

最终程序时间复杂度为 O(kn)，其中 k 为转圈圈数。

本代码还跑到了全洛谷最优解哈哈哈。

Record

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
int n,tot,ans[N],ttt;//tot表示遍历到的顺序（即不包括重复的），ttt表示排名（即包括重复的），两者有一定的差异，请读者在后面的代码自行体会
int cnt1,cnt2;
double l,x,y,z;
unordered_map<double,bool> vis;//记录每个theta是否被访问过
bool ok;

struct node{
    int id;
    double rad,r,z;
};//id表示这个点的编号，r即为d，rad即为tan theta，z同题目

bool cmp(node x,node y)
{
    if(x.rad==y.rad) return x.r<y.r;
    return x.rad>y.rad;
}//排序时关键词一定要看好

node zheng[N],fu[N];//分成两个半圆

signed main()
{
    memset(ans,-1,sizeof(ans));
    scanf("%d%lf",&n,&l);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf%lf",&x,&y,&z);
        if(x==0&&y==0)
        {
            ans[i]=1;
            l+=z;
            tot++;
        }//对于在原点的点特判
        if(x==0)//特判y轴
        {
            if(y>0)
            {
                zheng[++cnt1].id=i;
                zheng[cnt1].r=(double)sqrt(x*x+y*y);
                zheng[cnt1].rad=1e20;//赋为无穷大
                zheng[cnt1].z=(double)z;
            }
            else
            {
                fu[++cnt2].id=i;
                fu[cnt2].r=(double)sqrt(x*x+y*y);
                fu[cnt2].rad=1e20;
                fu[cnt2].z=(double)z;
            }
        }
        else if(x>0)
        {
            zheng[++cnt1].id=i;
            zheng[cnt1].r=(double)sqrt(x*x+y*y);
            zheng[cnt1].rad=(double)y/x;
            zheng[cnt1].z=(double)z;
        }
        else
        {
            fu[++cnt2].id=i;
            fu[cnt2].r=(double)sqrt(x*x+y*y);
            fu[cnt2].rad=(double)y/x;
            fu[cnt2].z=(double)z;
        }
    }
    sort(zheng+1,zheng+cnt1+1,cmp);
    sort(fu+1,fu+cnt2+1,cmp);
    while(1)//模拟转圈过程
    {
        ok=0;
        vis.clear();
        for(int i=1;i<=cnt1;i++)
        {
            if(ans[zheng[i].id]!=-1) continue;//已经遍历过
            if(l<zheng[i].r) continue;//扫不到
            if(!vis[zheng[i].rad])
            {
                vis[zheng[i].rad]=1;
                ttt=tot+1;//新的theta才更新排名
            }
            ans[zheng[i].id]=ttt;
            l+=zheng[i].z;
            tot++;
            ok=1;
        }
        vis.clear();//这个真的真的真的真的很重要！！！
        for(int i=1;i<=cnt2;i++)//同上
        {
            if(ans[fu[i].id]!=-1) continue;
            if(l<fu[i].r) continue;
            if(!vis[fu[i].rad])
            {
                vis[fu[i].rad]=1;
                ttt=tot+1;
            }
            ans[fu[i].id]=ttt;
            l+=fu[i].z;
            tot++;
            ok=1;
        }
        if(ok==0) break;//没有任何点被修改则跳出循环
    }
    for(int i=1;i<=n;i++) printf("%d ",ans[i]);
    printf("\n");
    return 0;
}

一件有趣的事：之前不小心把其中的一个 cnt1 写成 cnt2 了，居然也是 90 分。数据水啦！