Codeforces Round 1467 题目大意 & 解题报告

Codeforces Round #695 (Div. 2)

许久不打变得更菜了…

A. Wizard of Orz

0 大意

给定 $n$ 个板子,每个板子上有一个相同的数字 $x ( 0 \leq x \leq 9 )$

随机选择一个数字 $y(1 \leq y \leq n)$,令板子 $i$ 上的数字变成 $ x + |y – i| \pmod 10$

1 Code

显然,输出 $98\{987654321\}$ 的前 $n$ 位即可

#include <cstdio>

int main() {
	int T;
	scanf( "%d", &T );
	while( T -- ) {
		int n;
		scanf( "%d", &n );
		if( n == 1 ) 
			printf( "9" );
		else {
			printf( "98" );
			int cur = 9;
			for( int i = 3; i <= n; i ++ ) {
				printf( "%d", cur );
				cur ++;
				if( cur >= 10 ) 
					cur = 0;
			}
		}
		printf( "\n" );
	}
}

B Hills And Valleys

0 大意

给定一个长度为 $n$ 的序列,对于$\forall i (1 \leq i \leq n)$,如果满足 $ a_i < a_{i-1},a_i < a_{i+1} $ 或 $ a_i > a_{i-1}, a_i > a_{i+1} $ 则对答案贡献 $1$

现在,你可以随意修改仅 $1$ 个数字,求最小的贡献和

1 思路

对于 $i$, 我们令 $max = \max( a_{i+1}, a{i-1} ), min = \min( a_{i+1}, a{i-1} )$

则显然只有 $ a_i = \{ max – 1, max, max + 1, min – 1, min, min + 1\}$ 六种值可能有不同的结果,其他值的结果会和这六个中的某一个相同。

枚举即可

2 Code

#include <cstdio>

#include <vector>

const long long INF = ( 1LL << 60LL );
const long long N = 3e5 + 1e4;

long long n;
long long a[N];

bool chk( long long cur, long long left, long long rig ) {
	if( cur < left && cur < rig ) 
		return true;
	if( cur > left && cur > rig ) 
		return true;
	return false;
}

bool is_vaild( long long cur ) {
	return cur > 1 && cur < n;
}

long long calc( long long cur, long long val ) {
	return ( is_vaild(cur) && chk( val, a[ cur - 1 ], a[ cur + 1 ] ) )
		+ ( is_vaild( cur - 1 ) && chk( a[ cur - 1 ], a[ cur - 2 ], val ) )
		+ ( is_vaild( cur + 1 ) && chk( a[ cur + 1 ], val, a[ cur + 2 ] ) ) ;
}

int main() {
#ifdef woshiluo
	freopen( "b.in", "r", stdin );
	freopen( "b.out", "w", stdout );
#endif
	long long T;
	scanf( "%lld", &T );
	while( T -- ) {
		long long ans = INF, raw = 0;
		scanf( "%lld", &n );

		// Readin
		for( long long i = 1; i <= n; i ++ ) {
			scanf( "%lld", &a[i] );
		}
		a[ n + 1 ] = 0;

		for( long long i = 2; i < n; i ++ ) {
			if( i != 1 && i != n )
				raw += chk( a[i], a[ i - 1 ], a[ i + 1 ] );
		}

		// Calc
		for( long long i = 1; i <= n; i ++ ) {
			long long min = std::min( a[ i - 1 ], a[ i + 1 ] );
			long long max = std::max( a[ i - 1 ], a[ i + 1 ] );

			long long res = INF;
			res = std::min( res, calc( i, min - 1 ) );
			res = std::min( res, calc( i, min ) );
			res = std::min( res, calc( i, min + 1 ) );
			res = std::min( res, calc( i, max - 1 ) );
			res = std::min( res, calc( i, max ) );
			res = std::min( res, calc( i, max + 1 ) );

			ans = std::min( ans, raw - ( calc( i, a[i] ) - res ) );
		}
		
		printf( "%lld\n", ans );
	}
}

C Three Bags

1 大意

三个集合,你可以从一个集合中取出一个数 $a$,从另一个集合中取出一个数字 $b$, 将 $a-b$ 放回第一个集合

求最后剩下的数字的最大值

2 思路

将这个减少的关系建成图之后,容易发现,答案无非是两种情况

  1. 两个集合的和减去另一个集合的和
  2. 所有数字减去两个不同集合的最小数字

那么都试一下就可以

3 Code

/// Woshiluo
/// Email: woshiluo.luo [at] outlook.com
/// Blog: https://blog.woshiluo.com

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <vector>
#include <algorithm>

const long long LLF = 1e18;
const int INF = 0x3f3f3f3f;

template<class T>
T Min( T a, T b ) { return a < b? a: b; }
template<class T>
T Max( T a, T b ) { return a > b? a: b; }
template<class T>
void chk_Min( T &a, T b ) { if( a > b ) a = b; }
template<class T>
void chk_Max( T &a, T b ) { if( a < b ) a = b; }

int n[3];
std::vector<long long> a[3];

int main() {
	scanf( "%d%d%d", &n[0], &n[1], &n[2] );
	long long min = LLF, tot = 0;
	for( int j = 0; j < 3; j ++ ) {
		long long sum = 0;
		for( int i = 1; i <= n[j]; i ++ ) {
			int tmp;
			scanf( "%d", &tmp );
			a[j].push_back(tmp);
			sum += tmp;
		}
		tot += sum;
		chk_Min(min, sum);
		std::sort(a[j].begin(), a[j].end());
	}

	for( int i = 0; i < 3; i ++ ) {
		for( int j = i + 1; j < 3; j ++ ) {
			chk_Min( min, a[i][0] + a[j][0] );
		}
	}

	printf( "%lld\n", tot - 2LL * min );
}

D Sum of Paths

1 大意

机器人可以且仅可以向左或向右走,每个点有权值,机器人可以走 $k$ 步,起点任意,求机器人所有的可能的路径的权值的和

令路径的权值为其经过所有点的点权和(如果一个点经过了多次,则多次计算)

2 思路

显然每一个点对答案造成的贡献的次数是恒定的,求出这个次数即即可

3 Code

// Woshiluo
// Email: woshiluo.luo [at] outlook.com
// Blog: https://blog.woshiluo.com

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <vector>
#include <algorithm>

template<class T>
T Min( T a, T b ) { return a < b? a: b; }
template<class T>
T Max( T a, T b ) { return a > b? a: b; }
template<class T>
void chk_Min( T &a, T b ) { if( a > b ) a = b; }
template<class T>
void chk_Max( T &a, T b ) { if( a < b ) a = b; }

const int N = 5100;
const int mod = 1e9 + 7;

struct ModInt {
	int cur;
	ModInt( int _cur = 0 ) { cur = (((_cur % mod) + mod) % mod); }
	ModInt operator +( const ModInt &b ) const { return (cur + b.cur) % mod; }
	ModInt operator *( const ModInt &b ) const { return (1LL * cur * b.cur) % mod; }
	bool operator !=( const ModInt &b ) const { return cur != b.cur; }
	void operator +=( const ModInt &b ) {
		cur += b.cur;
		if( cur >= mod ) 
			cur -= mod;
	}
	void operator *=( const ModInt &b ) {
		cur = ( 1LL * cur * b.cur ) % mod;
	}
	void output( char end = '\n' ) {
		printf( "%d%c", ( cur + mod ) % mod, end );
	}
};

int n, k, q;
ModInt f[N][N], a[N], p[N];

int main() {
#ifdef woshiluo
	freopen( "d.in", "r", stdin );
	freopen( "d.out", "w", stdout );
#endif

	scanf( "%d%d%d", &n, &k, &q );
	for( int i = 1; i <= n; i ++ ) {
		int tmp;
		scanf( "%d", &tmp );
		a[i] = tmp;
		f[0][i] = 1;
	}

	for( int i = 1; i <= k; i ++ ) {
		int la = i - 1;
		for( int j = 1; j <= n; j ++ ) {
			f[i][j] = f[la][ j - 1 ] + f[la][ j + 1 ];
		}
	}

	for( int i = 1; i <= n; i ++ ) {
		for( int j = 0; j <= k; j ++ ) {
			p[i] += f[j][i] * f[ k - j ][i];
		}
	}

	ModInt ans = 0;
	for( int i = 1; i <= n; i ++ ) {
		ans += a[i] * p[i];
	}
	while( q -- ) {
		int pos, val;
		scanf( "%d%d", &pos, &val );
		ans += a[pos] * p[pos] * -1;
		a[pos] = val;
		ans += a[pos] * p[pos];
		ans.output();
	}
}

E Distinctive Roots in a Tree

1 题目大意

每个节点有一个给定的权值,如果一个根到所有节点的路径上的点的权值没有重复,,则我们称这个节点为好根,求好根个数

带修,只修改一个点

2 思路

容易发现,如果一个节点的权值已经出现过,那么只有两种状况

  1. 两个节点没有父子内,则两个节点的字数都不可能为好根
  2. 两个节点有父子关系,则只有两个节点之间的节点可以为好根

容易发现这个可以通过树上差分维护

3 Code

/// Woshiluo
/// Email: woshiluo.luo [at] outlook.com
/// Blog: https://blog.woshiluo.com

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <map>
#include <vector>
#include <algorithm>

template<class T>
T Min( T a, T b ) { return a < b? a: b; }
template<class T>
T Max( T a, T b ) { return a > b? a: b; }
template<class T>
void chk_Min( T &a, T b ) { if( a > b ) a = b; }
template<class T>
void chk_Max( T &a, T b ) { if( a < b ) a = b; }

const int N = 2e5 + 1e4;

// Edge Start
struct edge {
	int to, next;
} e[ N << 1 ];
int ehead[N], ecnt;
inline void add_edge( int cur, int to ) {
	ecnt ++;
	e[ecnt].to = to;
	e[ecnt].next = ehead[cur];
	ehead[cur] = ecnt;
}
// Edge End

int n;
int a[N], sum[N];

inline void add( int from, int to, int val ) {
	sum[from] += val;
	sum[to + 1] -= val;
}

int dfn[N], size[N], la[N], idx;
bool vis[N];
void dfs( int cur, int fa ) {
	idx ++; dfn[cur] = idx; size[cur] = 1;
	vis[cur] = true;

	bool flag = false; 
	if( la[ a[cur] ] ) {
		flag = true;
		if( vis[ la[ a[cur] ] ] == false ) {
			int aot = la[ a[cur] ];
			add( dfn[aot], dfn[aot] + size[aot] - 1, 1 );
		}
	}
	la[ a[cur] ] = cur;

	for( int i = ehead[cur]; i; i = e[i].next ) {
		if( e[i].to == fa )
			continue;
		dfs( e[i].to, cur );
		size[cur] += size[ e[i].to ];
		if( la[ a[cur] ] != cur ) {
			add( 1, n, 1 );
			add( dfn[ e[i].to ], dfn[ e[i].to ] + size[ e[i].to ] - 1, -1 );
		}
		la[ a[cur] ] = cur;
	}

	if( flag ) 
		add( dfn[cur], dfn[cur] + size[cur] - 1, 1 );
	vis[cur] = false;
}

int main() {
#ifdef woshiluo
	freopen( "e.in", "r", stdin );
	freopen( "e.out", "w", stdout );
#endif
	scanf( "%d", &n );
	int cnt = 0;
	std::map<int, int> mp;
	for(int i = 1; i <= n; i ++) {
		scanf( "%d", &a[i] );
		if( mp.count(a[i]) ) 
			a[i] = mp[ a[i] ];
		else {
			cnt ++;
			mp[ a[i] ] = cnt;
			a[i] = cnt;
		}
	}
	for(int i = 1; i < n; i ++) {
		int u, v;
		scanf("%d%d", &u, &v);
		add_edge(u, v);
		add_edge(v, u);
	}

	dfs(1, 0);

	int ans = 0;
	for( int i = 1; i <= n; i ++ ) {
		sum[i] += sum[ i - 1 ];
		if( sum[i] == 0 )  {
			ans ++;
		}
	}

	printf( "%d\n", ans );

}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

message
account_circle
Please input name.
email
Please input email address.
links