约瑟夫问题

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1073 范围：10^6

http://noi.openjudge.cn/ch0302/1748/ 范围：30

三种方法分别得分：链接1：0      92   100

                         链接2：100  100 100

以下三种方法时间复杂度递减

#include<cstdio>#include<cstring>using namespace std;int n,k;bool v[301];int main(){    while(scanf("%d%d",&n,&k)!=EOF)    {        if(!n) return 0;        int now=-1,id=0,s=0;        memset(v,0,sizeof(v));        while(s<n-1)        {            while(id<k)            {                now=(now+1)%n;                if(!v[now]) id++;            }            v[now]=true;            s++;            id=0;        }         for(int i=0;i<n;i++)         if(!v[i])         {             printf("%d\n",i+1);             break;         }    }    }

暴力枚举法

 

#include<cstdio>#include<algorithm>#define N 1000001using namespace std;int n,m;struct node{    int l,r,sum;}tr[N*4];void build(int k,int l,int r){    tr[k].l=l; tr[k].r=r; tr[k].sum=r-l+1;    if(l==r) return;    int mid=l+r>>1;    build(k<<1,l,mid);build(k<<1|1,mid+1,r);}int query2(int k,int opl,int opr){    if(opl==tr[k].l&&opr==tr[k].r) return    tr[k].sum;    int mid=tr[k].l+tr[k].r>>1;    if(opr<=mid) return query2(k<<1,opl,opr);    if(opl>mid) return query2(k<<1|1,opl,opr);    return  query2(k<<1,opl,mid)+query2(k<<1|1,mid+1,opr);}int query1(int k,int l,int s){    if(tr[k].l==tr[k].r)     return tr[k].l;    int mid=tr[k].l+tr[k].r>>1;    int tmp=0;    if(l<=mid) tmp=query2(k,l,mid);    if(s<=tmp) query1(k<<1,l,s);    else  query1(k<<1|1,max(mid+1,l),s-tmp);}void change(int k,int w){    if(tr[k].l==tr[k].r)    {        tr[k].sum=0;        return;    }    int mid=tr[k].l+tr[k].r>>1;    if(w<=mid) change(k<<1,w);    else change(k<<1|1,w);    tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;}int query3(int k,int s){    if(tr[k].l==tr[k].r) return tr[k].l;    int tmp=tr[k<<1].sum;    if(s<=tmp) return query3(k<<1,s);    return query3(k<<1|1,s-tmp);}int main(){    while(scanf("%d%d",&n,&m)!=EOF)    {        if(!n) return 0;        build(1,1,n);        int pos=0,k,tot,tot2;        for(int i=1;i<n;i++)        {            if(pos==n) pos=0;            tot=query2(1,pos+1,n);            if(tot>=m)  pos=query1(1,pos+1,m);            else            {                k=m-tot;                tot2=query2(1,1,n);                k%=tot2;                if(!k) k=tot2;                pos=query3(1,k);            }            change(1,pos);        }        printf("%d\n",query3(1,1));    }    }

线段树

 

#include<cstdio>using namespace std;int main(){    int n,k,ans=0;    scanf("%d%d",&n,&k);    for(int i=2;i<=n;i++)     ans=(ans+k)%i;    printf("%d",ans+1);}

推公式

 某大佬的推导过程http://book.51cto.com/art/201403/433941.htm