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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1498: [NOI2006]神奇的口袋  

2014-07-16 23:20:00|  分类: oi,bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


我们神奇的发现把x[1],x[2]...x[n]映射到1,2,...n是等价的,所以直接算就好了嗯。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • const int maxn = 20000 ;

  •  

  • bool flag[ maxn + 10 ] ;

  • int p[ maxn ] , pn = 0 ;

  •  

  • inline void Init(  ) {

  •         memset( flag , true , sizeof( flag ) ) ;

  •         for ( int i = 2 ; i <= maxn ; ++ i ) if ( flag[ i ] ) {

  •                 p[ ++ pn ] = i ;

  •                 for ( int j = i << 1 ; j <= maxn ; j += i ) flag[ j ] = false ;

  •         }

  • }

  •  

  • inline int gcd( int x , int y ) {

  •         if ( x < y ) swap( x , y ) ;

  •         for ( int z ; y ; z = y , y = x % y , x = z ) ;

  •         return x ;

  • }

  •  

  • struct NUM {

  •         int cnt[ maxn ] ;

  •         NUM(  ) {

  •                 memset( cnt , 0 , sizeof( cnt ) ) ;

  •         }

  •         inline void add( int x ) {

  •                 for ( int i = 0 ; i ++ < pn ; ) if ( x == 1 ) break ; else

  •                 while ( ! ( x % p[ i ] ) ) {

  •                         ++ cnt[ i ] , x /= p[ i ] ;

  •                 }

  •         }

  • } n1 , n2 ;

  •  

  • struct Bignum {

  •         int n , a[ maxn ] ;

  •         inline void Init(  ) {

  •                 memset( a , 0 , sizeof( a ) ) ; a[ n = 1 ] = 1 ;

  •         }

  •         inline void mul( int x ) {

  •                 for ( int i = 0 ; i ++ < n ; ) a[ i ] *= x ;

  •                 for ( int i = 0 ; i ++ < n ; ) if ( a[ i ] >= 10 ) {

  •                         a[ i + 1 ] += a[ i ] / 10 ; a[ i ] %= 10 ;

  •                 }

  •                 while ( a[ n + 1 ] ) {

  •                         ++ n ;

  •                         if ( a[ n ] >= 10 ) {

  •                                 a[ n + 1 ] += a[ n ] / 10 ; a[ n ] %= 10 ;

  •                         } else break ;

  •                 }

  •         }

  •         inline void write(  ) {

  •                 for ( int i = n ; i ; -- i ) printf( "%d" , a[ i ] ) ;

  •         }

  • } m ;

  •  

  • inline void print( NUM &x ) {

  •         m.Init(  ) ;

  •         for ( int i = 0 ; i ++ < pn ; ) for ( int j = 0 ; j ++ < x.cnt[ i ] ; ) {

  •                 m.mul( p[ i ] ) ;

  •         }

  •         m.write(  ) ;

  • }

  •  

  • int n , t , d , a[ maxn ] , y[ maxn ] ;

  •  

  • int main(  ) {

  •         Init(  ) ;

  •         scanf( "%d%d%d" , &t , &n , &d ) ;

  •         int tot = 0 ;

  •         for ( int i = 0 ; i ++ < t ; ) {

  •                 scanf( "%d" , a + i ) ; tot += a[ i ] ;

  •         }

  •         int x ; for ( int i = 0 ; i ++ < n ; ) scanf( "%d%d" , &x , y + i ) ;

  •         for ( int i = 0 , g , px , py ; i ++ < n ; ) {

  •                 px = a[ y[ i ] ] , py = tot ; g = gcd( px , py ) ;

  •                 px /= g , py /= g ; n1.add( px ) , n2.add( py ) ;

  •                 a[ y[ i ] ] += d , tot += d ;

  •         }

  •         for ( int i = 0 ; i ++ < pn ; ) if ( n1.cnt[ i ] && n2.cnt[ i ] ) {

  •                 if ( n1.cnt[ i ] > n2.cnt[ i ] ) {

  •                         n1.cnt[ i ] -= n2.cnt[ i ] ; n2.cnt[ i ] = 0 ;

  •                 } else {

  •                         n2.cnt[ i ] -= n1.cnt[ i ] ; n1.cnt[ i ] = 0 ;

  •                 }

  •         }

  •         print( n1 ) ; printf( "/" ) ; print( n2 ) ; printf( "\n" ) ;

  •         return 0 ;

  • }


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

历史上的今天

评论

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

页脚

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