P5819 【L&K R-03】音游大计算 题解

KobeBeanBryantCox · 2025-02-24 15:43:21 · 题解

P5819 【L&K R-03】音游大计算 题解

题目传送门。

大常数选手前来报到，实测不开 O2 TLE 4 个点并且我卡不过去了，开了能 AC。

代码不算长，4k 以内，用了很多很长的变量名和函数名，改短了的话估计能 3k 以内。

为调试方便，我封装了很多东西。

题意

你要实现一个类似 phigros 的评判机制。

但是按键大小不统一、判定线不会移动、只有 note 键、且玩家不会读谱只会背谱。

鉴定为音游玩多了导致的。

具体看题目描述。

思路

不难看出线段树。

第一步：辅助内容

constexpr int none=0,miss=1,good=2,perfect=3;

表示 key 的评判状态。

struct Key
{
    int t,l,r,judgetime,state; // 到达判定线的时间，左右端点，被评判的时间，评判状态
    bool operator<(const Key &a)const{return t<a.t;} // 排序用的
}key[N];

封装 key。

struct Click
{
    int t,pos; // 点击的时间和位置
    bool operator<(const Click &a)const{return t<a.t;} // 排序用的
}click[N];

封装每一次点击。

struct Discretizing
{
    vector<int>a;
    inline void put(int v){a.push_back(v);} // 插入 v
    inline void init() // 离散化
    {
        sort(a.begin(),a.end());
        a.erase(unique(a.begin(),a.end()),a.end());
    }
    inline int get(int v){return lower_bound(a.begin(),a.end(),v)-a.begin()+1;} // 得到离散化后的值
}pos;

封装离散化（通常不会封装离散化，但是这个题太恶心了，我不想把代码写得很乱）。

第二步：读入及初始化

inline void init(int n,int m)
{
    for(int i=1;i<=n;i++)
    {
        double t,l,r;cin>>t>>l>>r;
        t=t*1e5+0.5,l=l*1e5+0.5,r=r*1e5+0.5; // 转成整数避免精度误差
        key[i]={t,l,r};
        pos.put(l),pos.put(r); // 放入离散化数组中
    }
    for(int i=1;i<=m;i++)
    {
        double t,p;cin>>t>>p;
        t=t*1e5+0.5,p=p*1e5+0.5; // 转成整数避免精度误差
        click[i]={t,p};
        pos.put(p); // 放入离散化数组中
    }
}
--------------
主函数内：
    int n,m;cin>>n>>m;
    init(n,m);
    sort(key+1,key+n+1),sort(click+1,click+m+1); // 按时间排序
    pos.init(),T.build(1,1,pos.a.size()); // 离散化和构建线段树
    for(int i=1;i<=n;i++)key[i].l=pos.get(key[i].l),key[i].r=pos.get(key[i].r);
    for(int i=1;i<=m;i++)click[i].pos=pos.get(click[i].pos); // 取出离散化后的值

第三步：构建线段树及插入所有 key

judge 函数内：
    for(int i=1;i<=n;i++)
    {
        int l=key[i].l,r=key[i].r;
        T.addkey(1,l,r,i);
    }

以上是插入所有 key。

接下来是线段树的构建。

因为一个区间可能有多个 key，所以每个区间维护一个队列（其他题解说的都是链表，但我觉得队列会合适一点）。

注意到这样并不会消耗很多空间，因为一个区间最多覆盖线段树上 \log 个节点，每个节点的队列长度总和是 n\log 的。

struct Seg 内：
    struct node
    {
        int l,r;
        list<int>keyid; // 开 queue 或者手写 queue 都会 MLE，原因放本文最后
        #define push push_back
        #define pop pop_front // 刚开始我写的是 queue MLE 了，后面改成 list 其他的不想改了就 define 一下
        inline void push(int id){keyid.push(id);}
    }tr[(3*N)<<2]; // 3*N 是因为离散化后最多有 2n+m 个点
    #define lc (x<<1)
    #define rc (x<<1|1)
    void build(int x,int l,int r) // 其实没什么用，主要就是求出 tr[x].l 和 tr[x].r，如果写法不一样，可以把 build 删了
    {
        tr[x].l=l,tr[x].r=r;
        if(l==r)return;
        int mid=(l+r)>>1;
        build(lc,l,mid),build(rc,mid+1,r);
    }
    void addkey(int x,const int l,const int r,const int id)
    {
        if(tr[x].l>=l&&tr[x].r<=r)return tr[x].push(id),void(); // 在区间插入编号为 id 的 key
        int mid=(tr[x].l+tr[x].r)>>1;
        if(l<=mid)addkey(lc,l,r,id);
        if(r>mid)addkey(rc,l,r,id);
    }

第四步：判定

judge 函数内：
    for(int i=1;i<=m;i++)
    {
        int p=click[i].pos,t=T.querytime(1,p,click[i].t); // 查询下一个将在当前点击产生判定的 key 的接触判定线的时间
        if(t!=inf)T.change(1,p,t,click[i].t); // 对接触判定线的时间为 t 的 key 进行评判，如果 t=inf，说明这次点击是一次无效点击
    }

以上是对每一个点击所对应的 key 进行判定。

为什么不找到了直接判定，而是要写两个函数呢？

因为题目说了相同时间接触判定线的 key 同时产生判定，这样做刚刚好可以实现。

线段树内的函数是这样的（有点长，慢慢看）：

struct Seg 内：
    struct node
    {
        已省去上文讲过的
        inline void pop(int t) // 这个用处是把超过评判时间的和已经评判过的弹出队列
        {
            while(!keyid.empty())
            {
                int id=keyid.front();
                if(key[id].state!=none){keyid.pop();continue;} // 代表评判过了
                // 上一行要写的原因是：当前 id 可能在其他线段树上的节点被评判过了
                if(key[id].t+60000>t)break;
                key[id].judgetime=key[id].t+60000;
                key[id].state=miss; // 产生 miss 判定并且修改判定时间为接触判定线时间+60000
                keyid.pop();
            }
        }
        inline int gettime(int t) // 找到队列中下一个将评判的 key 的时间
        {
            if(keyid.empty())return inf; // 队列为空
            int id=keyid.front();
            if(key[id].t-t>=100000)return inf; // 如果没到可以产生评判的时间，返回 inf
            return key[id].t;
        }
        inline void judge(int t,int judgetime) // 对队列中接触判定线时间为 t 的 key，进行评判，修改判定时间为 judgetime
        {
            for(;!keyid.empty();keyid.pop())
            {
                int id=keyid.front();
                if(key[id].t!=t)break; // 如果接触判定线时间不是 t 了，退出即可
                if(key[id].state!=none)continue; // 评判过的
                key[id].judgetime=judgetime;
                if(abs(key[id].t-judgetime)<20000)key[id].state=perfect; // 根据题目要求判断即可
                else if(abs(key[id].t-judgetime)<60000)key[id].state=good;
                else key[id].state=miss;
            }
        }
    }tr[(3*N)<<2];
    已省去上文讲过的
    int querytime(int x,const int pos,const int t) // 查询下一个将在时间为 t 时产生判定的 key 的接触判定线的时间
    {
        tr[x].pop(t); // 弹出超过时间的和评判过的
        int tim=tr[x].gettime(t); // 找到当前最低的 key 的时间
        // 思路类似于标记永久化，在经过的路径的节点上都要贡献并取 min，因为我们并没有 pushdown 且 pushdown 的时空复杂度过高（需要复制队列）
        if(tr[x].l==tr[x].r)return tim;
        int mid=(tr[x].l+tr[x].r)>>1;
        if(pos<=mid)return min(tim,querytime(lc,pos,t)); // 取 min 是题目要求：只能对离屏幕顶端最远的产生判定
        else return min(tim,querytime(rc,pos,t));
    }
    void change(int x,const int pos,const int t,const int judgetime) // 对接触判定线时间为 t 的 key 评判且修改为 judgetime 的评判时间
    {
        tr[x].judge(t,judgetime); // 直接调用上面的函数即可
        if(tr[x].l==tr[x].r)return;
        int mid=(tr[x].l+tr[x].r)>>1;
        if(pos<=mid)change(lc,pos,t,judgetime);
        else change(rc,pos,t,judgetime);
    }

第五步：求出答案

现在已经对所有能评判的 key 都进行了评判，只剩求答案了。

简单，不解释，看代码：

inline void getans(int n)
{
    for(int i=1;i<=n;i++)
        if(key[i].state==none) // 可能还有一些没判到，这些一定都是 miss
        {
            key[i].state=miss;
            key[i].judgetime=key[i].t+60000;
        }
    sort(key+1,key+n+1,[](const Key &a,const Key &b)
    {
        if(a.judgetime==b.judgetime)return a.state<b.state;
        return a.judgetime<b.judgetime;
    }); // 要根据判定时间来处理
    int perfect=0,good=0,miss=0,maxcombo=0,sum=0;
    for(int i=1;i<=n;i++)
    {
        if(key[i].state==::miss)miss++,maxcombo=max(maxcombo,sum),sum=0; // 不会有人不知道 :: 的含义吧，这就是取全局变量的意思，一般用在有重名的时候
        if(key[i].state==::good)good++,sum++;
        if(key[i].state==::perfect)perfect++,sum++;
    }
    cout<<perfect<<" "<<good<<" "<<miss<<" "<<max(maxcombo,sum);
    if(perfect==maxcombo&&good==0&&miss==0)cerr<<"AP!"; // All Perfect
    else if(maxcombo==n)cerr<<"FC!"; // Full Combo
}

然后捏？没有然后啦，已经做完了喵。

AC 代码

不知道为什么我的代码常数那么大，估计是因为封装太多东西导致的。

// 好吧，怎么卡都卡不进 3 秒内，常数大选手是这样的，实测不开 O2 TLE
#include<bits/stdc++.h>
#define Code using
#define by namespace
#define wjb std
Code by wjb;
constexpr int N=1.2e5+10,inf=1e9;
constexpr int none=0,miss=1,good=2,perfect=3;
struct Key
{
    int t,l,r,judgetime,state;
    bool operator<(const Key &a)const{return t<a.t;}
}key[N];
struct Click
{
    int t,pos;
    bool operator<(const Click &a)const{return t<a.t;}
}click[N];
struct Discretizing
{
    vector<int>a;
    inline void put(int v){a.push_back(v);}
    inline void init()
    {
        sort(a.begin(),a.end());
        a.erase(unique(a.begin(),a.end()),a.end());
    }
    inline int get(int v){return lower_bound(a.begin(),a.end(),v)-a.begin()+1;}
}pos;
struct Seg
{
    struct node
    {
        int l,r;
        list<int>keyid; // 开 queue 或者手写 queue 都会 MLE
        #define push push_back
        #define pop pop_front
        inline void push(int id){keyid.push(id);}
        inline void pop(int t)
        {
            while(!keyid.empty())
            {
                int id=keyid.front();
                if(key[id].state!=none){keyid.pop();continue;}
                if(key[id].t+60000>t)break;
                key[id].judgetime=key[id].t+60000;
                key[id].state=miss;
                keyid.pop();
            }
        }
        inline int gettime(int t)
        {
            if(keyid.empty())return inf;
            int id=keyid.front();
            if(key[id].t-t>=100000)return inf;
            return key[id].t;
        }
        inline void judge(int t,int judgetime)
        {
            for(;!keyid.empty();keyid.pop())
            {
                int id=keyid.front();
                if(key[id].t!=t)break;
                if(key[id].state!=none)continue;
                key[id].judgetime=judgetime;
                if(abs(key[id].t-judgetime)<20000)key[id].state=perfect;
                else if(abs(key[id].t-judgetime)<60000)key[id].state=good;
                else key[id].state=miss;
            }
        }
    }tr[(3*N)<<2];
    #define lc (x<<1)
    #define rc (x<<1|1)
    void build(int x,int l,int r)
    {
        tr[x].l=l,tr[x].r=r;
        if(l==r)return;
        int mid=(l+r)>>1;
        build(lc,l,mid),build(rc,mid+1,r);
    }
    void addkey(int x,const int l,const int r,const int id)
    {
        if(tr[x].l>=l&&tr[x].r<=r)return tr[x].push(id),void();
        int mid=(tr[x].l+tr[x].r)>>1;
        if(l<=mid)addkey(lc,l,r,id);
        if(r>mid)addkey(rc,l,r,id);
    }
    int querytime(int x,const int pos,const int t)
    {
        tr[x].pop(t);
        int tim=tr[x].gettime(t);
        if(tr[x].l==tr[x].r)return tim;
        int mid=(tr[x].l+tr[x].r)>>1;
        if(pos<=mid)return min(tim,querytime(lc,pos,t));
        else return min(tim,querytime(rc,pos,t));
    }
    void change(int x,const int pos,const int t,const int judgetime)
    {
        tr[x].judge(t,judgetime);
        if(tr[x].l==tr[x].r)return;
        int mid=(tr[x].l+tr[x].r)>>1;
        if(pos<=mid)change(lc,pos,t,judgetime);
        else change(rc,pos,t,judgetime);
    }
}T;
inline void init(int n,int m)
{
    for(int i=1;i<=n;i++)
    {
        double t,l,r;cin>>t>>l>>r;
        t=t*1e5+0.5,l=l*1e5+0.5,r=r*1e5+0.5;
        key[i]={t,l,r};
        pos.put(l),pos.put(r);
    }
    for(int i=1;i<=m;i++)
    {
        double t,p;cin>>t>>p;
        t=t*1e5+0.5,p=p*1e5+0.5;
        click[i]={t,p};
        pos.put(p);
    }
}
inline void judge(int n,int m)
{
    for(int i=1;i<=n;i++)
    {
        int l=key[i].l,r=key[i].r;
        T.addkey(1,l,r,i);
    }
    for(int i=1;i<=m;i++)
    {
        int p=click[i].pos,t=T.querytime(1,p,click[i].t);
        if(t!=inf)T.change(1,p,t,click[i].t);
    }
}
inline void getans(int n)
{
    for(int i=1;i<=n;i++)
        if(key[i].state==none)
        {
            key[i].state=miss;
            key[i].judgetime=key[i].t+60000;
        }
    sort(key+1,key+n+1,[](const Key &a,const Key &b)
    {
        if(a.judgetime==b.judgetime)return a.state<b.state;
        return a.judgetime<b.judgetime;
    });
    int perfect=0,good=0,miss=0,maxcombo=0,sum=0;
    for(int i=1;i<=n;i++)
    {
        if(key[i].state==::miss)miss++,maxcombo=max(maxcombo,sum),sum=0;
        if(key[i].state==::good)good++,sum++;
        if(key[i].state==::perfect)perfect++,sum++;
    }
    cout<<perfect<<" "<<good<<" "<<miss<<" "<<max(maxcombo,sum);
    if(perfect==maxcombo&&good==0&&miss==0)cerr<<"AP!";
    else if(maxcombo==n)cerr<<"FC!";
}
int main()
{
    ios::sync_with_stdio(false);cout.tie(0),cin.tie(0);
    int n,m;cin>>n>>m;
    init(n,m);
    sort(key+1,key+n+1),sort(click+1,click+m+1);
    pos.init(),T.build(1,1,pos.a.size());
    for(int i=1;i<=n;i++)key[i].l=pos.get(key[i].l),key[i].r=pos.get(key[i].r);
    for(int i=1;i<=m;i++)click[i].pos=pos.get(click[i].pos);
    judge(n,m),getans(n);
    return 0;
}

补充：

STL 的 queue MLE（10 个点）的原因：queue 只有在销毁的时候才会释放内存，而 list 是弹出元素就释放内存。

关于手写 queue（指针版）也 MLE（5 个点），我不知道，有大佬知道原理的可以评论一下。

另外，有没有 phigros 大佬带带我这个萌新。