注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3131][Sdoi2013]淘金  

2015-03-18 20:40:27|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3131: [Sdoi2013]淘金

做过类似的题……
我是乱写的,代码错了不要找我
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
ll n;
int ans,m,fn;
ll list[30];
struct Node{int a;ll b;Node(int aa=0,ll bb=0){a=aa;b=bb;}};
bool operator < (const Node&a,const Node&b){
if(a.a!=b.a)return a.a<b.a;
return a.b < b.b;
}
queue<Node>dui,wait;
map<Node,ll>f[30];
ll fin[(int)(1e4+10)];
void update(int i,Node next,ll val){
if(next.b > n)return;
if(!f[i].count(next)){
wait.push(next);
f[i][next]=val;
}else f[i][next] += val;
}
void solve(ll x){
int i,j,zero=0;ll zval;
for(list[0]=0;x;x/=10)list[++list[0]] = x%10;
//for(i=1;i*2<=list[0];i++)swap(list[i],list[list[0]-i+1]);
dui.push(Node(0,1));
f[list[0]+1][Node(0,1)]=1;
for(i=list[0];i;i--){
while(!dui.empty()){
Node now = dui.front();dui.pop();
//printf("[%d]%d %lld\n",i,now.a,now.b);
ll fn = f[i+1][now];
for(j=1;j<=9;j++)
if(!now.a){//0
if(j<list[i]){
update(i,Node(1,now.b*j),fn);
}else if(j==list[i]){
update(i,Node(0,now.b*j),fn);
}else break;
}else{//1
update(i,Node(1,now.b*j),fn);
}
}
//0
if(i>1)update(i,Node(1,1), 1);
while(!wait.empty()){
Node now = wait.front();wait.pop();
if(i==1 && !now.a)zero = now.b,zval=f[i][now];
dui.push(now);
}
}
while(!dui.empty()){
Node now = dui.front();dui.pop();
if(now.a==0)continue;
fin[++fn] = f[1][now];
if(now.b == zero)fin[fn] += zval,zero=0;
}
if(zero)fin[++fn] = zval;
}
struct Data{Data(int aa=0,ll v=0){a=aa;b=1;val=v;}int a,b;ll val;};
bool operator < (const Data&a,const Data&b){return a.val < b.val;}
priority_queue<Data>dd;
bool rcmp(ll a,ll b){return a>b;}
int main(){
//freopen("in.txt","r",stdin);
int i,j;
cin >> n >> m;
solve(n);
sort(fin+1,fin+1+fn,rcmp);
for(i=1;i<=fn;i++){
dd.push(Data(i,fin[i]*fin[1]));
}
//cout << fn<<' ' << fin[1] << endl;
while(m--){
if(dd.empty())break;
Data now = dd.top();dd.pop();
ans = (ans + now.val)%MOD;
now.b++;
if(now.b > fn)continue;
now.val = fin[now.a]*fin[now.b];
dd.push(now);
}
printf("%d\n",ans);
return 0;
}

题解:
数位DP
首先DP处理出来对于固定的j,满足f[i]=j的i的个数。
因为i个数>0的j非常少(<1e4),所以直接用map暴力dp
然后对于个数排序,用堆贪心选就好了

需要注意K<=N^2而不是有意义j个数的平方,所以有可能有意义的值选完了还不够K个
  评论这张
 
阅读(337)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017