注册 登录  
 加关注

网易博客网站关停、迁移的公告:

将从2018年11月30日00:00起正式停止网易博客运营
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

3131: [Sdoi2013]淘金(数位统计+堆)  

2014-03-12 19:47:00|  分类: oi,bzoj,数位统计 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=3131


之前被wshjza问了这道题,然后突然发现自己傻叉地还不会数位统计(其实调起来真的挺恶心的),最后滚了水了半天的那种压缩前缀的方法,然后就继续滚水过掉了。(STL无敌!)


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <set>

  • #include <queue>

  •  

  • using namespace std ;

  •  

  • #define tset set < node > :: iterator

  • #define maxm 100100

  • #define rep( i , x ) for ( int i = 0 ; i < x ; ++ i )

  •  

  • typedef long long ll ;

  •  

  • const ll mod = 1000000007 ;

  •  

  • struct node {

  •      

  •     ll x , cnt ;

  •      

  •     node(  ) {

  •         cnt = 0 ;

  •     }

  •      

  •     node( ll _x , ll _cnt ) : x( _x ) , cnt( _cnt ) {

  •          

  •     }

  •      

  •     bool operator < ( const node &a ) const {

  •         return x < a.x ;

  •     }

  •      

  •     bool operator == ( const node &a ) const {

  •         return x == a.x ;

  •     }

  •      

  •     bool operator > ( const node &a ) const {

  •         return x > a. x ;

  •     }

  •      

  • };

  •  

  • set < node > bst[ 20 ] , pre[ 20 ] ;

  •  

  • ll n , N[ 20 ] ;

  • int k ;

  •  

  • void dfs( int now ) {

  •     if ( ! now ) {

  •         rep( i , N[ now ] ) pre[ now ].insert( node( i + 1 , 1 ) ) ;

  •         return ;

  •     }

  •     rep( i , N[ now ] ) {

  •         for ( tset p = bst[ now - 1 ].begin(  ) ; p != bst[ now - 1 ].end(  ) ; ++ p ) {

  •             node temp = *p ; temp.x *= ll( i ) ;

  •             if ( temp.x && temp.x <= n  ) {

  •                 tset ip = pre[ now ].find( temp ) ;

  •                 if ( ip == pre[ now ].end(  ) ) {

  •                     pre[ now ].insert( temp ) ;

  •                 } else {

  •                     temp.cnt += ip -> cnt ;

  •                     pre[ now ].erase( ip ) ;

  •                     pre[ now ].insert( temp ) ;

  •                 }

  •             }

  •         }

  •     }

  •     if ( N[ now - 1 ] ) {

  •         dfs( now - 1 ) ;

  •         for ( tset p = pre[ now - 1 ].begin(  ) ; p != pre[ now - 1 ].end(  ) ; ++ p ) {

  •             node temp = *p ; temp.x *= N[ now ] ;

  •             if ( temp.x && temp.x <= n  ) {

  •                 tset ip = pre[ now ].find( temp ) ;

  •                 if ( ip == pre[ now ].end(  ) ) {

  •                     pre[ now ].insert( temp ) ;

  •                 } else {

  •                     temp.cnt += ip -> cnt ;

  •                     pre[ now ].erase( ip ) ;

  •                     pre[ now ].insert( temp ) ;

  •                 }

  •             }

  •         }

  •     }

  • }

  •  

  • ll num[ maxm ] ;

  • int m = 0 ;

  •  

  • bool cmp( ll x , ll y ) {

  •     return x > y ;

  • }

  •  

  • void cal( ll x ) {

  •     int len = 0 ;

  •     for ( ; x ; x /= 10 ) N[ len ++ ] = x % 10 ;

  •     rep( i , len - 1 ) {

  •         bst[ i ].clear(  ) ;

  •         if ( ! i ) {

  •             rep( j , 9 ) bst[ i ].insert( node( j + 1 , 1 ) ) ;

  •         } else {

  •             for ( tset p = bst[ i - 1 ].begin(  ) ; p != bst[ i - 1 ].end(  ) ; ++ p ) {

  •                 node temp = *p ;

  •                 rep( j , 10 ) if ( temp.x * ll( j ) && temp.x * ll( j ) <= n ) {

  •                     node rec = temp ; rec.x = temp.x * ll( j ) ;

  •                     tset pi = bst[ i ].find( rec ) ;

  •                     if ( pi == bst[ i ].end(  ) ) {

  •                         bst[ i ].insert( rec ) ;

  •                     } else {

  •                         rec.cnt += pi -> cnt ;

  •                         bst[ i ].erase( pi ) ;

  •                         bst[ i ].insert( rec ) ;

  •                     }

  •                 }

  •             }

  •         }

  •     }

  •     rep( i , len ) pre[ i ].clear(  ) ;

  •     dfs( len - 1 ) ;

  •     rep( i , len - 1 ) {

  •         bst[ i ].clear(  ) ;

  •         if ( ! i ) {

  •             rep( j , 9 ) bst[ i ].insert( node( j + 1 , 1 ) ) ;

  •         } else {

  •             rep( j , 9 ) bst[ i ].insert( node( j + 1 , 1 ) ) ;

  •             for ( tset p = bst[ i - 1 ].begin(  ) ; p != bst[ i - 1 ].end(  ) ; ++ p ) {

  •                 node temp = *p ;

  •                 rep( j , 10 ) if ( temp.x * ll( j ) && temp.x * ll( j ) <= n ) {

  •                     node rec = temp ; rec.x = temp.x * ll( j ) ;

  •                     tset pi = bst[ i ].find( rec ) ;

  •                     if ( pi == bst[ i ].end(  ) ) {

  •                         bst[ i ].insert( rec ) ;

  •                     } else {

  •                         rec.cnt += pi -> cnt ;

  •                         bst[ i ].erase( pi ) ;

  •                         bst[ i ].insert( rec ) ;

  •                     }

  •                 }

  •             }

  •         }

  •     }

  •     if ( len - 1 ) for ( tset p = bst[ len - 2 ].begin(  ) ; p != bst[ len - 2 ].end(  ) ; ++ p ) {

  •         node temp = *p ;

  •         tset ip = pre[ len - 1 ].find( temp ) ;

  •         if ( ip == pre[ len - 1 ].end(  ) ) pre[ len - 1 ].insert( temp ) ;

  •         else {

  •             temp.cnt += ip -> cnt ;

  •             pre[ len - 1 ].erase( ip ) ;

  •             pre[ len - 1 ].insert( temp ) ;

  •         }

  •     }

  •     for ( tset p = pre[ len - 1 ].begin(  ) ; p != pre[ len - 1 ].end(  ) ; ++ p ) if ( p -> x ) {

  •         num[ m ++ ] = p -> cnt ;

  •     }

  •     sort( num , num + m , cmp ) ;

  • }

  •  

  • struct Node {

  •      

  •     int x , y ;

  •      

  •     Node( int _x , int _y ) : x( _x ) , y( _y ) {

  •          

  •     }

  •      

  •     bool operator < ( const Node &a ) const {

  •         return num[ x ] * num[ y ] < num[ a.x ] * num[ a.y ] ;

  •     }

  •      

  • };

  •  

  • priority_queue < Node > q ;

  •  

  • ll ans = 0 ;

  •  

  • void Solve(  ) {

  •     rep( i , m ) q.push( Node( i , 0 ) ) ;

  •     rep( i , k ) {

  •         if ( q.empty(  ) ) return ;

  •         Node temp = q.top(  ) ; q.pop(  ) ;

  •         ll rec = num[ temp.x ] % mod , ret = num[ temp.y ] % mod ;

  •         ( ans += ( ( rec * ret ) % mod ) ) %= mod ;

  •         if ( ( ++ temp.y ) < m ) q.push( temp ) ;

  •     }

  • }

  •  

  • int main(  ) {

  •     scanf( "%lld%d" , &n , &k ) ;

  •     if ( ! n || ! k ) {

  •         printf( "0\n" ) ; return 0 ;

  •     }

  •     cal( n ) ;

  •     Solve(  ) ;

  •     printf( "%lld\n" , ans ) ;

  •     return 0 ;

  • }



  评论这张
 
阅读(3)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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