Codeforces #Round 376 部分题解

A:

题目传送门：http://codeforces.com/problemset/problem/731/A

直接根据题意模拟即可

 #include "bits/stdc++.h"

 using namespace std ;

 typedef long long QAQ ;

 char s[  ] ;

 inline int Calc ( const char x , const char y ) {

         if ( x > y ) return x - y ;

         else return y -x ;

 }

 inline int gmin ( int x , int y ) {

         return x > y ? y : x ;

 }

 int main ( ) {

         scanf ( "%s" , s +  ) ;

         int len = strlen ( s +  ) ;

         char now = 'a' ;

         QAQ Ans =   ;

         for ( int i= ; i<=len ; ++i ) {

                 char next = s[ i ] ;

                 int cost = gmin( Calc ( now , next ) ,  - Calc ( now , next ) ) ;

                 Ans += cost ;

                 now = s[ i ] ;

         }

         cout << Ans << endl ;

         return  ;

 } 

B:

题目传送门：http://codeforces.com/problemset/problem/731/B

贪心

 #include <iostream>

 #include <cstdio>

 #include <fstream>

 #include <sstream>

 using namespace std ;

 const int maxN = 2e5 + 1e3 ;

 const double eps = 1e- ;

 int arr [ maxN ] ;

 int INPUT ( ) {

         int x =  , f =  ; char ch = getchar ( ) ;

         while ( ch < '' || ch > '' ) { if ( ch == '-' ) f = - ; ch = getchar ( ) ; }

         while ( ch <='' && ch >= '' ){ x = ( x <<  ) + ( x <<  ) + ch - '' ; ch = getchar ( ) ; }

         return x * f ;

 }

 int main ( ) {

         int N = INPUT ( ) ;

         for ( int i= ; i<=N ; ++i ) {

                 arr[ i ] = INPUT ( ) ;

         }

         for ( int i= ; i<=N+ ; ++i ) {

                 if ( arr[ i ] <  ) {

                         goto Fail ;

                 }

                 if ( arr[ i ] %  ==  ){

                         -- arr[ i +  ] ;

                 }

         }

         cout << "YES" << endl ;

         goto End ;

         Fail :

                 cout << "NO" << endl ;

         End:

                 return  ;

 }

C:

题目传送门：http://codeforces.com/problemset/problem/731/C

将每个联通袜子分量加入一个冰炸鸡，用带权的冰炸鸡维护。最小染色数等于总共个数 - 颜色袜子最多的个数。

 #include "bits/stdc++.h"

 using namespace std ;

 const int maxN = 2e5 + 1e3 ;

 typedef long long QAQ ;

 int c[ maxN ] , t1[ maxN ] , t2[ maxN ] , father[ maxN ] , size[ maxN ] ;

 map <int ,int>mp[ maxN ] ;

 QAQ Ans ;

 int getfa ( const int x ) { return father[ x ] == x ? x : father[ x ] = getfa ( father[ x ] ) ; }

 inline int gmin ( const int x , const int y ) { return x > y ? y : x ; }

 inline int gmax ( const int x , const int y ) { return x > y ? x : y ; }

 void Set_Init ( const int n ) { for ( int i= ; i<=n ; ++i ) father[ i ] = i  , size[ i ] =  ; }

 inline void Union_Set ( int x , int y ) { father[ x ] = y ; size[ y ] += size [ x ] ; }

 inline int INPUT ( ) {

         int ret =  , f =  ; char ch = getchar( ) ;

         while ( ch < '' || '' < ch ) { if ( ch == '-' ) f = - ; ch = getchar ( ) ; }

         while ( '' <= ch && ch <= '' ) { ret = ( ret <<  ) + ( ret <<  ) + ch - '' ; ch = getchar ( ) ; }

         return ret * f ;

 }

 int main ( ) {

         int N = INPUT ( ) , M = INPUT ( ) , K = INPUT ( ) ;

         for ( int i= ; i<=N ; ++i )

                 c[ i ] = INPUT ( ) ;

         Set_Init ( N ) ;

         for ( int i= ; i<=M ; ++i ) {

                 t1[ i ] = INPUT ( ) , t2[ i ] = INPUT ( ) ;

                 int px = getfa ( t1[ i ] ) ;

                 int py = getfa ( t2[ i ] ) ;

                 if ( px != py ) Union_Set ( px , py ) ;

         }

         for ( int i= ; i<=N ; ++i ) ++mp[ getfa ( i ) ][ c[ i ] ] ;

         for ( int i= ; i<=N ; ++i ) {

                 if ( getfa ( i ) == i ) {

                         int temp =  ;

                         map <int , int>::iterator It ;

                         for ( It = mp[ i ].begin( ) ; It != mp[ i ].end ( ) ; ++It ) {

                                 temp = gmax( temp, It -> second ) ;

                         }

                         Ans += size[ i ] - temp ;

                 }

         }

         cout << Ans << endl ;

         return  ;

 }