poj 2886 Who Gets the Most Candies? （线段树模拟加强版约瑟夫问题+反素数)

2016-09-21 · 2 min read · 反素数 线段树

poj 2886 题目链接

题意：n个人围成一圈，每个人身上由一个数，可正可负。从第k个人开始出圈，如果第k个人身上的数是X,X>0，就左边第x个没有出圈的人出圈，否则右边第-X个人出圈。 第k个人出圈得到的糖果数目为f(k)，f(x)表示x的因子个数。现在问谁能拿到最多的糖果，并且拿到了多少糖果。

思路：看起来好像很麻烦。。其实可以分解成两个问题。

第一个子问题就是约瑟夫问题的加强版。。。每次间隔不是定数，而取决与上一次出队的人。。。

终点是数据有5E5.。。模拟的话会炸掉。。。所以用线段树来模拟这个过程。。。

类似于那道插队的问题。。。线段树的域存的是某区间中空位置的数量。。初始为1.。。

然后每次update的时候优先查看左子树。。。

第二个子问题就是。。。到底第几个出去的人那道的糖果最多。。。。

其实也就是求1..n中。。。因子数最大的那个。。。

利用反素数表。。。每次upper_bound一下即可。。。

 1/* ***********************************************
 2Author :111qqz
 3Created Time :Wed 21 Sep 2016 09:19:11 PM CST
 4File Name :code/poj/2886.cpp
 5************************************************ */
 6#include <cstdio>
 7#include <cstring>
 8#include <iostream>
 9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=5E5+7;
32int tree[N<<2];
33int n,k;
34char nam[N][11];
35int val[N];
36int s[40] = {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};   
37int b[40] = {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};  
38void PushUp( int rt)
39{
40    tree[rt] = tree[rt<<1] + tree[rt<<1|1];
41}
42void build( int l,int r,int rt)
43{
44    if (l==r)
45    {
46	tree[rt] = 1;
47	return;
48    }
49    int m = (l+r)>>1;
50    build(lson);
51    build(rson);
52    PushUp(rt);
53}
54int update( int p,int l,int r,int rt)
55{
56    if (l==r)
57    {
58	tree[rt]--;
59	return l;
60    }
61    int m = (l+r)>>1;
62    int ret;
63    if (p<=tree[rt<<1]) ret = update(p,lson);
64    else ret = update(p-tree[rt<<1],rson);
65    PushUp(rt);
66    return ret;
67}
68int main()
69{
70	#ifndef  ONLINE_JUDGE 
71	freopen("code/in.txt","r",stdin);
72  #endif
73	while (~scanf("%d%d",&n,&k))
74	{
75	    ms(tree,0);
76	    for ( int i = 1 ;i <= n ; i++) scanf("%s%d",nam[i],&val[i]);
77	    build(1,n,1);
78	    int id = upper_bound(s,s+40,n)-s-1; 
79	    int m = s[id];
80	    int ans = b[id];
81	    int num = n; //剩余人数
82	    int pos;
83	    for ( int i = 0 ; i < m ; i++)
84	    {
85		num--;
86		pos = update(k,1,n,1);
87		if (num==0) break;
88		if (val[pos]>=0) k = (k-1-1+val[pos])%num+1; //先-1变成0based，最后+1变回1_based.
89		else k = ((k-1+val[pos])%num+num)%num+1;
90	    }
91	    printf("%s %d\n",nam[pos],ans);
92	}
93    return 0;
94}

顺便再来个打反素数以及对应约数的表。

/* ***********************************************
Author :111qqz
Created Time :Wed 21 Sep 2016 05:14:13 PM CST
File Name :anti-prime.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int NN=500015;
 7const int N=500005;
 8int noprime[NN],table[NN][2];
 9int T;
10void init(){
11     ms(noprime,0);
12     for (int i=1;i<=N;++i){
13         for(int j=i;j<=N;j+=i)
14                 ++noprime[j];
15     }
16     T=0;
17     table[0][0]=1;
18     table[0][1]=1;
19     for (int i=2;i<=N;++i)
20         if (noprime[i]>table[T][1]){
21            table[++T][0]=i;
22            table[T][1]=noprime[i];
23         }
24     ++T;
25}
26int main()
27{
28	#ifndef  ONLINE_JUDGE 
29	freopen("code/in.txt","r",stdin);
30  #endif

	init();
	for ( int i = 1 ; i <= T ; i++) printf("%d %d\n",table[i][0],table[i][1]);

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}