BZOJ2793[Poi2012]Vouchers——枚举-白红宇

BZOJ2793[Poi2012]Vouchers——枚举

阅读量：7116 次

发布时间：2019-06-28

本文共 1258 字，大约阅读时间需要 4 分钟。

题目描述

考虑正整数集合，现在有n组人依次来取数，假设第i组来了x人，他们每个取的数一定是x的倍数，并且是还剩下的最小的x个。

正整数中有m个数被标成了幸运数，问有哪些人取到了幸运数。

输入

第一行一个正整数m (m<=1,000,000)，下面m行每行一个正整数x (x<=1,000,000)，表示x是一个幸运数。

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

输出

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

样例输入

样例输出

提示

总共来了10个人，他们取走的数依次是4 8 12 16 2 6 20 24 28 32。

第2、4、6个人取到的是幸运数8、16、6。

观察到幸运数大小<=10^6，那么我们只需要记录10^6之内的数就行了，每次取数后记录x的最小的倍数是多少，下一次再取x时直接从记录位置开始取就好了。当超过10^6时直接记录超过的数有多少个，不用求具体每个人取的是什么。

#include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;int b[1000010];int a[1000010];int n,m;long long cnt;int x;long long ans[1000010];int last[1000010];int num;int main(){ scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d",&x); a[x]=1; } b[0]=1; scanf("%d",&n); while(n--) { scanf("%d",&x); int j=x; int &i=last[x]; for(;j;j--) { while(b[i]&&i<=1000000) { i+=x; } if(i>1000000) { break; } b[i]=1; ++cnt; if(a[i]) { ans[++num]=cnt; } } cnt+=j; } printf("%d\n",num); for(int i=1;i<=num;i++) { printf("%lld\n",ans[i]); }}

转载于:https://www.cnblogs.com/Khada-Jhin/p/9591380.html

你可能感兴趣的文章