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

 
 
 

日志

 
 

SDOI 2013 Day2 淘金 ( BZOJ3131 ) 数位DP  

2014-03-12 12:48:59|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
对于一道数位DP都没写过的我 此题真是神题
然后我还叫了不少oier一起来被此题虐
不过值得庆幸的是 我居然还是比他们先A掉的233
-------------------------------------------------------------------------------------------
以下是出题人写的题解
首先 x,y 坐标不相关。我们分别处理两者。
y=f(x)。y 只有 2、3、5、7  四个约数。在给定的 N 范围中,这种数的数量很小,大约只有
20000 个。我们设有 S 个。
第一步:生成所有的只有 2、3、5、7 约数的数:O(S)或者 O(S log S)。
第二步:对于每个只有 2、3、5、7 约数的数 A
i,求出 1..n 中有多少数各位数字乘积=A
i。
数位统计问题。可以使用 O(SlogN)预处理,每次 O(logN)的算法。 假设求得的结果是 num[i],
表示第 i 个数 1..n 中有多少数各位数字成绩等于它。
第三步:合并 x、y 坐标。也即求得 num[i]*num[j]的第 K 大。可以使用堆在 O(KlogS)的复杂
度内解决。
-------------------------------------------------------------------------------------------
以下是一些不错的链接
-------------------------------------------------------------------------------------------
最后是我自己的部分
首先表示如果情况不方便讨论的话 递归的记忆化搜索实现或许更方便
然后即使不用map的话 做些预处理来减少 if 代码也不会长多少
把数位DP的部分写好后 接下来的堆排就相对而言好写多了
不过有一个疑问就是 好像一开始枚举符合要求的那些数时
如果这样枚举就可以AC
for(long long t7=1,n7=0;t7<=n;t7*=7,++n7)
for(long long t5=t7,n5=0;t5<=n;t5*=5,++n5)
for(long long t3=t5,n3=0;t3<=n;t3*=3,++n3)
for(long long t2=t3,n2=0;t2<=n;t2<<=1,++n2)
{
        long long ans=trydoans(n2,n3,n5,n7);
        if(ans)arr[++ap]=ans;
 }
反过来的话就只能对前4组(小数据)
for(long long t2=1,n2=0;t2<=n;t2<<=1,++n2)
for(long long t3=t2,n3=0;t3<=n;t3*=3,++n3)
for(long long t5=t3,n5=0;t5<=n;t5*=5,++n5)
for(long long t7=t5,n7=0;t7<=n;t7*=7,++n7)
{
        long long ans=trydoans(n2,n3,n5,n7);
        if(ans)arr[++ap]=ans;
 }
这到底是什么情况额?
-------------------------------------------------------------------------------------------
  评论这张
 
阅读(171)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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