[cpp] /******************************************* 題目大意： 有n個小孩在玩游戲，每個小孩手上都有一個數字; 第k個小孩先出去，然後給出手上的數值x; 大於0的話就是從他左邊開始數的第x個小孩; 否則就是從右邊數的第-x個小孩接著出列; 直到所有小孩出列; 第p個出列的小孩，將拿到f(p)個糖果; f(p)表示p的正因子個數; 現在要求得到最多糖果的小孩; 算法分析： 對於任何正整數x,其約數的個數記做g(x).例如g(1)=1,g(6)=4; 如果某個正整數x滿足:對於任意i(0<i<x),都有g(i)<g(x),則稱x為反素數; 所以反素數滿足f[x]>f[i](1<i<x); 所以得到的最多糖果數其實就是小於n的最大反素數k; 反素數可以直接預處理也可以求; 之後用線段樹模擬二分搜索找到第k個小孩出列為止; 算法過程： 建立線段樹，線段樹區間表示區間內人的個數; 搜索第i個人時所經過的路徑區間人數的減一; 然後根據提示求得的下一個跳出的人是誰; 並記錄第i個跳出的人是誰; ********************************************/ #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<climits> #include<algorithm> using namespace std; #define L l,m,u<<1 #define R m+1,r,u<<1|1 //u*2+1 const int N=500005; struct node { int l,r; int sum; }a[N*3]; struct game { char name[12]; int x; }s[N]; int c[N];//第i個人跳出所得糖果 int num;//得糖果最多的人的輸入序號 int n,k; int v,z;//z表示當前已跳出的人數 int e;//e表示第幾個跳出的人得到的糖果最多 void build(int l,int r,int u)//u為根結點 { a[u].l=l; a[u].r=r; a[u].sum=(r-l+1); if(a[u].l==a[u].r) return; int m=(r+l)>>1; build(L); build(R); } void updata(int u,int t)//t表示目前隊列此區間第幾個人跳出 { a[u].sum--;//所到區間人數減一,自上而下沿途更新 if(a[u].l==a[u].r)//最後結點 { if(e==z)//z是當前已跳出的人數 { num=a[u].l;//如果是第e個人跳出 記錄答案 } if(n-z==0)//全跳出 return ; if(s[a[u].l].x>0)//求從線段樹左起下一次第幾個人跳出 v--; v=((v+s[a[u].l].x)%(n-z)+(n-z))%(n-z);//坑爹有沒有~ if(v==0)//一圈轉完了 v=n-z;//計算下一個要刪除的人是從左算起的第幾個人 } else { if(a[u*2].sum>=t)//左邊人數足夠則向左搜 { updata(u*2,t); } else { t-=a[u*2].sum;//否則減去左邊人數向右搜 updata(u*2+1,t); } } } void candy()//求第i人跳出能得到的糖果數量 { memset(c,0,sizeof(c)); for(int i=1; i<N; i++) { c[i]++; for(int j=i*2; j<N; j+=i) { c[j]++; } } } int main() { //freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin); candy(); while(~scanf("%d %d",&n,&k)) { e=1; for(int i=1; i<=n; i++) { www.2cto.com getchar(); scanf("%s %d",s[i].name,&s[i].x); if(c[i]>c[e]) e=i; } build(1,n,1); v=k;//第k個孩子先跳出 for(z=1; z<=n; ++z)//z表示當前已跳出的人數 { updata(1,v); } printf("%s %d\n",s[num].name,c[e]); } return 0; }
