BZOJ 2793: [Poi2012]Vouchers(调和级数)

Description

考虑正整数集合,现在有n组人依次来取数,假设第i组来了x人,他们每个取的数一定是x的倍数,并且是还剩下的最小的x个。 正整数中有m个数被标成了幸运数,问有哪些人取到了幸运数。

Input

第一行一个正整数m (m<=1,000,000),下面m行每行一个正整数x (x<=1,000,000),表示x是一个幸运数。 接下来一行一个正整数n (n<=1,000,000),下面n行每行一个正整数x (x<=1,000,000),表示这一组来了x个人。

Output

第一行输出一个非负整数k,表示k个人取到了幸运数,下面k行依次表示取到幸运数的人的编号,人按照来的顺序从1开始编号。

Sample Input

4 1 6 8 16 3 4 2 4

Sample Output

3 2 4 6

HINT

Hint 总共来了10个人,他们取走的数依次是4 8 12 16 2 6 20 24 28 32。 第2、4、6个人取到的是幸运数8、16、6。

(别把这题想太难,其实很水的)

Source

鸣谢Oimaster

我真傻,真的。

单知道这题是个大暴力就不用花半个小时去推式子。。。

还是太菜了QWQ....

我们用have[x]表示x的倍数已经枚举到了多少

然后对于每个询问暴力枚举就可以了。。起点是have[x]+x

时间复杂度

\dfrac {n}{1}+\dfrac {n}{2}+\ldots +\dfrac {n}{n}=n\log n

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#define int long long 
//#define getchar() (S == T && (T = (S = BB) + fread(BB, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
//char BB[1 << 15], *S = BB, *T = BB;
using namespace std;
const int MAXN=1e6+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int have[MAXN],take[MAXN],a[MAXN],limit=0;
int ans[MAXN],cnt=0;
main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    int N=read();
    for(int i=1;i<=N;i++) 
    {
        int x=read();
        limit=max(limit,x);
        a[x]=1;
    }
    int M=read();
    int now=0;
    while(M--)
    {
        int x=read(),t=x;
        for(int i=have[x]+x;i<=limit;i+=x)
        {
            if(!take[i])
            {
                now++;t--;
                take[i]=1;
                if(a[i]) ans[++cnt]=now;
            }
            have[x]=i;
            if(t==0) break;
        }
        now+=t;
    }
    printf("%lld\n",cnt);
    for(int i=1;i<=cnt;i++)
        printf("%lld\n",ans[i]);
    return 0;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

HDU4352 XHXJ's LIS(LIS 状压)

刚开始的思路是$f[i][j]$表示到第$i$位,LIS长度为$j$的方案。 然而发现根本不能转移,除非知道了之前的状态然后重新dp一遍。。

9930
来自专栏数据结构与算法

洛谷P1306 斐波那契公约数

题目描述 对于Fibonacci数列:1,1,2,3,5,8,13......大家应该很熟悉吧~~~但是现在有一个很“简单”问题:第n项和第m项的最大公约数是多...

35960
来自专栏数据结构与算法

HDU 5215 Cycle(dfs判环)

\(T\)组数据,给出\(n\)个点\(m\)条边的有向图,问是否存在一个奇环/偶环

10120
来自专栏数据结构与算法

洛谷P3128 [USACO15DEC]最大流Max Flow(树上差分)

边差分就是对边进行操作,我们在$u, v$除加上$val$,同时在$lca$处减去$2 * val$

13130
来自专栏Alan's Lab

iOS一点点 - TableView 拼音序排序(汉字转拼音、简繁体转换、日文转罗马音等)

Introduction to ICU General Transforms Transform Rule Tutorial 使用ICU进行拼音转汉字暂时似乎也...

36220
来自专栏数据结构与算法

2559. [NOIP2016]组合数问题

【题目描述】 【输入格式】    从文件中读入数据。    第一行有两个整数t, k,其中t代表该测试点总共有多少组测试数据,k的意义见【问题描述】。 ...

389100
来自专栏owent

POJ PKU 1990 MooFest 解题报告

6010
来自专栏数据结构与算法

cf1042F. Leaf Sets(贪心)

考场上想的贪心是对的:考虑一棵子树,如果该子树内最深的两个节点的距离相加$>k$就删掉最深的那个点,向上update的时候只返回最深的点的深度

17330
来自专栏编程

数控宏程序的编程及应用

1. 什么场合会用到宏程序编程? 其实说起来宏就是用公式来加工零件,比如说椭圆,如果没有宏的话,我们要逐点算出曲线上的点,然后慢慢来用直线逼近,如果是个光洁度要...

21180
来自专栏聊聊技术

原 "二分查找(Binary Search

437110

扫码关注云+社区

领取腾讯云代金券