6

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

 3 years ago
source link: https://blog.woshiluo.com/1824.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

即 Codeforces Round #695 (Div. 2)

许久不打变得更菜了…

A. Wizard of Orz

给定 n 个板子，每个板子上有一个相同的数字 x(0≤x≤9)

随机选择一个数字 y(1≤y≤n)，令板子 i 上的数字变成 x+|y–i|(mod1)0

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

给定一个长度为 n 的序列，对于∀i(1≤i≤n)，如果满足 ai<ai−1,ai<ai+1 或 ai>ai−1,ai>ai+1 则对答案贡献 1

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

对于 i, 我们令 max=max(ai+1,ai−1),min=min(ai+1,ai−1)

则显然只有 ai={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

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

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

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

  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

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

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

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

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 题目大意

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

带修，只修改一个点

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

  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 );

}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK