AT_abc412_c [ABC412C] Giant Domino-题解

Hf_Poem · 2025-11-21 18:32:43 · 题解

我们将骨牌视为图中的节点，如果骨牌 i 可以推倒骨牌 j（即 S_j \leq 2\times S_i），则存在从 i 到 j 的有向边。

所以将骨牌按大小排序，使用双向链表维护未访问节点，BFS 时只需遍历链表中满足大小条件的节点即可。

具体的算法：

先将骨牌按大小排序，记录每个骨牌在排序后的位置，然后建立双向链表维护未访问节点。

从 1 号骨牌开始 BFS，每次扩展时遍历链表中所有大小不超过当前骨牌大小两倍的骨牌。

访问过的节点需要从链表中删除。

最后，当访问到 N 号骨牌时就找到路径长度啦。

代码实现

#include<bits/stdc++.h>
#define IXcape cout<<endl;return 0
#define Venti cout<<"\nVenti!\n"
#define int long long
using namespace std;
const int V=1e6+10;
int s[V];
int p[V],nxt[V],pr[V],d[V];
pair<int,int> a[V];

inline
void rm(int idx,int&h){
    if(pr[idx]!=-1)nxt[pr[idx]]=nxt[idx];
    else h=nxt[idx];
    if(nxt[idx]!=-1)pr[nxt[idx]]=pr[idx];
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        int N;
        cin>>N;
        for(int i=1;i<=N;i++)cin>>s[i];
        for(int i=0;i<N;i++)a[i]={s[i+1],i+1};
        sort(a,a+N);
        int pos[N+1];
        for(int i=0;i<N;i++)pos[a[i].second]=i;
        int h=0;
        for(int i=0;i<N;i++){
            pr[i]=i-1;
            nxt[i]=i+1;
        }
        pr[0]=-1;
        nxt[N-1]=-1;
        memset(d,-1,sizeof(d));
        queue<int>q;
        d[1]=1;
        q.push(1);
        rm(pos[1],h);
        while(!q.empty()){
            int u=q.front();q.pop();
            if(u==N)break;
            int t=2*s[u];
            int c=h;
            while(c!=-1&&a[c].first<=t){
                int nx=nxt[c],id=a[c].second;
                if(d[id]==-1){
                    d[id]=d[u]+1;
                    q.push(id);
                    rm(c,h);
                }
                c=nx;
            }
        }
        cout<<d[N]<<'\n';
    }
    IXcape;
}

时间复杂度 O(N \log N)。