[codeforces] Codeforces Round #279(Div.2) 문제 해결

12670 단어 codeforces
전송문: [codeforces] Codeforces Round #279(Div. 2)
490A. Team Olympiad
수량이 1, 2, 3 중에 제일 작은 거요.시뮬레이션을 하면 돼요. 벡터를 사용하면 아주 편리해요. 하지만 저는 인접표를 썼어요.(나는 특별한 죽음의 기교가 있다)
#include <set>
#include <vector>
#include <cstdio>
#include <cstring>
#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 ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define root 1 , 1 , Graph.bcc_cnt
#define mid ( ( l + r ) >> 1 )

const int MAXN = 100005 ;
const int MAXE = 100005 ;

struct Edge {
	int v , n ;
	Edge () {}
	Edge ( int v , int n ) : v ( v ) , n ( n ) {}
} ;


Edge E[MAXE] ;
int H[4] , cntE ;
int a[MAXN] , b[MAXN] , c[MAXN] ;
int all[4] ;
int n ;

void clear () {
	cntE = 0 ;
	clr ( H , -1 ) ;
	clr ( all , 0 ) ;
}

void addedge ( int u , int v ) {
	E[cntE] = Edge ( v , H[u] ) ;
	H[u] = cntE ++ ;
}

void solve () {
	int x ;
	clear () ;
	For ( i , 1 , n ) {
		scanf ( "%d" , &x ) ;
		addedge ( x , i ) ;
		all[x] ++ ;
	}
	int m = min ( min ( all[1] , all[2] ) , all[3] ) ;
	printf ( "%d
" , m ) ;
	int cnt ;
	cnt = 0 ;
	for ( int i = H[1] ; ~i ; i = E[i].n ) {
		a[cnt ++] = E[i].v ;
		if ( cnt == m ) break ;
	}
	cnt = 0 ;
	for ( int i = H[2] ; ~i ; i = E[i].n ) {
		b[cnt ++] = E[i].v ;
		if ( cnt == m ) break ;
	}
	cnt = 0 ;
	for ( int i = H[3] ; ~i ; i = E[i].n ) {
		c[cnt ++] = E[i].v ;
		if ( cnt == m ) break ;
	}
	rep ( i , 0 , m ) printf ( "%d %d %d
" , a[i] , b[i] , c[i] ) ;
}

int main () {
	while ( ~scanf ( "%d" , &n ) ) solve () ;
	return 0 ;
}

490B. Queue
매 쌍의ai,bi에 대해next[ai]=bi를 설정하면 0부터next를 따라 가면 짝수인 사람의 번호를 쉽게 알 수 있다.
그리고 우리는 모든 사람에게 선구자pre[bi]=ai를 기록한다. 위치가 1인 사람은 선구가 없기 때문에 이 사람을 다시 찾는다. 이 사람부터next를 따라 가면 위치가 홀수인 사람의 번호를 벗어날 수 있다.
이 문제에 이르러 해결하다.
#include <set>
#include <vector>
#include <cstdio>
#include <cstring>
#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 ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define root 1 , 1 , Graph.bcc_cnt
#define mid ( ( l + r ) >> 1 )

const int MAXN = 1000005 ;
const int MAXE = 100005 ;

int next[MAXN] ;
int pos[MAXN] ;
int use[MAXN] ;
int p[MAXN] ;
int n ;

void solve () {
	int x , y ;
	clr ( next , 0 ) ;
	clr ( use , 0 ) ;
	rep ( i , 0 , MAXN ) p[i] = i ;
	For ( i , 1 , n ) {
		scanf ( "%d%d" , &x , &y ) ;
		next[x] = y ;
		use[x] = use[y] = 1 ;
		p[y] = x ;
	}
	x = 0 , y = 2 ;
	while ( next[x] ) {
		pos[y] = next[x] ;
		y += 2 ;
		x = next[x] ;
	}
	For ( i , 1 , 1000000 ) {
		if ( !use[i] ) continue ;
		if ( p[i] == i ) {
			x = i ;
			break ;
		}
	}
	y = 1 ;
	while ( x ) {
		pos[y] = x ;
		y += 2 ;
		x = next[x] ;
	}
	For ( i , 1 , n ) printf ( "%d%c" , pos[i] , i < n ? ' ' : '
' ) ;
}

int main () {
	while ( ~scanf ( "%d" , &n ) ) solve () ;
	return 0 ;
}
490 C. Hacking Cypher
문자열을 두 부로 나누어 위치 i에서 두 개의 수 x, y를 끊었다고 가정하면, i+1에서 두 개의 수를 O(1)로 추정할 수 있습니다.
x1 = (x* 10 + s[i + 1])% a, y1 = (y* 10 - s[i + 1]* pow[n - i - 2])% b, 그중 pow[i]=10 ^i, pow[i]=pow[i - 1]%b.
#include <set>
#include <vector>
#include <cstdio>
#include <cstring>
#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 ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define root 1 , 1 , Graph.bcc_cnt
#define mid ( ( l + r ) >> 1 )

const int MAXN = 1000005 ;
const int MAXE = 100005 ;

char s[MAXN] ;
LL pow[MAXN] ;
int a , b ;

void solve () {
	int L = 0 , R = 0 ;
	int n = strlen ( s ) ;
	pow[0] = 1 ;
	rep ( i , 1 , MAXN ) pow[i] = pow[i - 1] * 10 % b ;
	rep ( i , 0 , n ) R = ( R * 10 + s[i] - '0' ) % b ;
	rep ( i , 0 , n - 1 ) {
		L = ( L * 10 + s[i] - '0' ) % a ;
		R = ( R - ( s[i] - '0' ) * pow[n - i - 1] % b + b ) % b ;
		if ( L == 0 && R == 0 && s[i + 1] != '0' ) {
			printf ( "YES
" ) ;
			For ( j , 0 , i ) printf ( "%c" , s[j] ) ;
			printf ( "
" ) ;
			rep ( j , i + 1 , n ) printf ( "%c" , s[j] ) ;
			printf ( "
" ) ;
			return ;
		}
	}
	printf ( "NO
" ) ;
}

int main () {

	while ( ~scanf ( "%s%d%d" , s , &a , &b ) ) solve () ;
	return 0 ;
}

490D. Chocolate
먼저 a1*b1, a2*b2를 얻어 그들의 gcd(a1*b1, a2*b2)=x를 얻어 답을 쉽게 알 수 있다. 만약에 존재한다면 면적은 반드시 그들의 gcd의 배수이다. 그리고 a1*b1/x중 2의 개수, a2*b2/x중 2의 개수, a1*b1/x중 3의 개수, a2*b2/x중 3의 개수를 얻는다.그리고 우리는 3이 많은 그 면적의 3을 2로 바꾸는데 이것은 반드시 진행해야 한다는 것을 알기 쉽다.그리고 2가 비교적 많은 면적에서 나머지 2를 제거하고 이렇게 처리한 후에 두 직사각형의 최종 면적이 같으면 해가 있고 그렇지 않으면 해가 없다.
PS: 폭력은 많이 쓸 수 있다고 생각합니다. 직사각형 1을 처리하면 모든 면적을 순서대로 배열하고 마지막 a1, b1이 변하는 값과 사용하는 최소 걸음수를 기록합니다. 그리고 직사각형 2를 똑같이 처리하고 얻은 면적을 직사각형 1에서 2분으로 나누어 찾을 수 있는지 확인하고 가능하면 업데이트를 합니다.그리고 OK.
#include <set>
#include <vector>
#include <cstdio>
#include <cstring>
#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 ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define root 1 , 1 , cnt
#define mid ( ( l + r ) >> 1 )

const int MAXN = 100005 ;
const int MAXE = 200005 ;

int a[2] , b[2] ;
int a1 , b1 , a2 , b2 ;

inline LL gcd ( LL a , LL b ) {
	return b ? gcd ( b , a % b ) : a ;
}

inline void divide ( LL a , int b , int &cnt ) {
	for ( cnt = 0 ; a % b == 0 ; a /= b ) ++ cnt ;
	//printf ( "%d
" , cnt ) ;
}

void solve () {
	int cnt = 0 ;
	LL x1 = ( LL ) a1 * b1 ;
	LL x2 = ( LL ) a2 * b2 ;
	LL x = gcd ( x1 , x2 ) ;
	//printf ( "%d
" , x ) ;
	divide ( x1 / x , 2 , a[0] ) ;
	divide ( x2 / x , 2 , a[1] ) ;
	divide ( x1 / x , 3 , b[0] ) ;
	divide ( x2 / x , 3 , b[1] ) ;
	while ( b[0] > b[1] ) {
		-- b[0] ;
		++ a[0] ;
		x1 = x1 / 3 * 2 ;
		++ cnt ;
		if ( a1 % 3 == 0 ) a1 = a1 / 3 * 2 ;
		else if ( b1 % 3 == 0 ) b1 = b1 / 3 * 2 ;
		else {
			printf ( "-1
" ) ;
			return ;
		}
	}
	while ( b[1] > b[0] ) {
		-- b[1] ;
		++ a[1] ;
		x2 = x2 / 3 * 2 ;
		++ cnt ;
		if ( a2 % 3 == 0 ) a2 = a2 / 3 * 2 ;
		else if ( b2 % 3 == 0 ) b2 = b2 / 3 * 2 ;
		else {
			printf ( "-1
" ) ;
			return ;
		}
	}
	while ( a[0] > a[1] ) {
		-- a[0] ;
		++ cnt ;
		x1 /= 2 ;
		if ( a1 % 2 == 0 ) a1 /= 2 ;
		else if ( b1 % 2 == 0 ) b1 /= 2 ;
		else {
			printf ( "-1
" ) ;
			return ;
		}
	}
	while ( a[1] > a[0] ) {
		-- a[1] ;
		++ cnt ;
		x2 /= 2 ;
		if ( a2 % 2 == 0 ) a2 /= 2 ;
		else if ( b2 % 2 == 0 ) b2/= 2 ;
		else {
			printf ( "-1
" ) ;
			return ;
		}
	}
	if ( x1 != x2 ) {
		printf ( "-1
" ) ;
		return ;
	}
	printf ( "%d
" , cnt ) ;
	printf ( "%d %d
" , a1 , b1 ) ;
	printf ( "%d %d
" , a2 , b2 ) ;
}

int main () {
	while ( ~scanf ( "%d%d%d%d" , &a1 , &b1 , &a2 , &b2 ) ) solve () ;
	return 0 ;
}
490 E. Restoring Increasing Sequence
나는 이 문제가 훨씬 간단하다고 생각한다.
모든 수를 최대로 바꿀 수 있는 수(?를 9로 바꿀 수 있는 수)로 바꾸고 그 다음에 높은 자리에서 하나하나 줄여서 이 방법으로 이전보다 큰 가장 작은 수를 찾아라.찾지 못하면 해가 없다.나는 이 문제가 짜증나는 것이 바로 시뮬레이션이라고 생각한다. AC가 한 번 더 괜찮다. 그렇지 않으면 음이 모두 아프다.
#include <set>
#include <vector>
#include <cstdio>
#include <cstring>
#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 ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define root 1 , 1 , Graph.bcc_cnt
#define mid ( ( l + r ) >> 1 )

const int MAXN = 100005 ;
const int MAXE = 100005 ;
const int L = 9 ;

struct Node {
	int num , n ;
	int digit[L] ;
	int unknow[L] ;
} ;

Node a[MAXN] ;
int pow[L] ;
char s[L] ;
int n ;

void solve () {
	clr ( a , 0 ) ;
	int flag = 0 ;
	For ( i , 1 , n ) {
		scanf ( "%s" , s ) ;
		a[i].n = strlen ( s ) ;
		if ( s[0] == '0' ) flag = 1 ;
		rep ( j , 0 , a[i].n ) {
			if ( s[j] == '?' ) {
				a[i].num = a[i].num * 10 + 9 ;
				a[i].digit[a[i].n - j - 1] = 9 ;
				a[i].unknow[a[i].n - j - 1] = 1 ;
			} else {
				a[i].num = a[i].num * 10 + s[j] - '0' ;
				a[i].digit[a[i].n - j - 1] = s[j] - '0' ;
			}
		}
	}
	if ( flag ) {
		printf ( "NO
" ) ;
		return ;
	}
	int pre = 0 ;
	For ( i , 1 , n ) {
		int first = 1 , now = a[i].num ;
		rev ( j , a[i].n - 1 , 0 ) {
			if ( a[i].unknow[j] == 0 ) {
				first = 0 ;
				continue ;
			}
			int up = first ? 8 : 9 ;
			rep ( k , 0 , up ) {
				if ( now - pow[j] <= pre ) break ;
				now -= pow[j] ;
			}
			first = 0 ;
		}
		if ( now <= pre ) {
			printf ( "NO
" ) ;
			return ;
		}
		a[i].num = now ;
		pre = now ;
	}
	printf ( "YES
" ) ;
	For ( i , 1 , n ) printf ( "%d
" , a[i].num ) ;
}

int main () {
	pow[0] = 1 ;
	rep ( i , 1 , 10 ) pow[i] = pow[i - 1] * 10 ;
	while ( ~scanf ( "%d" , &n ) ) solve () ;
	return 0 ;
}

490F. Treeland Tour
정해는 아니지만 복잡도를 조금 계산해 보니 상수가 작은 O(N^2logN)는 끊길 수 있다.
방법은 매거근을 열거한 다음에 dfs입니다. 이 점에 들어갈 때 이 점을 2분구LIS의 방법에 따라 창고에 추가하고 최우수치를 업데이트합니다. 이 점을 떠날 때 창고의 요소를 바꾸면 됩니다.이 방법의 상수는 아직 매우 작다. 처음에 나는 라인 트리로 이 절차를 완성했다.TLE가...역시 너무 어려...
폭력적이지 않은 걸 어떻게 해야 할지 생각이 안 났어요. -
#include <set>
#include <vector>
#include <cstdio>
#include <cstring>
#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 ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define root 1 , 1 , cnt
#define mid ( ( l + r ) >> 1 )

const int MAXN = 100005 ;
const int MAXE = 200005 ;

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 n ;
int S[MAXN] ;
int ans ;

void clear () {
	cntE = 0 ;
	clr ( H , -1 ) ;
}

void addedge ( int u , int v ) {
	E[cntE] = Edge ( v , H[u] ) ;
	H[u] = cntE ++ ;
}

int search ( int x , int l , int r ) {
	while ( l < r ) {
		int m = mid ;
		if ( val[S[m]] >= x ) r = m ;
		else l = m + 1 ;
	}
	return l ;
}

void dfs ( int u , int top = 0 , int fa = 0 ) {
	int pos , tmp ;
	if ( !top || val[S[top - 1]] < val[u] ) {
		S[top ++] = u ;
		ans = max ( ans , top ) ;
		pos = top - 1 ;
	} else {
		pos = search ( val[u] , 0 , top - 1 ) ;
		tmp = S[pos] ;
		S[pos] = u ;
	}
	for ( int i = H[u] ; ~i ; i = E[i].n ) if ( E[i].v != fa ) dfs ( E[i].v , top , u ) ;
	S[pos] = tmp ;
}

void solve () {
	ans = 0 ;
	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 ) ;
	}
	For ( i , 1 , n ) dfs ( i ) ;
	printf ( "%d
" , ans ) ;
}

int main () {
	while ( ~scanf ( "%d" , &n ) ) solve () ;
	return 0 ;
}
[codeforces] Codeforces Round #280(Div.2) 물문제 특집
[회전 알고리즘] 슬라이딩 창

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage