P8671 [蓝桥杯 2018 国 AC] 约瑟夫环 题解

· · 题解

大家好，我非常喜欢线段树，所以我用线段树通过了这道题。

看各位大佬们用的都是递推公式，本蒟蒻就讲一个好理解一点的线段树吧。

朴素做法当然是直接枚举，时间复杂度 \mathcal O(nk)。

我们现在想一下它的问题在哪里。每次踢一个人没有问题，但是查找下一个要被踢掉的人要用 \mathcal O(k) 的时间来找。这时候就要用强大的线段树来优化啦。

我们的线段树要支持以下操作：

第一个操作好说，第二个其实有做法，但是有点科技，这里讲一个小技巧转化成全局查询。

我们先把没被踢的人记为 1，踢掉的人记为 0。

这样，我们便可以 \mathcal O(\log n) 求出一个人前面和后面还剩下多少人。

设当前被删的人的位置为 pos，这个人前面剩下的人数为 pre，后面剩下的人数为 suf。

接下来分类讨论一下：

全局查询直接在线段树上二分就可以。

这样就做完啦，有什么问题欢迎指出！

#include<bits/stdc++.h>
using namespace std;
#define re register
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
const int maxn=1e6+10;
int n,k;
int t[maxn<<2];
inline void pushup(int p){
    t[p]=t[ls]+t[rs];
}
void build(int p,int l,int r){
    if(l==r){
        t[p]=1;
        return ;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(p); 
}
void remove(int p,int l,int r,int v){
    if(l==r){
        t[p]=0;
        return ;
    }
    if(mid>=v)remove(ls,l,mid,v);
    else remove(rs,mid+1,r,v);
    pushup(p);
}
int querys(int p,int l,int r,int L,int R){
    if(L<=l&&r<=R)return t[p];
    int res=0;
    if(mid>=L)res+=querys(ls,l,mid,L,R);
    if(mid<R)res+=querys(rs,mid+1,r,L,R);
    return res;
}
int queryr(int p,int l,int r,int rk){
    if(l==r)return l;
    if(t[ls]>=rk)return queryr(ls,l,mid,rk);
    else return queryr(rs,mid+1,r,rk-t[ls]); 
}
int pos=0;
int rest;
bool killed[maxn];
int tmp,pre,suf;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    rest=n;
    build(1,1,n);
    while(rest>1){
        tmp=(k-1)%rest+1;//随着剩余人数的减少，k有可能比n大，需要处理一下
        pre=(pos<=1?0:querys(1,1,n,1,pos-1));
        suf=querys(1,1,n,pos+1,n);
        if(suf<tmp)pos=queryr(1,1,n,tmp-suf);
        else pos=queryr(1,1,n,pre+tmp);
        remove(1,1,n,pos);
        killed[pos]=true;
        rest--;
    }
    for(re int i=1;i<=n;++i){
        if(!killed[i]){
            cout<<i;
            break;
        }
    }
    return 0;
}