首页 > 代码库 > Codeforces Round #256 (Div. 2)
Codeforces Round #256 (Div. 2)
A - Rewards
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int main(){ 5 int a[3], b[3], sum1 = 0, sum2 = 0; 6 int n; 7 for( int i = 0; i < 3; i++ ){ 8 cin>>a[i]; 9 sum1 += a[i];10 }11 for( int i = 0; i < 3; i++ ){12 cin>>b[i];13 sum2 += b[i];14 }15 int ans1, ans2;16 if( sum1 % 5 == 0 ) ans1 = sum1/5;17 else ans1 = sum1/5 + 1;18 if( sum2 % 10 == 0 ) ans2 = sum2/10;19 else ans2 = sum2/10 + 1;20 cin>>n;21 if( n >= (ans1 + ans2) ){22 printf( "YES\n");23 }24 else printf( "NO\n" );25 return 0;26 }
B - Suffix Structures
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<algorithm> 6 7 using namespace std; 8 9 int x[100], z[100];10 char a[1000], b[1000];11 int main(){12 cin >> a >> b;13 int n = strlen( a ), m = strlen( b );14 for( int i = 0; i < n; i++ ){15 x[ a[i]-‘a‘ ]++;16 }17 for( int i = 0; i < n; i++ ){18 z[ b[i]-‘a‘ ]++;19 }20 if( n == m ){21 bool flag = 0;22 for( int i = 0; i < 26; i++ ){23 if( x[i] != z[i] ) flag = 1;24 }25 if( !flag ){26 printf( "array\n" ); return 0;27 }28 else {29 printf( "need tree\n" ); return 0;30 }31 }32 if( n < m ){33 printf( "need tree\n" ); return 0;34 }35 if( n > m ){36 bool flag = 0;37 for( int i = 0; i < 26; i++ ){38 if( z[i] > x[i] ) flag = 1;39 }40 if( flag ){41 printf( "need tree\n" ); return 0;42 }43 if( !flag ){44 int i = 0, j = 0;45 while( j < m && i < n ){46 if( a[i] == b[j] ){47 i++, j++;48 }49 else i++;50 }51 if( j == m ){52 printf( "automaton\n" ); return 0;53 }54 else{55 printf( "both\n" ); return 0;56 }57 }58 }59 return 0;60 }
C - Painting Fence
刷木板。分治的思想，dfs(l, r, k), 看每一段是横着刷还是竖着刷比较忧。。
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #include<string> 6 #include<queue> 7 #include<cmath> 8 #include<vector> 9 10 using namespace std;11 12 #define mnx 10400013 #define ll long long14 #define inf 0x3f3f3f3f15 #define lson l, m, rt << 116 #define rson m+1, r, rt << 1 | 117 18 int a[mnx];19 int dfs( int l, int r, int k ){20 if( l > r ) return 0;21 if( l == r ){22 return min( 1, a[l] - k );23 }24 int mn = min_element( a + l, a + r + 1 ) - a;25 return min( r - l + 1, a[mn] - k + dfs( l, mn - 1, a[mn] ) + dfs( mn + 1, r, a[mn] ) );26 }27 int main(){28 int n, mn = inf;29 scanf( "%d", &n );30 for( int i = 1; i <= n; i++ ){31 scanf( "%d", &a[i] );32 mn = min( mn, a[i] );33 }34 printf( "%d\n", dfs( 1, n, 0 ) );35 return 0;36 }
还有一种dp的做法，http://blog.csdn.net/u014733623/article/details/37927873 真巨神啊。。
说一下我的理解，dp[i][j]表示第i列以后的木板都刷完了（不包括第i列）且第j列是横着刷的，如果value[j]>=value[i]，则dp[i-1][j] = dp[i][i]，第i-1列刷完了，且第j列是横着刷的，因为第j列如果横着刷，肯定也能够把第i列刷了，所以会等于第i列以后刷完了且第i列是横着刷的。else， dp[i-1][j]=min(dp[i][j]+1,dp[i][i]+value[i]-value[j]),dp[i][j]+1,表示的是第i列以后的刷完了，且第j列是横着刷的，这时再把第i列竖着刷一次；dp[i][i]+value[i]-value[j]，表示的是第i列刷完了，且第i列是横着刷的(第i列实际上还没有刷),value[i]-value[j]这时如果刷第j列的话，第i列还要横着刷value[i] - value[j]次，所以 dp[i-1][j]=min(dp[i][j]+1,dp[i][i]+value[i]-value[j])
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #include<string> 6 #include<queue> 7 #include<cmath> 8 #include<vector> 9 10 using namespace std;11 12 #define mnx 505013 #define ll long long14 #define inf 0x3f3f3f3f15 #define lson l, m, rt << 116 #define rson m+1, r, rt << 1 | 117 18 int a[mnx], dp[mnx][mnx];19 int main(){20 int n;21 scanf( "%d", &n );22 for( int i = 1; i <= n; i++ ){23 scanf( "%d", &a[i] );24 }25 for( int i = n; i >= 1; i-- ){26 for( int j = 0; j < n; j++ ){27 if( a[j] >= a[i] ){28 dp[i-1][j] = dp[i][i];29 }30 else dp[i-1][j] = min( dp[i][j] + 1, dp[i][i] + a[i] - a[j] );31 }32 }33 printf( "%d\n", dp[0][0] );34 return 0;35 }
D - Multiplication Table
n*m的矩阵，每个格子的值是i*j，叫你找第k大的值。。二分的做法，对1，n*m二分，二分的值mid在第一行比它小的有 mid / 1个，第二行比它小的有mid / 2个，……，比它小的加起来如果比k小，就对 mid + 1， r 进行二分，否则就对 l, mid 进行二分
1 #include<iostream> 2 #include<cstring> 3 #include<string> 4 #include<cstdio> 5 #include<algorithm> 6 #include<cmath> 7 8 using namespace std; 9 10 #define inf 0x3f3f3f3f11 #define eps 1e-812 #define maxn 11111113 #define mod 100000714 #define ll long long15 16 int main(){17 ll n, m, k;18 cin >> n >> m >> k;19 ll r = n * m, l = 1, mid;20 while( l < r ){21 mid = ( l + r ) >> 1;22 ll sum = 0;23 for( ll i = 1; i <= n; i++ ){24 sum += min( mid / i, m );25 }26 if( sum < k ){27 l = mid + 1;28 }29 else r = mid;30 }31 printf( "%I64d\n", r );32 return 0;33 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。