Who Gets the Most Candies? POJ - 2886（線段樹單點更新+區間查詢+反素數）

預備知識：反素數決議

思路：有了反素數的解法之后就是線段樹的事了，

我們可以用線段樹來維護哪些人被淘汰，哪些人沒被淘汰，被淘汰的人的位置，沒被淘汰的人的位置，

我們可以把所有人表示為一個[1,n]的區間，沒被淘汰的人權值為1，那么通過線段樹維護區間和，就可以知道沒被淘汰人的分布情況，tree[root].value就是總人數，因為線段樹的二分性質，如果淘汰的人在第x個位置，那么我們可以找到區間和為x的位置來得到這個人的位置，把這個位置的權值更新為0，然后更新線段樹，就可以表示這個人被淘汰，總人數也是減去1，就可以表示游戲中還剩多少人，

假設這個被淘汰的人位置是inx,下一個淘汰的人位于他的左（右）第A個，我們可以mod = A%（剩余人數），然后我們可以得到inx左邊（L）和右邊的人數（R），然后根據mod和A的正負號來確定下一個人的位置，

  1 #include <iostream>
  2 #include <cmath>
  3 #include <cstdio>
  4 
  5 #define ll long long
  6 
  7 using namespace std;
  8 
  9 const int N = 5e5+10;
 10 struct Info{
 11     char name[20];
 12     int turn;
 13 }p[N];
 14 struct node{
 15     int l,r,value;
 16     int mid(){ return (l+r) >> 1; }
 17 }tree[N << 2];
 18 int c[N];
 19 int n, s, ss, inx;
 20 int pr[] = {2,3,5,7,11,13,17,19,23,29};
 21 int Max,num;
 22 
 23 void dfs(int inx, int v, int cnt, int pw){
 24     for(int i = 1; i <= pw; ++i){
 25         if((ll)v * pr[inx] > (ll)n){
 26             if(Max < cnt * i){
 27                 Max = cnt * i;
 28                 num = v;
 29                 
 30             }else if(cnt * i == Max) num = min(num, v);
 31             break;
 32         }
 33         else dfs(inx + 1, v *= pr[inx], cnt * (i + 1), i);
 34 
 35     }
 36 }
 37 
 38 //反素數模板
 39 void AntPrime(){
 40     Max = 1;
 41     dfs(0, 1, 1, 30);   
 42 }
 43 
 44 void build_tree(int rt, int L, int R){
 45     tree[rt].l = L; tree[rt].r = R;
 46     if(L == R){
 47         if(L == s) inx = rt;
 48         tree[rt].value = https://www.cnblogs.com/SSummerZzz/p/1;
 49         return;
 50     }
 51     int mid = tree[rt].mid();
 52     int lson = rt << 1;
 53     int rson = rt << 1 | 1;
 54     build_tree(lson, L, mid);
 55     build_tree(rson,mid + 1, R);
 56     tree[rt].value = https://www.cnblogs.com/SSummerZzz/p/tree[lson].value + tree[rson].value;
 57 }
 58 
 59 void update(int x){
 60     while(x != 1){
 61         --tree[x].value;
 62         x >>= 1;
 63     }
 64 }
 65 
 66 void search(int tot,int rt){
 67     //找到位置
 68     if(tree[rt].l == tree[rt].r){
 69         ss = tree[rt].l; //原始佇列的位置
 70         inx = rt; //線段樹的位置，方便更新
 71         return;
 72     }
 73     int lson = rt << 1;
 74     int rson = rt << 1 | 1;
 75     if(tree[lson].value >= tot) search(tot, lson);
 76     else search(tot - tree[lson].value, rson);
 77 }
 78 
 79 void solve(){
 80     while(~scanf("%d%d", &n, &s)){
 81         build_tree(1,1,n);
 82         AntPrime();//得到反素數和它的約數個數
 83         for(int i = 1; i <= n; ++i){
 84             scanf("%s%d", p[i].name, &p[i].turn);
 85         }
 86         int cnt = 0;
 87         int remain = n;
 88         //s  淘汰佇列人的位置
 89         //ss 原始佇列人的位置
 90         ss = s;
 91         while(++cnt != num){
 92             update(inx);//更新線段樹
 93             int turn = abs((double)p[ss].turn); 
 94             turn %= (remain - 1);
 95             if(!turn) turn = remain - 1;
 96             if(p[ss].turn > 0){ 
 97                 int r = remain - s;
 98                 if(r >= turn) s = s + turn - 1;
 99                 else s = turn - r;
100             }else{
101                 int l = s - 1;
102                 if(l >= turn) s = l - turn + 1;
103                 else s = (remain - 1) - (turn - l) + 1;
104             }
105             // cout << "position is " << ss << endl;
106             // cout << "jumped out people  " << p[ss].name << endl;
107             search(s, 1);
108             --remain;
109         }
110         printf("%s %d\n", p[ss].name, Max);
111     }    
112 }
113 
114 int main(){
115 
116     solve();
117 
118     return 0;
119 }

標籤：其他

上一篇：反素數決議

下一篇：POJ - 1847 Tram