╰(￣▽￣)╭

小 Z在玩一個 叫做《淘金者》的游戲。游戲的世界是一個 二維坐標(biāo) 。X軸、Y軸坐標(biāo)范圍均為1..N。初始的時候，所有的整數(shù)坐標(biāo)點(diǎn)上均有一塊金子，共 N*N 塊。

一陣風(fēng)吹過， 金子的位置發(fā)生了一些變化。細(xì)心的小Z發(fā)現(xiàn)， 初始 在(i, j) 坐標(biāo) 處的金子會變到 (f(i),f(j))坐標(biāo) 處。其中f(x)表示 x各位數(shù)字的乘積 ，例如 ，例如 f(99)=81，f(12)=2，f(10)=0。如果金子變化后的坐標(biāo)不在 1..N 的范圍內(nèi)，我們認(rèn)為這塊金子已經(jīng) 被移出游戲。 同時可以發(fā)現(xiàn)， 對于變化之后的游戲局面， 某些 坐 標(biāo)上的金子數(shù)量可能 不止一塊 ，而另外一些坐標(biāo)上可能已經(jīng)沒有金子 。這次變化 之后， 游戲?qū)⒉粫賹?金子的位置和數(shù)量進(jìn)行改變，玩家可以開始采集工作。

小 Z很懶 ，打算 只進(jìn)行 只進(jìn)行 K次采集 。每次采集可以得到某 一個坐標(biāo)上的所有 金子 ，采集之后該坐標(biāo)上的金子數(shù)變?yōu)?0。

現(xiàn)在小 Z希望知道，對于變化之后的游戲局面，在采集次數(shù)為K的前提下， 最多可以采集到少塊金子？

答案可能很大，小 Z希望得到1000000007 (10^ 9+7) 取模之后的答案。

(⊙ ▽ ⊙)

橫縱坐標(biāo)可以分開討論，
為什么？
f()函數(shù)只與其中某一個坐標(biāo)有關(guān)。

---

然后還要注意到一個性質(zhì)：
由于f()只會是0..9的數(shù)之積，所以質(zhì)因子只會有2,3,5,7。
這個性質(zhì)保證了，不同的積不會超過50000個，并且可以利用數(shù)位動態(tài)規(guī)劃預(yù)處理出：
這些積分別出現(xiàn)多少次。

---

現(xiàn)在考慮使用數(shù)位動態(tài)規(guī)劃求出這些積分別出現(xiàn)多少次a[]。
設(shè)fi,j,k,l,o,p表示，填了i位數(shù)，并且積為2j?3k?5l?7o，且當(dāng)前的i位數(shù)是否小于n的前i位（小于等于時p=0，否則p=1）。
容易轉(zhuǎn)移；
并且也很容易得出每個積分別出現(xiàn)多少次。（滿足條件的fi,j,k,l,o,p則對a[2j?3k?5l?7o]貢獻(xiàn)）

---

知道了a[]后，原問題變成找出前k最大的a[i]?a[j]；
做法：
首先對a[]從大到小排序，然后先把所有a[i]?a[1]?(i∈[1,len(a[])])放入線段樹的對應(yīng)位置；
顯然對線段樹進(jìn)行k次最值查詢；
每次查詢后得到最值的位置，把這一位第二項(xiàng)的a[]往后取一位。

(￣～￣)

#include<iostream> #include<algorithm> #include<stdio.h> #include<math.h> #define ll long long using namespace std; const char* fin="ex3216.in"; const char* fout="ex3216.out"; const ll inf=0x7fffffff; const ll maxn=60007,mo=1000000007,maxh=999997,maxt=maxn*8; ll n,m,i,j,k,l,o,p,index,J,K,L,O,P; ll A[maxn],len,ans; ll f[14][40][26][20][15][2],a[40][26][20][15]; struct node{ll x,y; }b[maxn]; bool cmp(node a,node b){return a.y>b.y; } ll h[maxh],d[maxh],num; ll hash(ll x){ll k=x%maxh;while (h[k] && h[k]!=x) k=(k+1)%maxh;return k; } ll c[maxt],cc[maxt]; void plant(ll l,ll r,ll t){ll mid=(l+r)/2;if (l==r){cc[t]=1;c[t]=b[l].y*b[1].y;return;}plant(l,mid,t*2);plant(mid+1,r,t*2+1);c[t]=max(c[t*2],c[t*2+1]); } ll getmax(ll l,ll r,ll t){ll mid=(l+r)/2,k;if (l==r){k=c[t];c[t]=b[l].y*b[++cc[t]].y;return k;}if (c[t*2]>c[t*2+1]) k=getmax(l,mid,t*2);else k=getmax(mid+1,r,t*2+1);c[t]=max(c[t*2],c[t*2+1]);return k; } int main(){char ch=getchar();n=0;while (ch<='9' && ch>='0') A[++len]=ch-'0',n=n*10+ch-'0',ch=getchar();for (i=1;i<=len/2;i++) swap(A[i],A[len-i+1]);scanf("%lld",&m);f[0][0][0][0][0][0]=1;a[0][0][0][0]=1;for (j=0;j<40;j++)for (k=0;k<26;k++)for (l=0;l<20;l++)for (o=0;o<15;o++){if (j) a[j][k][l][o]=a[j-1][k][l][o]*2;else if (k) a[j][k][l][o]=a[j][k-1][l][o]*3;else if (l) a[j][k][l][o]=a[j][k][l-1][o]*5;else if (o) a[j][k][l][o]=a[j][k][l][o-1]*7;if (a[j][k][l][o]>n) a[j][k][l][o]=n+1;}for (i=0;i<=len;i++)for (j=0;j<40;j++)for (k=0;k<26;k++)for (l=0;l<20;l++)for (o=0;o<15;o++)for (p=0;p<2;p++){if (i<len)for (index=1;index<=9;index++){ll tmp=index;J=K=L=O=P=0;if (index>A[i+1]) P=1;else if (index==A[i+1]) P=p;while (tmp%2==0) tmp/=2,J++;while (tmp%3==0) tmp/=3,K++;while (tmp%5==0) tmp/=5,L++;while (tmp%7==0) tmp/=7,O++;f[i+1][j+J][k+K][l+L][o+O][P]=(f[i+1][j+J][k+K][l+L][o+O][P]+f[i][j][k][l][o][p])%mo;}if (f[i][j][k][l][o][p]>0 && i>0 && (i<len || !p)){if (a[j][k][l][o]>n){continue;}ll tmp=hash(a[j][k][l][o]);if (!h[tmp]){h[tmp]=a[j][k][l][o];b[d[tmp]=++num].x=a[j][k][l][o];}b[d[tmp]].y+=f[i][j][k][l][o][p];}}sort(b+1,b+num+1,cmp);plant(1,num,1);for (i=1;i<=m;i++) ans=(ans+getmax(1,num,1))%mo;printf("%lld",ans);return 0; }

(⊙v⊙)

1.對于f(x)這種一元函數(shù)，可以單獨(dú)考慮和討論。
2.對積的質(zhì)因子敏感，例如本題，只有2,3,5,7這四個質(zhì)因子。

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

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的【JZOJ3216】【SDOI2013】淘金的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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