poj1426，POJ 2886 Who Gets the MostCandies

POJ 2886 Who Gets the MostCandies?(線段樹+模擬+求數的約數個數)

http://poj.org/problem?id=2886

題意： n個孩子按順時針排列，每個人手上都有一張牌，牌上有一個數字，從第k個孩子開始出隊，出隊的孩子卡上數字是val,則從他開始順時針第val人是下一個出隊的，負數則逆時針數那個第val個人，第P個出隊的會得到的糖果數是p的因子個數，輸出得到最多糖果的人和他的糖果數，如果有多個，則輸出最先出隊的人。

分析：

? ? ? ? 其實本題就是模擬每輪游戲，然后在每一輪游戲中先算出當前需要出隊的第j個孩子，然后用線段樹找到還在隊中的第j個還是得原始編號，因為要輸出名字。

poj1426、? ? ? ? 首先建立一棵線段樹，其每個葉節點都是1（代表每個孩子都在圈中，如果第i個孩子不在圈中，那么就令第i個葉子（孩子的編號不是i而是i管理的區間l或r）sum=0）。

分析題中的例子：

4 2

Tom 2

Jack 4

Mary -1

Sam 1

?????? 假設我們第一個出去的孩子是第2個孩子，那么我們把第二個葉節點的值置為0，該步只需要通過update找到sum值正好為2的那個區間的右端點（且該右端點的sum值也為1）即可。然后讓這個sum變為0，表示這個孩子出了圈。并且我們讀到了JACK的val值為4，當前圈剩余3個人，所以我們向后找4%3=1個人，如果[3，n]內的sum和>=1，那么直接在JACK右邊即[3，n]區間找即可。如果sum的和<1，那么就在JACK左邊[1,1]內找1-sum的那個位置的1.

依次類推即可。線段樹的每個葉節點維護name，val，sum三個值，非葉節點只需要維護sum值即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 500000+100;
#define lson i*2,l,m
#define rson i*2+1,m+1,r
int sum[MAXN*4];
int cnt;
struct node
{char name[10];int val;
}nodes[MAXN];
void PushUp(int i)
{sum[i]=sum[i*2]+sum[i*2+1];
}
void build(int i,int l,int r)
{if(l==r){sum[i]=1;return ;}int m=(l+r)/2;build(lson);build(rson);PushUp(i);
}int update(int q,int i,int l,int r)//找到第q個sum為1的葉節點，并返回其在線段樹中的節點編號
{if(l==r){sum[i]=0;return l;}int m=(r+l)/2;int res;if(q<=sum[2*i]) res= update(q,lson);else  res= update(q-sum[2*i],rson);PushUp(i);return res;
}
int f[500010];//f[i]=x表示i的約數有x個
void get_f()
{int i,j;for(i=1;i<=500000;i++)for(j=1;i*j<=500000;j++){f[i*j]++;//假設x=i*j，那么i*j和j*i時，f[x]都會++，正好是加上了i和j各一次。}
}
int main()
{int n,k;memset(f,0,sizeof(f));get_f();while(scanf("%d%d",&n,&k)==2&&n&&k){build(1,1,n);for(int i=1;i<=n;i++){scanf("%s%d",nodes[i].name,&nodes[i].val);}if(n==1){printf("%s 1\n",nodes[1].name);continue;}int j=k;int ans=0;char ans_name[10];cnt=n;//cnt為當前有效葉節點的總數for(int i=1;i<=n;i++){//printf("j=%d\n",j);int num=update(j,1,1,n);//num是指原始序列的第num個孩子，j是指線段樹區間[1,n]內的第j個1cnt--;int x= f[i];int v=nodes[num].val;if(ans<x){ans = x;strcpy(ans_name,nodes[num].name);}if(i==n)break;int l_num=j-1;int r_num=cnt-j+1;if(v<0)//用v值來得到下一個需要處理的j值{v=(-v)%cnt;if(v==0)v=cnt;if(l_num>=v) j =l_num-v+1;else j=cnt-(v-l_num)+1;}else if(v>0){v=v%cnt;if(v==0)v=cnt;if(r_num>=v)j=l_num+v;else j=v-r_num;}}printf("%s %d\n",ans_name,ans);}return 0;
}

?