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 <stdio.h> #include <string.h> 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; }