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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1407: [Noi2002]Savage(拓展欧几里德)  

2014-07-14 11:16:00|  分类: oi,bzoj,数论,拓 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


暴力枚举m,然后暴力枚举每一对(i,j)的野人,用拓展欧几里德算出他们会不会相遇。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • typedef int ll ;

  •  

  • const ll maxn = 16 ;

  •  

  • ll n , p[ maxn ] , c[ maxn ] , l[ maxn ] ;

  •  

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

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

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

  •     return x ;

  • }

  •  

  • void exgcd( ll a , ll b , ll &x , ll &y ) {

  •     if ( ! b ) {

  •         x = 1 , y = 0 ; return ;

  •     }

  •     ll tx , ty ; exgcd( b , a % b , tx , ty ) ;

  •     x = ty , y = tx - ( a / b ) * ty ;

  • }

  •  

  • inline bool check( ll i , ll j , ll m ) {

  •     if ( c[ i ] < c[ j ] ) swap( i , j ) ;

  •     ll A = ( p[ j ] - p[ i ] ) , B = m , C = c[ i ] - c[ j ] , v , g ;

  •     if ( A < 0 ) {

  •         A = - A , v = -1 ;

  •     } else v = 1 ;

  •     g = gcd( A , B ) ;

  •     if ( C % g ) return false ;

  •     ll x , y ;

  •     if ( A > B ) exgcd( A / g , B / g , x , y ) ; else exgcd( B / g , A / g , y , x ) ;

  •     x *= v , x *= ( C / g ) ;

  •     if ( x > 0 ) x %= ( B / g ) ;

  •     if ( x < 0 ) x += ( ( - x ) / ( B / g ) + ( ( - x ) % ( B / g ) > 0 ) ) * ( B / g ) ;

  •     return x <= l[ i ] && x <= l[ j ] ;

  • }

  •  

  • int main(  ) {

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

  •     ll maxc = 0 ;

  •     for ( ll i = 0 ; i ++ < n ; ) {

  •         scanf( "%d%d%d" , c + i , p + i , l + i ) ;

  •         maxc = max( maxc , c[ i ] -- ) ;

  •     }

  •     for ( ll m = maxc ; ; ++ m ) {

  •         bool flag = true ;

  •         for ( ll i = 1 ; i < n ; ++ i ) {

  •             for ( ll j = i + 1 ; j <= n ; ++ j ) if ( check( i , j , m ) ) {

  •                 flag = false ; break ;

  •             }

  •             if ( ! flag ) break ;

  •         }

  •         if ( flag ) {

  •             printf( "%d\n" , m ) ; break ;

  •         }

  •     }

  •     return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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