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

Description

考慮正整數(shù)集合，現(xiàn)在有n組人依次來(lái)取數(shù)，假設(shè)第i組來(lái)了x人，他們每個(gè)取的數(shù)一定是x的倍數(shù)，并且是還剩下的最小的x個(gè)。
正整數(shù)中有m個(gè)數(shù)被標(biāo)成了幸運(yùn)數(shù)，問(wèn)有哪些人取到了幸運(yùn)數(shù)。

?

Input

第一行一個(gè)正整數(shù)m (m<=1,000,000)，下面m行每行一個(gè)正整數(shù)x (x<=1,000,000)，表示x是一個(gè)幸運(yùn)數(shù)。
接下來(lái)一行一個(gè)正整數(shù)n (n<=1,000,000)，下面n行每行一個(gè)正整數(shù)x (x<=1,000,000)，表示這一組來(lái)了x個(gè)人。

?

Output

第一行輸出一個(gè)非負(fù)整數(shù)k，表示k個(gè)人取到了幸運(yùn)數(shù)，下面k行依次表示取到幸運(yùn)數(shù)的人的編號(hào)，人按照來(lái)的順序從1開(kāi)始編號(hào)。

?

Sample Input

4
1
6
8
16
3
4
2
4

Sample Output

3
2
4
6

HINT

?

Hint

總共來(lái)了10個(gè)人，他們?nèi)∽叩臄?shù)依次是4 8 12 16 2 6 20 24 28 32。

第2、4、6個(gè)人取到的是幸運(yùn)數(shù)8、16、6。

（別把這題想太難，其實(shí)很水的）

?

?

Source

鳴謝Oimaster

我真傻，真的。 單知道這題是個(gè)大暴力就不用花半個(gè)小時(shí)去推式子。。。 還是太菜了QWQ.... 我們用$have[x]$表示$x$的倍數(shù)已經(jīng)枚舉到了多少 然后對(duì)于每個(gè)詢問(wèn)暴力枚舉就可以了。。起點(diǎn)是$have[x]+x$ 時(shí)間復(fù)雜度 $\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 WIN32freopen("a.in","r",stdin);#else#endifint 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; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zwfymqz/p/8481187.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 2793: [Poi2012]Vouchers(调和级数)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。