本文主要是介绍poj 2886 Who Gets the Most Candies?，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
单点更新，还有凡素数表，所谓反素数，
对于任何正整数x,起约数的个数记做g(x).例如g(1)=1,g(6)=4.
定义：如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数.
现在给一个N,求出不超过N的最大的反素数.
比如:输入1000 输出 840
思维过程:
求[1..N]中最大的反素数-->求约数最多的数
如果求约数的个数 756=2^2*3^3*7^1
(2+1)*(3+1)*(1+1)=24
基于上述结论,给出算法:按照质因数大小递增顺序搜索每一个质因子,枚举每一个质因子
为了剪枝:
性质一:一个反素数的质因子必然是从2开始连续的质数.
因为最多只需要10个素数构造:2,3,5,7,11,13,17,19,23,29
性质二:p=2^t1*3^t2*5^t3*7^t4.....必然t1>=t2>=t3>=....
题意： N个孩子围成一个圈，从第K个开始淘汰，每淘汰一个，出示手中的数字，决定下一个淘汰者，正数表示左手第n个，负数反之。每个人可以拿到的存活 回数 的因数个数的糖果，求拿到最多糖果数的孩子的名字以及糖果数。那么最大回数肯定是n次，那么找n内最大的反素数就好了
再根据线段树在这个回合为最大值得时候的原始位置求他的名字。。
就建个树，然后每次就把出来的那个位置标记为0，说明没人了//
然后根据现在他所在的位置求他原始位置，就出来了
代码如下：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
using namespace std;#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1const int N = 500100;
char name[N][11];
int val[N];int a[37]={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,500001};
int b[37]={1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,80,84,90,96,100,108,120,128,144,160,168,180,192,200,1314521};int sum[N<<2];void build(int l, int r, int rt)
{sum[rt] = r - l + 1;if (l == r) return ;int m = (l + r) >> 1;build(lson);build(rson);
}int query(int num, int l,int r,int rt)
{sum[rt]--;if (l == r){return l;}int m=(l+r)>>1;if (num <= sum[rt<<1]) return query(num,lson);return query(num-sum[rt<<1], rson);
}int main()
{int n, k;while (scanf("%d %d", &n, &k) != EOF){int i = 0, Max = 0, p = 0;while (a[i] <= n)i++;p = a[i-1];Max = b[i-1]; int h=n;build(1, n, 1);for (i = 1; i <= n; ++i){scanf("%s %d", &name[i], &val[i]);}int id;for (i = 0; i < p; ++i){n--;id = query(k,1,h,1);if (n == 0) break;if (val[id] > 0)k = (k-1+val[id]-1)%n+1;elsek = ((k-1+val[id])%n+n)%n+1;}printf("%s %d\n", name[id], Max);}return 0;
}
这篇关于poj 2886 Who Gets the Most Candies?的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
