toj_2959.cpp

Tianjin University Online Judge 的80多道题目 .

#include<cstdio>
#include<cstring>
#include<cstdlib>
#define MAXNUM 100010
int n , b , pOfB , a[ MAXNUM ];
int nOfD[ 2 ][ 2 ][ MAXNUM ];

int main()
{
    int i , j , k ,  larger , smaller , diff , num;
    
//    freopen( "toj_2959_in.txt" , "r" , stdin );
//    freoepn( "toj_2959_out.txt" , "w" , stdout );
    scanf( "%d%d" , &n , &b );
    for( i = 0; i < n; i++ ){
        scanf( "%d" , &a[ i ] );
        if( a[ i ] == b )
            pOfB = i;
    }
    memset( nOfD , 0 , sizeof( nOfD ) );
    nOfD[ 0 ][ 0 ][ 0 ] = nOfD[ 1 ][ 0 ][ 0 ] = 1;
    larger = 0;
    smaller = 0;
    for( i = pOfB - 1 ; i >= 0; i-- ){
        if( a[ i ] > b )
            larger++;
        else
            smaller++;
        diff = larger - smaller;
//        printf( "%d %d\n" , larger , smaller );
        if( diff >= 0 )
            nOfD[ 0 ][ 0 ][ diff ]++;
        else
            nOfD[ 0 ][ 1 ][ abs( diff ) ]++;
    }
    larger = 0;
    smaller = 0;
    for( i = pOfB + 1 ; i < n; i++ ){
        if( a[ i ] > b )
            larger++;
        else
            smaller++;
        diff = larger - smaller;

        if( diff >= 0 )
            nOfD[ 1 ][ 0 ][ diff ]++;
        else
            nOfD[ 1 ][ 1 ][ abs( diff ) ]++;
    }
//     for( i = 0; i < 2; i++ ){
//         for( j = 0; j < 2; j++ ){
//             for( k = 0; k < n; k++ )
//                 printf( "%d " , nOfD[ i ][ j ][ k ] );
//             printf( "\n" );
//         }
//         printf( "\n" );
//     }
    for( num = 0 , i = 1; i < n; i++ )
        for( j = 0; j < 2; j++ ){
            num += nOfD[ 0 ][ j ][ i ] * nOfD[ 1 ][ 1 - j ][ i ];
        }
    num += nOfD[ 0 ][ 0 ][ 0 ] * nOfD[ 1 ][ 0 ][ 0 ];
    printf( "%d\n" , num );
//    system( "pause" );
    return 0;
}