CodeVS/1282 2015年4月5日 (日) 20:02云璟月（讨论 | 贡献）的版本 (差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
约瑟夫问题	★☆☆☆☆	答案正确	100	2015-3-29 21:26:45	数组不够大（40）

题意

N个小朋友围一圈，每次点到第k个出列，问出列顺序。

题解

• 我们设定小朋友有两个编号，一个是原始编号i，另一个是在剔除掉一些小朋友后的编号i'，每个小朋友后是否在圈中记为p。e.g.

原始编号
i  1 2 3 4 5
i' 1 2 3 4 5
p  1 1 1 1 1
剔除掉第3个小朋友的编号
i  1 2 3 4 5
i' 1 2 x 3 4
p  1 1 0 1 1

容易知道i'是p的前缀和。可以用线段树处理问题。

代码

1282.cpp代码已折叠 展开折叠内容

#include<stdio.h> #include<algorithm> using namespace std; template<size_t N> class SegmentTree { //模板：线段树// public: int tree[N]; int lazy[N]; #define lchild rt << 1, l, m #define rchild rt << 1 | 1, m + 1, r void push_up(int rt) { tree[rt] = tree[rt << 1] + tree[rt << 1 | 1]; } int build(int rt,int l,int r,int ex) { if(l==r) { if(ex!=l) return tree[rt]=1; else return tree[rt]=1e+7; } int m=(l+r)>>1; return tree[rt]=build(lchild,ex)+build(rchild,ex); } void push_down(int rt, int len) { tree[rt << 1] += lazy[rt] * (len - (len >> 1)); lazy[rt << 1] += lazy[rt]; tree[rt << 1 | 1] += lazy[rt] * (len >> 1); lazy[rt << 1 | 1] += lazy[rt]; lazy[rt] = 0; } void push_down(int rt) { tree[rt << 1] += lazy[rt]; lazy[rt << 1] += lazy[rt]; tree[rt << 1 | 1] += lazy[rt]; lazy[rt << 1 | 1] += lazy[rt]; lazy[rt] = 0; } void update(int L, int R, int delta, int rt , int l , int r ) { if (L <= l && r <= R) { tree[rt] += delta * (r - l + 1); lazy[rt] += delta; return; } if (lazy[rt]) push_down(rt, r - l + 1); int m = (l + r) >> 1; if (L <= m) update(L, R, delta, lchild); if (R > m) update(L, R, delta, rchild); push_up(rt); } int query(int L, int R, int rt , int l , int r ) { if (L <= l && r <= R) return tree[rt]; if (lazy[rt]) push_down(rt, r - l + 1); int m = (l + r) >> 1, ret = 0; if (L <= m) ret += query(L, R, lchild); if (R > m) ret += query(L, R, rchild); return ret; } }; SegmentTree<33333> tre={}; int n,k; int biSearch(int l,int r,int last) { if(l==r)return l; if(r<=0)return -1e+6; if(tre.query(1,m,1,1,n+1)<last) return biSearch(m+1,r,last); else return biSearch(l,m,last); } int main() { scanf("%d%d",&n,&k); tre.build(1,1,n+1,n+1); int last=0,least=n,lasti; for(int i=1;i<=n;++i,--least) { last=(last+k-1)%least+1; lasti=biSearch(1,n+1,last); tre.update(lasti,lasti,-1,1,1,n+1); printf("%d ",lasti); --last; } }