题解：P10195 [USACO24FEB] Quantum Moochanics G

_droplet_ · 2025-08-19 15:29:16 · 题解

题目分析

对于某一时刻，第一个碰撞的两点只能是两个相邻的点。

此时我们可以通过双端链表存储没有湮灭的点。

通过题目描述，点的运动轨迹可以理解为先向一边 s_i 单位，回到原来的点后再向另一边 s_i 单位，向这一边 2 \times s_i 单位，回到原来的点后再向另一边 2 \times s_i 单位，以此类推，我们可以 O(1) 的时间复杂度下求出任意两点的湮灭时间。

第一版思路

每次暴力求出任意两相邻点的湮灭时间，用双端链表删点。

优化

若直接暴力枚举的话只能过测试点 1-7，考虑用更快地方法算出湮灭时间。

注意到上方思路可转化为，每次要求一个集合的最小值，加入一个值，删除最小值，可以注意到可以用堆维护。

第二版思路

使用优先队列维护两相邻点湮灭时间，每次从队列重取点并加入左右点，用双端链表删点。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
struct node{
    long long vl,spd;
    int id,l,r;
    bool tn;
}a[N];
struct pq{
    int x,y;
    long long tm;
    friend bool operator<(pq a,pq b){
        return a.tm>b.tm;
    }
};
int n;
long long ans[N];
priority_queue<pq>q;

__inline long work(int x,int y){ // 任意两点的湮灭时间
    long long t=0;
    t=((a[y].vl-a[x].vl-1)/(a[x].spd+a[y].spd)+1)<<1;
    if(a[x].tn) t--;
    return t;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        cin>>n;
        while(!q.empty()) q.pop();
        memset(ans,0,sizeof(ans));
        a[0].r=1,a[n+1].l=n;
        for(int i=1;i<=n;i++) a[i].r=i+1,a[i].l=i-1;
        for(int i=1;i<=n;i++) cin>>a[i].vl,a[i].tn=i&1;
        for(int i=1;i<=n;i++) cin>>a[i].spd,a[i].id=i;
        for(int i=a[0].r;a[i].r!=n+1;i=a[i].r){
            int x=i,y=a[i].r;
            long long t=work(x,y);
            q.push({x,y,t});
        }
        while(1){
            auto [x,y,t]=q.top();
            q.pop();
            if(ans[x]||ans[y]) continue; // 若该点对其中一点已经被删，该点对不存在，舍去
            ans[x]=ans[y]=t;
            a[a[x].l].r=a[y].r;
            a[a[y].r].l=a[x].l;
            if(a[0].r==n+1) break;
            if(a[x].l==0||a[y].r==n+1) continue;
            long long nt=work(a[x].l,a[y].r);
            q.push({a[x].l,a[y].r,nt});
        }
        for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
        cout<<"\n";
    }
    return 0;
}