本文主要是介绍【codeforces】Codeforces Round #277 (Div. 2) 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：Codeforces Round #277 (Div. 2)
486A. Calculating Function
裸公式= =
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;typedef long long LL ;LL n ;int main () {while ( ~scanf ( "%I64d" , &n ) ) printf ( "%I64d\n" , n / 2 - ( n % 2 ? n : 0 ) ) ;return 0 ;
}486B. OR in Matrix
根据题意，将a矩阵必须为0的地方先填充为0，其他地方置为1，然后对b矩阵中为1的bij判断第i行或第j列是否有1，没有输出NO，判断到最后如果所有的bij都是合法的，则输出YES。
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std ;typedef long long LL ;#define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )
#define mid ( ( l + r ) >> 1 )int a[105][105] ;
int b[105][105] ;
int R[105] , C[105] ;
int n , m ;void solve () {clr ( R , 0 ) ;clr ( C , 0 ) ;For ( i , 1 , n ) For ( j , 1 , m ) a[i][j] = 1 ;For ( i , 1 , n ) For ( j , 1 , m ) {scanf ( "%d" , &b[i][j] ) ;if ( !b[i][j] ) {For ( k , 1 , m ) a[i][k] = 0 ;For ( k , 1 , n ) a[k][j] = 0 ;}}For ( i , 1 , n ) For ( j , 1 , m ) {R[i] += a[i][j] ;C[j] += a[i][j] ;}For ( i , 1 , n ) For ( j , 1 , m ) if ( b[i][j] ) {if ( a[i][j] ) continue ;if ( R[i] || C[j] ) continue ;printf ( "NO\n" ) ;return ;}printf ( "YES\n" ) ;For ( i , 1 , n ) For ( j , 1 , m ) printf ( "%d%c" , a[i][j] , j < m ? ' ' : '\n' ) ;
}int main () {while ( ~scanf ( "%d%d" , &n , &m ) ) solve () ;return 0 ;
}
486C. Palindrome Transformation
贪心，事实上只用在初始位置所在的字符串半边处理便足够了，于是考虑几种情况，判一下即可。这题错的吐血了，少打两个else，导致绝杀失败，不然30多名好歹好看一点。。
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std ;typedef long long LL ;#define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )
#define mid ( ( l + r ) >> 1 )const int MAXN = 100005 ;char s[MAXN] ;
int a[MAXN] ;
int n , p ;void solve () {int ans = 0 ;clr ( a , 0 ) ;scanf ( "%s" , s + 1 ) ;int l = n + 1 , r = 1 ;For ( i , 1 , n / 2 ) {if ( s[i] != s[n - i + 1] ) {a[i] = abs ( s[i] - s[n - i + 1] ) ;a[n - i + 1] = a[i] = min ( a[i] , 26 - a[i] ) ;ans += a[i] ;}}if ( p <= n / 2 ) {For ( i , 1 , n / 2 ) if ( a[i] ) l = min ( l , i ) , r = max ( r , i ) ;} else {For ( i , n / 2 + 1 , n ) if ( a[i] ) l = min ( l , i ) , r = max ( r , i ) ;}if ( l != n + 1 ) {if ( p <= l ) ans += r - p ;else if ( p >= r ) ans += p - l ;else ans += min ( r - l + r - p , r - l + p - l ) ;}printf ( "%d\n" , ans ) ;
}int main () {while ( ~scanf ( "%d%d" , &n , &p ) ) solve () ;return 0 ;
}486D. Valid Sets
考虑以每个点作为根结点扩展出一棵树，这个树满足树上所有的节点的权值都不比树根大且val[root]-val[v]<=d，然后可以树型DP求以这个点为树根的集合数。考虑到如果以u为根时扩展的树中包含了与u权值相同的v，那么以v为根时便不能包括u了，这个我们可以用一个数组判重。
具体见代码。
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std ;typedef long long LL ;#define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )
#define mid ( ( l + r ) >> 1 )const int MAXN = 2005 ;
const int MAXE = 4005 ;
const int mod = 1e9 + 7 ;struct Edge {int v , n ;Edge () {}Edge ( int v , int n ) : v ( v ) , n ( n ) {}
} ;Edge E[MAXE] ;
int H[MAXN] , cntE ;
int val[MAXN] ;
int vis[MAXN][MAXN] ;
LL dp[MAXN] ;
int d , n ;
int root ;void clear () {cntE = 0 ;clr ( H , -1 ) ;clr ( vis , 0 ) ;
}void addedge ( int u , int v ) {E[cntE] = Edge ( v , H[u] ) ;H[u] = cntE ++ ;
}LL dfs ( int u , int fa ) {dp[u] = 1 ;LL ans = 1 ;for ( int i = H[u] ; ~i ; i = E[i].n ) {int v = E[i].v ;if ( v == fa ) continue ;if ( val[v] > val[root] || vis[root][v] || val[root] - val[v] > d ) continue ;if ( val[root] == val[v] ) vis[root][v] = vis[v][root] = 1 ;LL tmp = dfs ( v , u ) ;ans = ( ans + tmp * dp[u] % mod ) % mod ;dp[u] = ( dp[u] + tmp * dp[u] ) % mod ;}return ans ;
}void solve () {int u , v ;clear () ;For ( i , 1 , n ) scanf ( "%d" , &val[i] ) ;rep ( i , 1 , n ) {scanf ( "%d%d" , &u , &v ) ;addedge ( u , v ) ;addedge ( v , u ) ;}LL ans = 0 ;For ( i , 1 , n ) {root = i ;ans = ( ans + dfs ( i , 0 ) ) % mod ;}printf ( "%I64d\n" , ans ) ;
}int main () {while ( ~scanf ( "%d%d" , &d , &n ) ) solve () ;return 0 ;
}
486E. LIS of Sequence
设F1[i]为1~i内以i结尾的LIS，F2[i]为i~n内以i开头的LIS，ans为1~n内的LIS。
1.F1[i]+F2[i]-1<ans。
2.F1[i]+F2[i]-1==ans时长度F1[i]不唯一。
3.F1[i]+F2[i]-1==ans时长度F1[i]唯一。
可用二分求F1[i]，F2[i]。
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std ;typedef long long LL ;#define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )
#define mid ( ( l + r ) >> 1 )const int MAXN = 100005 ;int vis[MAXN] ;
int S[MAXN] , top ;
int a[MAXN] ;
int F1[MAXN] ;
int F2[MAXN] ;
int n ;int search1 ( int x , int l , int r ) {while ( l < r ) {int m = mid ;if ( S[m] >= x ) r = m ;else l = m + 1 ;}return l ;
}int search2 ( int x , int l , int r ) {while ( l < r ) {int m = mid ;if ( S[m] <= x ) r = m ;else l = m + 1 ;}return l ;
}void solve () {clr ( vis , 0 ) ;For ( i , 1 , n ) scanf ( "%d" , &a[i] ) ;top = 0 ;For ( i , 1 , n ) {if ( !top || a[i] > S[top] ) {S[++ top] = a[i] ;F1[i] = top ;} else {int x = search1 ( a[i] , 1 , top ) ;S[x] = a[i] ;F1[i] = x ;}}top = 0 ;rev ( i , n , 1 ) {if ( !top || a[i] < S[top] ) {S[++ top] = a[i] ;F2[i] = top ;} else {int x = search2 ( a[i] , 1 , top ) ;S[x] = a[i] ;F2[i] = x ;}}int ans = top ;For ( i , 1 , n ) if ( F1[i] + F2[i] - 1 == ans ) ++ vis[F1[i]] ;For ( i , 1 , n ) {if ( F1[i] + F2[i] - 1 < ans ) putchar ( '1' ) ;else if ( vis[F1[i]] == 1 ) putchar ( '3' ) ;else putchar ( '2' ) ;}printf ( "\n" ) ;
}int main () {while ( ~scanf ( "%d" , &n ) ) solve () ;return 0 ;
}这篇关于【codeforces】Codeforces Round #277 (Div. 2) 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
