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

Posted by 111qqz on Wednesday, September 21, 2016

TOC

poj 2886 题目链接

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

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

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

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

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

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

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

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

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

/* ***********************************************
Author :111qqz
Created Time :Wed 21 Sep 2016 09:19:11 PM CST
File Name :code/poj/2886.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=5E5+7;
int tree[N<<2];
int n,k;
char nam[N][11];
int val[N];
int 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};   
int 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};  
void PushUp( int rt)
{
    tree[rt] = tree[rt<<1] + tree[rt<<1|1];
}
void build( int l,int r,int rt)
{
    if (l==r)
    {
    tree[rt] = 1;
    return;
    }
    int m = (l+r)>>1;
    build(lson);
    build(rson);
    PushUp(rt);
}
int update( int p,int l,int r,int rt)
{
    if (l==r)
    {
    tree[rt]--;
    return l;
    }
    int m = (l+r)>>1;
    int ret;
    if (p<=tree[rt<<1]) ret = update(p,lson);
    else ret = update(p-tree[rt<<1],rson);
    PushUp(rt);
    return ret;
}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif
    while (~scanf("%d%d",&n,&k))
    {
        ms(tree,0);
        for ( int i = 1 ;i <= n ; i++) scanf("%s%d",nam[i],&val[i]);
        build(1,n,1);
        int id = upper_bound(s,s+40,n)-s-1; 
        int m = s[id];
        int ans = b[id];
        int num = n; //剩余人数
        int pos;
        for ( int i = 0 ; i < m ; i++)
        {
        num--;
        pos = update(k,1,n,1);
        if (num==0) break;
        if (val[pos]>=0) k = (k-1-1+val[pos])%num+1; //先-1变成0based,最后+1变回1_based.
        else k = ((k-1+val[pos])%num+num)%num+1;
        }
        printf("%s %d\n",nam[pos],ans);
    }
    return 0;
}

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

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

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int NN=500015;
const int N=500005;
int noprime[NN],table[NN][2];
int T;
void init(){
     ms(noprime,0);
     for (int i=1;i<=N;++i){
         for(int j=i;j<=N;j+=i)
                 ++noprime[j];
     }
     T=0;
     table[0][0]=1;
     table[0][1]=1;
     for (int i=2;i<=N;++i)
         if (noprime[i]>table[T][1]){
            table[++T][0]=i;
            table[T][1]=noprime[i];
         }
     ++T;
}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif

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

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付