BZOJ 2793: [Poi2012]Vouchers(调和级数)
程序员文章站
2022-07-10 17:55:21
Description 考虑正整数集合,现在有n组人依次来取数,假设第i组来了x人,他们每个取的数一定是x的倍数,并且是还剩下的最小的x个。正整数中有m个数被标成了幸运数,问有哪些人取到了幸运数。 考虑正整数集合,现在有n组人依次来取数,假设第i组来了x人,他们每个取的数一定是x的倍数,并且是还剩下 ......
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
1
6
8
16
3
4
2
4
Sample Output
3
2
4
6
2
4
6
HINT
Hint
总共来了10个人,他们取走的数依次是4 8 12 16 2 6 20 24 28 32。
第2、4、6个人取到的是幸运数8、16、6。
(别把这题想太难,其实很水的)
Source
我真傻,真的。
单知道这题是个大暴力就不用花半个小时去推式子。。。
还是太菜了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; }
上一篇: 菜鸟玩注入之找后台篇