首页 > 代码库 > 淘金(bzoj 3131)
淘金(bzoj 3131)
Description
小Z在玩一个叫做《淘金者》的游戏。游戏的世界是一个二维坐标。X轴、Y轴坐标范围均为1..N。初始的时候,所有的整数坐标点上均有一块金子,共N*N块。
一阵风吹过,金子的位置发生了一些变化。细心的小Z发现,初始在(i,j)坐标处的金子会变到(f(i),fIj))坐标处。其中f(x)表示x各位数字的乘积,例如f(99)=81,f(12)=2,f(10)=0。如果金子变化后的坐标不在1..N的范围内,我们认为这块金子已经被移出游戏。同时可以发现,对于变化之后的游戏局面,某些坐标上的金子数量可能不止一块,而另外一些坐标上可能已经没有金子。这次变化之后,游戏将不会再对金子的位置和数量进行改变,玩家可以开始进行采集工作。
小Z很懒,打算只进行K次采集。每次采集可以得到某一个坐标上的所有金子,采集之后,该坐标上的金子数变为0。
现在小Z希望知道,对于变化之后的游戏局面,在采集次数为K的前提下,最多可以采集到多少块金子?
答案可能很大,小Z希望得到对1000000007(10^9+7)取模之后的答案。
Input
共一行,包含两介正整数N,K。
Output
一个整数,表示最多可以采集到的金子数量。
Sample Input
1 2 5
Sample Output
18
HINT
N < = 10^12 ,K < = 100000
对于100%的测试数据:K < = N^2
/* 数位DP+堆 这个题比较显然的做法是求出一维的转移,然后再用堆求出二维的前K大,问题是数据太大,无法直接求一维的。 我们可以发现,最大的积在10000左右,所以可以先dfs出所有可能的积,然后用数位DP求出积的个数。 f[i][j][k]表示填了i为,积为j,下一维能否任意填数的方案数。 */ #include<cstdio> #include<algorithm> #include<iostream> #include<queue> #define mod 1000000007 #define lon long long #define N 400010 using namespace std; lon n,k,a[N],len,dis[N],cnt,size[N],num[N],f[15][N][2]; struct node{ lon x,y,val; node(lon a,lon b){x=a;y=b;val=size[num[a]]*size[num[b]];} bool operator<(node s1) const{ return val<s1.val; } };priority_queue<node> q; lon read(){ lon num=0,flag=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)flag=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=num*10+c-‘0‘;c=getchar();} return num*flag; } bool cmp(int a,int b){return size[a]>size[b];} void dfs(lon last,lon dep,lon now){ if(dep==len+1){ dis[++cnt]=now; return; } if(!now) return; for(lon i=last;i<10;i++) dfs(i,dep+1,now*i); } int main(){ n=read();k=read(); while(n){ a[++len]=n%10; n/=10; } dfs(0,0,1); dis[++cnt]=0; sort(dis+1,dis+cnt+1); cnt=unique(dis+1,dis+cnt+1)-dis-1; f[0][2][0]=1; for(lon i=0;i<=len;i++) for(lon j=1;j<=cnt;j++) for(lon l=0;l<2;l++) if(f[i][j][l]){ lon p=(i==0?0:1); for(;p<10;p++){ f[i+1][lower_bound(dis+1,dis+cnt+1,dis[j]*p)-dis][l+p>a[i+1]]+=f[i][j][l]; } } for(lon i=1;i<=cnt;i++){ num[i]=i; for(lon j=1;j<len;j++) size[i]+=f[j][i][0]+f[j][i][1]; size[i]+=f[len][i][0]; } sort(num+2,num+cnt+1,cmp); q.push(node(2,2)); lon i=0,ans=0; while(!q.empty()){ node temp=q.top(); q.pop(); ans=(ans+temp.val)%mod; i++; if(i>=k) break; if(temp.x!=temp.y){ ans=(ans+temp.val)%mod; i++; if(i>=k) break; } if(temp.x!=temp.y) q.push(node(temp.x+1,temp.y)); if(temp.x==2) q.push(node(temp.x,temp.y+1)); } cout<<ans; return 0; }
淘金(bzoj 3131)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。