「BZOJ2793」[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
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。
（别把这题想太难，其实很水的）
题解
一开始想错了真是逗。。。
其实就是只要考虑1-100w的数，然后mn[x]记录x的倍数取到了mn[x]，下次取x的倍数就从mn[x]+x开始。。。
这复杂度是nlogn的貌似
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<algorithm> #include<queue> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int m,n,mx,tot; int mn[1000005]; ll cnt,ans[1000005]; bool lucky[1000005],Get[1000005]; void solve() { while(n--) { int x=read(),t=x; for(int j=mn[x]+x,k=0;j<=mx;j+=x) { if(!Get[j]) { cnt++;t--; Get[j]=1;k++; if(lucky[j])ans[++ans[0]]=cnt; if(k==x)break; } mn[x]=j; } cnt+=t; } } int main() { m=read(); for(int i=1;i<=m;i++) { int x=read(); lucky[x]=1; mx=max(mx,x); } n=read(); solve(); printf("%lld\n",ans[0]); for(int i=1;i<=ans[0];i++) printf("%lld\n",ans[i]); return 0; } |
Subscribe
计数器 9788925
OI 课件=>
OI 课件=>