【codeforces】Codeforces Round #279 (Div. 2) 题解

现在的位置: 首页 > 综合 > 正文

【codeforces】Codeforces Round #279 (Div. 2) 题解

2017年10月16日 ⁄ 综合 ⁄ 共 7533字 ⁄ 字号小中大 ⁄ 评论关闭

传送门：【codeforces】Codeforces Round #279 (Div. 2)

数量就是1，2，3中最小的那个。模拟即可，用vector超级方便，不过我还是用了邻接表。。（我有特殊的作死技巧）

#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\n" , 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\n" , 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 ? ' ' : '\n' ) ;
}

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

490 C. Hacking Cypher

将字符串拆成两份，假设我们从位置i断开得到两个数x，y，那么我们可以O（1）递推得到i+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\n" ) ;
			For ( j , 0 , i ) printf ( "%c" , s[j] ) ;
			printf ( "\n" ) ;
			rep ( j , i + 1 , n ) printf ( "%c" , s[j] ) ;
			printf ( "\n" ) ;
			return ;
		}
	}
	printf ( "NO\n" ) ;
}

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较多的那个面积的三转化成2，易知这个是一定要进行的。然后再将2较多的面积中把多余的2去掉，如果这样处理以后两个矩形的最终面积相同则有解，否则无解。

PS：我觉得暴力会好写很多，对矩形1处理得到所有面积排个序，同时记录最后a1，b1变成的值和所用的最小步数，然后同样对矩形2处理，对得到的面积在矩形1中二分看是否能找到，能的话就更新解。然后就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\n" , cnt ) ;
}

void solve () {
	int cnt = 0 ;
	LL x1 = ( LL ) a1 * b1 ;
	LL x2 = ( LL ) a2 * b2 ;
	LL x = gcd ( x1 , x2 ) ;
	//printf ( "%d\n" , 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\n" ) ;
			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\n" ) ;
			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\n" ) ;
			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\n" ) ;
			return ;
		}
	}
	if ( x1 != x2 ) {
		printf ( "-1\n" ) ;
		return ;
	}
	printf ( "%d\n" , cnt ) ;
	printf ( "%d %d\n" , a1 , b1 ) ;
	printf ( "%d %d\n" , 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\n" ) ;
		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\n" ) ;
			return ;
		}
		a[i].num = now ;
		pre = now ;
	}
	printf ( "YES\n" ) ;
	For ( i , 1 , n ) printf ( "%d\n" , 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，进入这个点的时候将这个点按照二分求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\n" , ans ) ;
}

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

【上篇】【codeforces】Codeforces Round #280 (Div. 2) 水题专场
【下篇】【codeforces】Codeforces Round #278 (Div. 1) 题解 487E. Tourists 点双连通+树链剖分

作者: fennel

该日志由 fennel 于7年前发表在综合分类下，最后更新于 2017年10月16日.
转载请注明: 【codeforces】Codeforces Round #279 (Div. 2) 题解 | 学步园 +复制链接

抱歉!评论已关闭.

学步园

【codeforces】Codeforces Round #279 (Div. 2) 题解

作者: fennel

书签

最新文章New

本站推荐

返回首页