【codeforces】Codeforces Round #277 (Div. 2) 解读

时间：2023-03-09 14:46:23
【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 ;

}

版权声明：本文博客原创文章，博客，未经同意，不得转载。

相关文章