POJ 2886Who Gets the Most Candies?（线段树）-白红宇

POJ 2886Who Gets the Most Candies?（线段树）

阅读量：6500 次

发布时间：2019-06-24

本文共 3458 字，大约阅读时间需要 11 分钟。

题目大意是说有n个人围成一圈，游戏的起点是k，每个人持有一个数字(非编号)num，每次当前的人退出圈，下一个人是他左边的第num个(也就是说下一个退出的是k+num， k可以为负数，表示右边的第num个)，这里的num的范围是1e9，现在一直如果一个人是第i个推出的，那么他的得分就是i的约束的个数，球得分最高的那个人的编号

这里有两个地方稍微不好处理：

1： num < 1e9 这里只需要模拟一下就可以了，如果当前在k，往右走num，还剩下rest个人，那么下一步应该往右走num % rest,同时先使用线段树计算出当前位置的左侧和右侧还有多少人，线段树里保存的是当前区间还剩下多少个人，线段树就可以查找出下一个需要推出的人的编号

2：由于i的约数的个数是可以求出的，也就是说只需要在N内找到一个约束最大的数X，判断谁是第X个退出的就可以了。这里就用到了反素数的概念，设G[i]表示i的约数的个数，若对于任意的j，j<i有G[i] > G[j]，那么i就是i反素数，这道题就转化为了球N以内的最大的反素数，设Max[i]为i以内的最大的反素数是Max[i]。在计算反素数时，设D[i]为i的约数的个数，由于对于i的一个素因子a，i除尽a后得到的a的幂是b，有D[i] = D[i/a] * (b+1) / b，而在计算D[i]时，D[i/a]已经被计算出，所以按照DP的思路，总体的复杂度就是NlonN（logN为求b时的复杂度）

1 #include   2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
               10 #include 
              
                11 #include 
               
                 12 #include 
                
                  13 #include 
                 
                   14 using namespace std; 15 #define INF 1e9 16 #define inf (-((LL)1<<40)) 17 #define lson k<<1, L, mid 18 #define rson k<<1|1, mid+1, R 19 #define mem0(a) memset(a,0,sizeof(a)) 20 #define mem1(a) memset(a,-1,sizeof(a)) 21 #define mem(a, b) memset(a, b, sizeof(a)) 22 #define FOPENIN(IN) freopen(IN, "r", stdin) 23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout) 24 template
                  
                    T CMP_MIN(T a, T b) { return a < b; } 25 template
                   
                     T CMP_MAX(T a, T b) { return a > b; } 26 template
                    
                      T MAX(T a, T b) { return a > b ? a : b; } 27 template
                     
                       T MIN(T a, T b) { return a < b ? a : b; } 28 template
                      
                        T GCD(T a, T b) { return b ? GCD(b, a%b) : a; } 29 template
                       
                         T LCM(T a, T b) { return a / GCD(a,b) * b; } 30 31 typedef __int64 LL; 32 //typedef long long LL; 33 const int MAXN = 500005; 34 const int MAXM = 100005; 35 const double eps = 1e-10; 36 const LL MOD = 1000000007; 37 38 char name[MAXN][20]; 39 int N, K,cnt, l, r, curPos; 40 int num[MAXN], tree[MAXN<<2], no[MAXN]; 41 42 void buildTree(int k, int L, int R) 43 { 44 if(L == R) { tree[k] = 1; return ; } 45 46 int mid = (L + R) >> 1; 47 48 buildTree(lson); buildTree(rson); 49 50 tree[k] = tree[k<<1] + tree[k<<1|1]; 51 } 52 53 void update(int k, int L, int R, int x) 54 { 55 if(L == R) { tree[k] = 0; no[L] = cnt; curPos = L; return ;} 56 57 int mid = (L + R) >> 1; 58 59 if(x <= tree[k<<1]) update(lson, x); 60 61 else update(rson, x-tree[k<<1]); 62 63 tree[k] = tree[k<<1] + tree[k<<1|1]; 64 } 65 66 int query(int k, int L, int R) 67 { 68 if(R < l || r < L) return 0; 69 70 if(l<=L && R<=r) return tree[k]; 71 72 int mid = (L+R) >> 1; 73 74 return query(lson) + query(rson); 75 } 76 77 void getNo() 78 { 79 cnt = 1; int pos = K; 80 for(int j=0;j
                        
                          0 && rightNum >= dis) pos = leftNum + dis; 88 else if(num[curPos] > 0 && rightNum < dis) pos = dis - rightNum; 89 else if(num[curPos] < 0 && leftNum >= dis) pos = leftNum - dis + 1; 90 else if(num[curPos] < 0 && leftNum < dis) pos = 2*leftNum + rightNum - dis + 1; 91 cnt ++; 92 } 93 for(int i=1;i<=N;i++)if(!no[i]) no[i] = N; 94 } 95 96 int isp[MAXN], yue[MAXN], D[MAXN], Max[MAXN]; 97 void init() 98 { 99 mem1(isp);yue[1] = 1;100 for(int i=2;i
                         
                           D[Max[i-1]]) Max[i] = i;120 else Max[i] = Max[i-1];121 }122 }123 124 int main()125 {126 //FOPENIN("in.txt");127 init();128 while(~scanf("%d %d%*c", &N, &K))129 {130 mem0(tree); mem0(no);131 buildTree(1, 1, N);132 for(int i=1;i<=N;i++)133 scanf("%s %d", name[i], &num[i]);134 getNo();135 for(int i=1;i<=N;i++) if(no[i] == Max[N])136 printf("%s %d\n", name[i], D[Max[N]]);137 }138 return 0;139 }

转载于:https://www.cnblogs.com/gj-Acit/p/3884816.html

你可能感兴趣的文章