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

GreenCloudS

 
 
 

日志

 
 

BZOJ-2396: 神奇的矩阵(随机判定)  

2014-06-18 22:42:00|  分类: oi,bzoj,矩阵乘法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


神奇的方法,随机出一个1*n的矩阵D,然后通过比较D*C和D*A*B来判定,多跑几次就可以A了。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <cstdlib>

  •  

  • using namespace std ;

  •  

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

  • #define check( ch ) ( ch >= '0' && ch <= '9' )

  •  

  • inline void getint( int &t ) {

  •     int ch ; for ( ch = getchar(  ) ; ! check( ch ) ; ch = getchar(  ) ) ;

  •     t = ch - '0' ;

  •     for ( ch = getchar(  ) ; check( ch ) ; ch = getchar(  ) ) t = t * 10 + ch - '0' ;

  • }

  •  

  • const int maxn = 1010 ;

  •  

  • int n , A[ maxn ][ maxn ] , B[ maxn ][ maxn ] , C[ maxn ][ maxn ] , D[ maxn ] , E[ maxn ] , F[ maxn ] ;

  •  

  • inline void mul( int a[] , int b[ maxn ][ maxn ] , int c[] ) {

  •     rep( i , n ) c[ i ] = 0 ;

  •     rep( i , n ) rep( j , n ) c[ i ] += a[ j ] * b[ j ][ i ] ;

  • }

  •  

  • inline bool cmp( int a[] , int b[] ) {

  •     rep( i , n ) if ( a[ i ] != b[ i ] ) return false ;

  •     return true ;

  • }

  •  

  • int main(  ) {

  •     srand( 12 ) ;

  •     while ( scanf( "%d" , &n ) != EOF ) {

  •         rep( i , n ) rep( j , n ) getint( A[ i ][ j ] ) ;

  •         rep( i , n ) rep( j , n ) getint( B[ i ][ j ] ) ;

  •         rep( i , n ) rep( j , n ) getint( C[ i ][ j ] ) ;

  •         bool flag = true ;

  •         rep( i , 11 ) {

  •             rep( j , n ) D[ j ] = rand(  ) % 10007 ;

  •             mul( D , A , F ) ; mul( F , B , E ) ; mul( D , C , F ) ;

  •             if ( ! cmp( E , F ) ) {

  •                 flag = false ; break ;

  •             }

  •         }

  •         printf( flag ? "Yes\n" : "No\n" ) ;

  •     }

  •     return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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