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

2018-06-17 21:09:15来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

Time Limit: 20 Sec  Memory Limit: 64 MB
Submit: 582  Solved: 250
[Submit][Status][Discuss]

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;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:POJ 1523 SPF(tarjan求割点)

下一篇:Jewel Magic UVA - 11996