专栏首页饶文津的专栏【POJ 2886】Who Gets the Most Candies?

【POJ 2886】Who Gets the Most Candies?

约瑟夫问题的升级版,每次出去的是前一个出去的人位置+手上的数字(正往前,负往后)。第i个出去的人拿的糖是i的约数的个数。求拿糖最多的人和他的糖果数。

分析

线段树单点更新,反素数。

我竟然WA在了反素数少了几个QAQ

代码

#include<cstdio>
#include<cstring>
#define N 500002
#define mid int m=l+((r-l)>>1)
#define lson l,m,node<<1
#define rson m+1,r,node<<1|1
using namespace std;

int v[N];
char name[N][13];
int n,k;
int sum[N<<2];

int rprim[50]= {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,554400};//反素数
int nprim[50]= {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,216};//反素数的约数个数

void build(int l,int r,int node)
{
    sum[node]=r-l+1;//sum储存这个区间有多少个数
    if(l<r)
    {
        mid;
        build(lson);
        build(rson);
    }
}
int out(int l,int r,int node,int k)
{
    sum[node]--;//这个区间减少一个数
    if(l==r)
        return l;//返回这个减少的数的原始下标
    mid;
    if(k<=sum[node<<1])//要找的第k个数小于等于左半区间的个数
        return out(lson,k);//就递归左子树
    else
        return out(rson,k-sum[node<<1]);//否则就在右子树,且k-左子树的个数
}
int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        memset(name,0,sizeof(name));//清空名字
        for(int i=1; i<=n; i++)
            scanf("%s%d",name[i],&v[i]);
        build(1,n,1);

        int tn=n,now,p=0;
        while(rprim[p]<=n)p++;//找出n里最大的反素数

        for(int i=1; i<rprim[p-1]; i++)//反素数前的都出队
        {
            now=out(1,n,1,k);//当前出队的序号
            tn--;//剩下的人数
            if (v[now]>0)//向前数
                k=(k-1+v[now])%tn;//先减去本身这个位置 然后往前v个 再取模
            else
                k=((k+v[now])%tn+tn)%tn;//直接往后 然后要取模再取模保证正数
            if (k==0) k=tn;//如果刚好是tn 取模会变成0
        }
        now=out(1,n,1,k);//得到第最大的反素数个出队的人的序号
        printf("%s %d\n",name[now],nprim[p-1]);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 归并排序算法

    饶文津
  • 【hihocoder 1424】 Asa's Chess Problem(有源汇上下界网络流)

    饶文津
  • 【POJ 3321】Apple Tree

    有n个节点以1为根节点的树,给你树的边关系u-v,一开始每个节点都有一个苹果,接下来有两种操作,C x改变节点x的苹果状态,Q x查询x为根的树的所有苹果个数。

    饶文津
  • 151. [USACO Dec07] 建造路径

    ★★   输入文件:roads.in   输出文件:roads.out 简单对比 时间限制:1 s   内存限制:128 MB 译 by CmYkRgB12...

    attack
  • C# Tryparse的用法

    int.TryParse(n1.Text, out P_int_Number) 其中第一个参数代表被转换的参数,第二个参数为转换后的参数 int类型,成功返回T...

    zls365
  • 图论算法模板整理及思路 不断更新 绝对精品

    DFS 1 #include<iostream> 2 #include<queue> 3 #include<cstdio> 4 using nam...

    attack
  • 不引入新的数组,实现数组元素交换位置函数

             最近遇到一道C++的面试题,要求不引入新的数组,实现数组元素交换位置函数,看似挺简单的,却还是花费了我不少时间,这里记录下来,给大家一个简单的...

    用户1221057
  • 最大连续子序列和(最大子数组和)四种最详细的解法

    解法1:穷举暴力法 枚举左端点跟右端点,然后遍历更新所有的子序列和,最终得到结果就是最大的

    杨鹏伟
  • 洛谷P1251 餐巾计划问题(最小费用最大流)

    从$S$向$i'$连边$(p, INF)$,表示每天早上可以以$p$的费用无限提供餐巾

    attack
  • Noip 2016 Day1 题解

    老师让我们刷历年真题, 然后漫不经心的说了一句:“你们就先做做noip2016 day1 吧” 。。。。。。 我还能说什么,,,,,老师你这是明摆着伤害我们啊2...

    attack

扫码关注云+社区

领取腾讯云代金券