首页 > 代码库 > Codeforces #Round 376 部分题解
Codeforces #Round 376 部分题解
A:
题目传送门:http://codeforces.com/problemset/problem/731/A
直接根据题意模拟即可
1 #include "bits/stdc++.h" 2 3 using namespace std ; 4 typedef long long QAQ ; 5 6 char s[ 1010 ] ; 7 8 inline int Calc ( const char x , const char y ) { 9 if ( x > y ) return x - y ;10 else return y -x ; 11 }12 13 inline int gmin ( int x , int y ) {14 return x > y ? y : x ; 15 }16 17 int main ( ) {18 scanf ( "%s" , s + 1 ) ;19 int len = strlen ( s + 1 ) ;20 21 char now = ‘a‘ ;22 QAQ Ans = 0 ;23 for ( int i=1 ; i<=len ; ++i ) {24 char next = s[ i ] ;25 int cost = gmin( Calc ( now , next ) , 26 - Calc ( now , next ) ) ;26 Ans += cost ; 27 now = s[ i ] ;28 }29 cout << Ans << endl ; 30 return 0 ; 31 }
B:
题目传送门:http://codeforces.com/problemset/problem/731/B
贪心
1 #include <iostream> 2 #include <cstdio> 3 #include <fstream> 4 #include <sstream> 5 6 using namespace std ; 7 const int maxN = 2e5 + 1e3 ; 8 const double eps = 1e-5 ; 9 10 int arr [ maxN ] ;11 12 int INPUT ( ) {13 int x = 0 , f = 1 ; char ch = getchar ( ) ;14 while ( ch < ‘0‘ || ch > ‘9‘ ) { if ( ch == ‘-‘ ) f = -1 ; ch = getchar ( ) ; } 15 while ( ch <=‘9‘ && ch >= ‘0‘ ){ x = ( x << 1 ) + ( x << 3 ) + ch - ‘0‘ ; ch = getchar ( ) ; } 16 return x * f ;17 }18 19 int main ( ) {20 int N = INPUT ( ) ;21 for ( int i=1 ; i<=N ; ++i ) {22 arr[ i ] = INPUT ( ) ;23 }24 for ( int i=1 ; i<=N+1 ; ++i ) {25 if ( arr[ i ] < 0 ) {26 goto Fail ;27 }28 if ( arr[ i ] % 2 == 1 ){29 -- arr[ i + 1 ] ;30 }31 }32 cout << "YES" << endl ;33 goto End ; 34 Fail :35 cout << "NO" << endl ; 36 End:37 return 0 ;38 }
C:
题目传送门:http://codeforces.com/problemset/problem/731/C
将每个联通袜子分量加入一个冰炸鸡,用带权的冰炸鸡维护。最小染色数等于总共个数 - 颜色袜子最多的个数。
1 #include "bits/stdc++.h" 2 3 using namespace std ; 4 const int maxN = 2e5 + 1e3 ; 5 typedef long long QAQ ; 6 7 int c[ maxN ] , t1[ maxN ] , t2[ maxN ] , father[ maxN ] , size[ maxN ] ; 8 map <int ,int>mp[ maxN ] ; 9 QAQ Ans ; 10 11 int getfa ( const int x ) { return father[ x ] == x ? x : father[ x ] = getfa ( father[ x ] ) ; } 12 inline int gmin ( const int x , const int y ) { return x > y ? y : x ; } 13 inline int gmax ( const int x , const int y ) { return x > y ? x : y ; } 14 void Set_Init ( const int n ) { for ( int i=1 ; i<=n ; ++i ) father[ i ] = i , size[ i ] = 1 ; }15 inline void Union_Set ( int x , int y ) { father[ x ] = y ; size[ y ] += size [ x ] ; } 16 17 inline int INPUT ( ) {18 int ret = 0 , f = 1 ; char ch = getchar( ) ;19 while ( ch < ‘0‘ || ‘9‘ < ch ) { if ( ch == ‘-‘ ) f = -1 ; ch = getchar ( ) ; } 20 while ( ‘0‘ <= ch && ch <= ‘9‘ ) { ret = ( ret << 1 ) + ( ret << 3 ) + ch - ‘0‘ ; ch = getchar ( ) ; }21 return ret * f ;22 } 23 24 25 int main ( ) {26 int N = INPUT ( ) , M = INPUT ( ) , K = INPUT ( ) ;27 for ( int i=1 ; i<=N ; ++i ) 28 c[ i ] = INPUT ( ) ;29 Set_Init ( N ) ;30 for ( int i=1 ; i<=M ; ++i ) {31 t1[ i ] = INPUT ( ) , t2[ i ] = INPUT ( ) ;32 int px = getfa ( t1[ i ] ) ;33 int py = getfa ( t2[ i ] ) ;34 if ( px != py ) Union_Set ( px , py ) ;35 }36 for ( int i=1 ; i<=N ; ++i ) ++mp[ getfa ( i ) ][ c[ i ] ] ;37 for ( int i=1 ; i<=N ; ++i ) {38 if ( getfa ( i ) == i ) {39 int temp = 0 ;40 map <int , int>::iterator It ; 41 for ( It = mp[ i ].begin( ) ; It != mp[ i ].end ( ) ; ++It ) {42 temp = gmax( temp, It -> second ) ;43 }44 Ans += size[ i ] - temp ; 45 }46 }47 cout << Ans << endl ; 48 return 0 ; 49 }
Codeforces #Round 376 部分题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。