首页 > 代码库 > [bzoj4800][Ceoi2015]Ice Hockey World Championship
[bzoj4800][Ceoi2015]Ice Hockey World Championship
来自FallDream的博客,未经允许,请勿转载,谢谢。
有n个物品,m块钱,给定每个物品的价格,求买物品的方案数
n<=40 m<=10^18
考虑双向宽搜,然后得到两个大小为2^20的数组,排序之后两个指针推一推计算答案即可。
排序最好用基数排序
#include<iostream>#include<cstdio>#include<cstring>#define MN 40#define MM 1050000#define N 32767#define ll unsigned long longusing namespace std;inline ll read(){ ll 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 n,lim,tot1=0,tot2=0,v[4][N+5];ll a[MN+5],s[MM+5],s2[MM+5],m,sa[MM+5],ans=0;void Dfs2(int x,ll y){ if(x==lim){s2[++tot2]=y;return;} if(y+a[x]<=m) Dfs2(x-1,y+a[x]); Dfs2(x-1,y); }void Dfs1(int x,ll y){ if(x>lim){s[++tot1]=y;return;} if(y+a[x]<=m)Dfs1(x+1,y+a[x]); Dfs1(x+1,y);}void Sort(ll*s,int n){ memset(v,0,sizeof(v));// for(int i=1;i<=n;++i) cout<<s[i]<<" ";puts(""); for(int i=1;i<=n;++i) for(ll j=s[i],i=0;i<4;j>>=15,++i) ++v[i][j&N]; for(int r=0;r<4;++r) for(int i=1;i<=N;++i) v[r][i]+=v[r][i-1]; for(ll r=0,j=N;r<4;++r,j<<=15) { for(register int i=n;i;--i) sa[v[r][(s[i]&j)>>(r*15)]--]=s[i]; for(register int i=1;i<=n;++i) s[i]=sa[i]; } }int main(){ n=read();lim=n>>1;m=read(); for(int i=1;i<=n;++i) a[i]=read(); Dfs1(1,0);Dfs2(n,0); Sort(s,tot1);Sort(s2,tot2); for(int i=tot1,j=1;i;--i) { while(j<tot2&&s2[j+1]+s[i]<=m) ++j; if(s2[j]+s[i]<=m) ans+=j; } printf("%lld\n",ans); return 0;}
[bzoj4800][Ceoi2015]Ice Hockey World Championship
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。