http://poj.org/problem?id=2886
題意：N 個小孩圍成一圈，他們被順時針編號為 1 到 N。每個小孩手中有一個卡片，上面有一個非 0 的數字，游戲從第 K 個小孩開始，他告訴其他小孩他卡片上的數字並離開這個圈，他卡片上的數字 A 表明了下一個離開的小孩，如果 A 是大於 0 的，則下個離開的是左手邊第 A 個，如果是小於 0 的，則是右手邊的第 -A 個小孩。游戲將直到所有小孩都離開，在游戲中，第 p 個離開的小孩將得到 F(p) 個糖果，F(p) 是 p 的約數的個數，問誰將得到最多的糖果。輸出最幸運的小孩的名字和他可以得到的糖果。
思路：乍一看這個題真不知道用線段樹怎麼寫，類似於約瑟夫環問題，每次從圈中刪除一個人，直到所有人出圈。其實線段樹恰好可以解決從圈中刪除一人這個問題，即單點更新。
因為n個小孩依次出圈，要知道誰的糖果最多，也就是求誰出圈的次序號的約數最多。所以我們可以預處理，先求出1~n中約數最多的那個數maxid,其約數個數是maxnum。所以我們直接模擬約瑟夫環，誰的出圈序號是maxid，誰得到的糖果最多。
當第一個人出圈後，下一個怎麼求？這就是由相對位置求原始位置的問題。只有先求出這次出圈的人的原始位置才能求出下一個人。這是通過線段樹來求的。線段樹附加區域存的是這個區間還有多少人，每踢出一個人區間的長度減1.求原始位置的方法與poj2828插隊問題類似。只不過那個是求出原始位置後直接插入，而這個是返回原始位置。
#include#include const int maxn = 500005; struct line { int l; int r; int len; }tree[maxn<<2]; int n,k; int maxid; //約束最大的編號 int maxnum; //約束個數的最大值，即maxid的約束個數 int div[maxn];//預處理每個數的約束個數 //預處理約數個數，並找出約束個數最多的編號maxid及其約束個數maxnum void solve_division() { memset(div,0,sizeof(div)); for(int i = 1; i <= n; i++) { div[i]++; for(int j = i*2; j <= n; j+=i) div[j]++; } maxid = 1; maxnum = div[1]; for(int i = 2; i <= n; i++) { if(div[i] > maxnum) { maxnum = div[i]; maxid = i; } } } void build(int v, int l, int r) { tree[v].l = l; tree[v].r = r; tree[v].len = r-l+1; if(l == r) return ; int mid = (l+r)>>1; build(v*2,l,mid); build(v*2+1,mid+1,r); } int query(int v, int k) //由相對位置找到其實際位置 { tree[v].len--; if(tree[v].l == tree[v].r) return tree[v].l; if(k <= tree[v*2].len) return query(v*2,k); else return query(v*2+1,k-tree[v*2].len); } char name[maxn][15]; int card[maxn]; int main() { while(~scanf("%d %d",&n,&k)) { solve_division(); for(int i = 1; i <= n; i++) scanf("%s %d",name[i],&card[i]); build(1,1,n); int pos; for(int i = 0; i < maxid; i++) //出圈maxid即可，就能找出第maxid次出圈的人的實際位置 { pos = query(1,k);//找到原始位置 n--;//出圈，個數減1 if(n==0) break; if(card[pos] > 0) k=(k-1+card[pos]-1)%n+1; else k=((k-1+card[pos])%n+n)%n+1; } printf("%s %d\n",name[pos],maxnum); } return 0; }
