1009: Josephus環的複仇

時間限制: 1 Sec  記憶體限制: 128 MB

送出: 170  解決: 15

[送出][狀态][讨論版]

題目描述

任給正整數n、k，按下述方法可得排列1，2，……,n的一個置換：将數字1，2，.. .,n環形排列，按順時針方向從1開始計數；計滿K時輸出該為之上的數字(并從環中删去該數字)，然後從下一個數字開始繼續計數，直到環中所有數字均被輸出為止。試編寫一算法，對輸人的任意正整數n、k（n>=k>0），輸出相應的置換。

資料結構老師沒有告訴xry111這題n、k的上限，是以xry111自作主張地認為n<=200000。請解決這一問題。

輸入

單組資料，包含2個整數n、k（0<k<=n<=200000）。

輸出

輸出1行，包含n個整數（含義如題目描述），用空格分割。

行末不要有多餘的空格。

樣例輸入

10 3      

樣例輸出

3 6 9 2 7 1 8 5 10 4

      

#include<bits/stdc++.h> 
#define REP(i,a,b) for(int i=a;i<=b;i++) 
#define MS0(a) memset(a,0,sizeof(a)) 
#define lson l,m,rt<<1 
#define rson m+1,r,rt<<1|1 
  
using namespace std; 
  
typedef long long ll; 
const int maxn=200100; 
const int INF=(1<<29); 
  
int n,k,K; 
struct SegTree 
{ 
    int l,r; 
    int id,cnt; 
    void debug() 
    { 
        printf("%2d %2d %2d %2d\n",l,r,id,cnt); 
    } 
};SegTree T[maxn<<2]; 
  
void push_up(int rt) 
{ 
    T[rt].cnt=T[rt<<1].cnt+T[rt<<1|1].cnt; 
} 
  
void build(int l,int r,int rt) 
{ 
    T[rt].l=l;T[rt].r=r; 
    if(l==r){ 
        T[rt].id=l; 
        T[rt].cnt=1; 
        return; 
    } 
    int m=(l+r)>>1; 
    build(lson); 
    build(rson); 
    push_up(rt); 
} 
  
int query(int L,int R,int l,int r,int rt) 
{ 
    if(L<=l&&r<=R) return T[rt].cnt; 
    int m=(l+r)>>1; 
    int res=0; 
    if(L<=m) res+=query(L,R,lson); 
    if(R>m) res+=query(L,R,rson); 
    return res; 
} 
  
void update(int p,int c,int l,int r,int rt) 
{ 
    if(l==r){ 
        T[rt].cnt=c; 
        return; 
    } 
    int m=(l+r)>>1; 
    if(p<=m) update(p,c,lson); 
    else update(p,c,rson); 
    push_up(rt); 
} 
  
int bin(int p,int l,int r) 
{ 
    while(l<r){ 
        int m=(l+r)>>1; 
        int ls=query(l,m,1,n,1); 
        if(p<=ls) r=m; 
        else l=m+1,p-=ls; 
    } 
    return l; 
} 
  
int main() 
{ 
    while(~scanf("%d%d",&n,&k)){ 
        build(1,n,1); 
        int cur=1; 
        REP(i,1,n){ 
            cur=(cur+k-1)%T[1].cnt; 
            if(cur==0) cur=T[1].cnt; 
            int p=bin(cur,1,n); 
            if(i==n) printf("%d\n",p); 
            else printf("%d ",p); 
            update(p,0,1,n,1); 
        } 
    } 
    return 0; 
} 
  
/************************************************************** 
    Problem: 1009 
    User: 14030140102 
    Language: C++ 
    Result: 正确 
    Time:716 ms 
    Memory:14196 kb 
****************************************************************/       

View Code

#include<bits/stdc++.h> 
#define REP(i,a,b) for(int i=a;i<=b;i++) 
#define MS0(a) memset(a,0,sizeof(a)) 
#define lson l,m,rt<<1 
#define rson m+1,r,rt<<1|1 
  
using namespace std; 
  
typedef long long ll; 
const int maxn=200100; 
const int INF=(1<<29); 
  
int n,k; 
int c[maxn];

int lowbit(int x)
{
    return x&(-x);
}

void add(int p,int x)
{
    while(p<=n){
        c[p]+=x;
        p+=lowbit(p);
    }
}

int sum(int p)
{
    int res=0;
    while(p>0){
        res+=c[p];
        p-=lowbit(p);
    }
    return res;
}
  
int bin(int p,int l,int r) 
{ 
    while(l<r){ 
        int m=(l+r)>>1; 
        int ls=sum(m)-sum(l-1);
        if(p<=ls) r=m; 
        else l=m+1,p-=ls; 
    } 
    return l; 
} 
  
int main() 
{ 
    while(~scanf("%d%d",&n,&k)){ 
        MS0(c);
        int cur=1; 
        REP(i,1,n) add(i,1);
        REP(i,1,n){ 
            int cnt=sum(n);
            cur=(cur+k-1)%cnt; 
            if(cur==0) cur=cnt; 
            int p=bin(cur,1,n); 
            if(i==n) printf("%d\n",p); 
            else printf("%d ",p);
            int x=sum(p)-sum(p-1);
            add(p,-x); 
        } 
    } 
    return 0; 
}      

View Code

轉載于:https://www.cnblogs.com/--560/p/4947308.html