呃，先说一下比赛是的情况，我们是分开读题的，我负责从后面开始读，读完最后一题，感觉在poj上见过一道相似的题，那是一道复杂模拟，当时觉得这题应该也是道模拟题，但是自己的代码能力实在太差，所以决定在ZJH做完后给他说下题意，但没想到直到最后这题也没人过，所以也就没说。然后是倒数第二题，这题让我不得不再次正视自己的英语，唉，明明知道这题就是根据给出的公式进行计算，但就是没看到p(r)是怎么定义的，失败啊，过后看了解题报告，果然如此~再然后是第三题，没来得及细看，XH就让我读一下第一题，看了一下第一题过的人挺多，但是最后我们都没能过掉，题意倒是读懂了，可是没有思路啊，再然后，看到1005 、1006 过的人挺多的，然后读这两题，读完题，ZJH去做第六题了，然后我们就开始想1005 ，然后悲剧就开始了，其实1005题意很好懂，但是卡时间，在剩下的时间中我一直在，能不能有一种方法，只用两重循环就能遍历出来，但直到比赛结束也没想出来，唉，悲剧的比赛啊~~
比完赛就看了1005的解题报告，不过觉得很麻烦，然后看了下面的留言，有一个大牛给出一个相当简单的方法，然后我就在一分钟后A了~~
代码：
View Code
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <algorithm> #include <math.h> #define N 20002 #define M 80000 using namespace std ; int sum[N] ; int main() { int cas , n , i , j ; char str[N] ; scanf( "%d" ,&cas ); for ( int c = 1 ; c <= cas ; c++ ) { scanf( "%d" , &n ); getchar(); memset( sum , 0 , sizeof ( sum )) ; for ( i = 1 ; i <= n ; i++ ) { scanf( "%s" , str ); getchar(); for ( j = 0 ; j < n ; j++ ) { if( str[j] == '1' ) sum[i]++ ; } } sort( sum , sum + n + 1 ); int flag = 0 ; for( i = 2 ; i <= n ; i++ ) { if ( sum[i] == sum[i-1] ) { flag = 1 ; break ; } } printf ( "Case #%d: " ,c ); if ( flag ) printf( "Yes\n" ); else printf ( "No\n" ); } return 0 ; }
从第一开始看，发现第一题竟然一句话解决了，就是求最大公约数，呃，我太无知了！！
代码:
View Code
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <algorithm> #include <math.h> #define N 20002 #define M 80000 using namespace std ; typedef long long ll ; ll gcd( ll x , ll y ) { if ( !y ) return x ; else return gcd( y , x % y ); } int main() { int cas , c ; ll x , y , z ; scanf ( "%d" ,&cas ); for ( c = 1 ; c <= cas ; c++ ) { cin>>x>>y ; z = gcd( x , y ); while( z > 1 ) { x /= z ; z = gcd( x , y ); } printf( "Case #%d: " , c ); if ( x == 1 ) printf( "YES\n" ); else printf( "NO\n" ); } return 0 ; }
然后是倒数第二题，看了解题报告上的讲解，然后A了。
代码：
View Code
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <algorithm> #include <map> #include <sstream> #define N 10004 #define M 103 using namespace std ; char str1[M][N] , str2[M][N] ; double cal( char st1[] , char st2[] ) { int num , rank , id ; double ave ; string ss ; map<string , int>mark ; istringstream a( st1 ); istringstream b( st2 ); num = rank = id = 0 ; ave = 0.0 ; mark.clear(); a>>ss; while( a>>ss ) { mark[ss] = 1 ; num++ ; } b>>ss ; while( b>>ss ) { rank++; if ( mark[ss] ) { id++ ; ave += ( 1.0 * id / rank ); } } return ave / num ; } int main() { int cas , n , i , j ; double ans ; scanf( "%d" , &cas ); for ( j = 1 ; j <= cas ; j++ ) { scanf( "%d" , &n ); getchar(); for ( i = 0 ; i < n ; i++ ) gets( str1[i] ); for( i = 0 ; i < n ; i++ ) gets( str2[i] ); ans = 0.0 ; for( i = 0 ; i < n ; i++ ) ans += cal( str1[i] , str2[i] ); printf( "Case #%d: %lf\n" , j , ans / n ); } return 0 ; }
再然后是1006 ，看报告是一道裸地线段树，又练了一遍自己的线段树，不过用到了离散化。
代码：
View Code
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <algorithm> #include <queue> #include <math.h> #define N 100005 using namespace std ; struct point { int lc ; int rc ; int num ; }p[12*N] ; int s[N] , t[N] , q[N] , data[3*N] ; int n , m , cnt ; void make_tree( int index , int l , int r ) { p[index].lc = l ; p[index].rc = r ; p[index].num = 0 ; if( l == r ) return ; int mid = ( r + l ) / 2 ; make_tree( 2 * index , l , mid ) ; make_tree( 2 * index + 1 , mid + 1 , r ); } int find( int x ) { int l = 1 ; int r = cnt ; int mid ; while ( l <= r ) { mid = ( l + r ) / 2 ; if ( data[mid] == x ) return mid ; else if ( data[mid] > x ) r = mid - 1 ; else l = mid + 1 ; } return -1 ; } void update( int index , int l , int r , int val ) { if ( l <= p[index].lc && p[index].rc <= r ) { p[index].num += val ; return ; } int mid = ( p[index].lc + p[index].rc ) / 2 ; if ( l <= mid ) update( 2*index , l , r , val ); if ( r > mid ) update( 2*index + 1 , l , r , val ); } int query ( int index , int val ) { if ( p[index].lc == p[index].rc ) return p[index].num ; int mid = ( p[index].lc + p[index].rc ) / 2 ; if ( p[index].num ) { p[2*index].num += p[index].num ; p[2*index+1].num += p[index].num ; p[index].num = 0 ; } if ( val <= mid ) return query( 2*index , val ); else return query( 2*index + 1 , val ) ; } int main() { int cas , c , i ; scanf( "%d" , &cas ); for ( c = 1 ; c <= cas ; c++ ) { scanf( "%d%d" , &n , &m ); for ( i = 1 ; i <= n ; i++ ) { scanf( "%d%d" , &s[i] , &t[i] ); data[i] = s[i] ; data[n+i] = t[i]; } for ( i = 1 ; i <= m ; i++ ) { scanf( "%d" , &q[i] ); data[2*n+i] = q[i] ; } sort( data + 1 , data + 2 * n + m + 1 ); cnt = 1; for ( i = 1 ; i <= 2 * n + m ; i++ ) if ( data[i] != data[cnt] ) data[++cnt] = data[i] ; make_tree( 1 , 1 , cnt ); for ( i = 1 ; i <= n ; i++ ) { update( 1 , find ( s[i] ) , find( t[i] ) , 1 ); } printf( "Case #%d:\n" , c ); for ( i = 1 ; i <= m ; i++ ) { printf ( "%d\n" , query( 1 , find( q[i] ))) ; } } return 0 ; }