Lottery Gym - 102822L

題意：

有n個(gè)盒子，每個(gè)盒子有x個(gè)球，每個(gè)球的數(shù)值為2^a,問(wèn)最多能組成多少數(shù)？答案mod 1e9+7

題解：

二進(jìn)制思維題，濃濃的cf風(fēng)格
參考題解
我們將數(shù)按照冪次進(jìn)行排序（從小到大），然后對(duì)于每一位i，我們考慮下一位i+1的位置是否可以用第i位表示出來(lái)
比如：當(dāng)前位是（2，5），下一位是（4，1）
當(dāng)前位是有5個(gè)2²,下一位是2⁴,我們用4個(gè)2²就可以表示出2⁴，說(shuō)明第i+1位可以被第i位表示。然后我們把第i位所能表示第i+1位的數(shù)量加給原本第i+1位的數(shù)量，看第i+1位是否能表示第i+2位，依次類(lèi)推
如果可以被表示，我們就把第i位和第i+1位看作是一個(gè)連續(xù)的段，然后我們求出所有的段，把一個(gè)段內(nèi)的所有指數(shù)a都化解成這個(gè)段內(nèi)最小指數(shù)a_min，段內(nèi)相加，段與段之間乘積，得到答案
例子：
n=3 (1,3),(2,3),(4,1)
我們發(fā)現(xiàn)他們是一個(gè)連續(xù)的段內(nèi)，這個(gè)段內(nèi)最小的指數(shù)為1，所有都化成這個(gè)指數(shù)。（4，1）可以化成(2,4),加上原先的(2,3)有（2，7），（2，7）又可以化成(1,14),原先就有(1,3)，再加上題木允許什么也不選，所以最后答案就是：（1 * 4 +3） * 2+3+1
這是一個(gè)段的答案，如果有多個(gè)段，答案相乘(這個(gè)不選，每一段都可以這樣選)
為什么這樣？我也是看了其他人的題解才知道這個(gè)方法，但是為什么這樣做呢？
如果第i個(gè)位可以表示出第i+1個(gè)位，說(shuō)明第i個(gè)位和第i+1個(gè)位之間的數(shù)均可以表示，所以我們可以看作一段。我們將所有指數(shù)都化成該段最低位指數(shù)a_min，有x個(gè)a_min，而其能表示的數(shù)就是t * a_min , t屬于0~x，所以答案是x+1
段與段之間是獨(dú)立的，無(wú)法互相表示，所以不同段的結(jié)果乘積
比如有：(2,7)和(6,3)，分別屬于兩個(gè)段
(2,7)所能表示的是：4，8，12…28
(6,3)所能表示的是: 64,128,192
兩者可以彼此組合，且不會(huì)重復(fù)，如果會(huì)重復(fù)，按照性質(zhì)就會(huì)屬于一個(gè)段

另：
如果兩個(gè)相鄰的箱子的指數(shù)差距大于32的話(huà)，那么他們是一定不會(huì)組成相同段的，因?yàn)閤最多1e9個(gè)能滿(mǎn)足的a的差距就這么大了。

代碼:

#include<bits/stdc++.h> using namespace std; const int mod=1e9+7;struct Node{long long a,x; }a[100010]; long long b[100010]; bool cmp(Node a,Node b){return a.a<b.a; } long long q_pow(long a,long b){long long res = 1;a %= mod;while(b){if(b & 1) res = res * a % mod;a = a * a % mod;b >>=1 ;}return res; } int main(){int t;scanf("%d",&t);for(int ti=1;ti<=t;ti++){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].a,&a[i].x);sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++)b[i]=a[i].x;long long ans=1;for(int l=1,r;l<=n;l=r+1){r=l;// a[r+1].a-a[r].a表示指數(shù)差， (b[r]>>(a[r+1].a-a[r].a))為正說(shuō)明第r位可以表示第r+1位 while(r < n && (b[r]>>(a[r+1].a-a[r].a)) && a[r+1].a - a[r].a <= 32){//從l開(kāi)始求所有組成的最長(zhǎng)連續(xù)段 b[r+1]+=b[r]>>(a[r+1].a-a[r].a); //將第r位所能表示的第r+1位的數(shù)量加到原先第r+1位的數(shù)量 r++;}for(int i=r;i>l;i--){//對(duì)段內(nèi)的指數(shù)全部分解 a[i-1].x=(a[i-1].x+a[i].x*q_pow(2ll,a[i].a-a[i-1].a))%mod;}ans=ans*(a[l].x+1)%mod;}// printf("%lld\n",ans);printf("Case #%d: %lld\n",ti,ans);} }

總結(jié)

以上是生活随笔為你收集整理的Lottery Gym - 102822L的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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