Codeforces Round 938 (Div. 3) A - F 题解

发布于：2024-04-09 ⋅ 阅读:(137) ⋅ 点赞:(0)

A. Yogurt Sale

题意：要购买n个酸奶，有两种买法，一种是一次买一个，价格a。一种是一次买两个，价格b，问买n个酸奶的最小价格。
题解：很容易想到用2a和b比较，判断输出即可。
代码：
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 4e5 + 7 ;
inline ll read(){
	ll x = 0 , f = 1 ;
	char c = getchar() ;
	while(c > '9' || c < '0'){
		if(c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
ll t , n , k , c , a[maxn] ;
ll head[maxn] , nxt[maxn] , ver[maxn] , cnt , ans ;

void solve(){
	n = read() ;
	k = read() ;
	c = read() ;
	if(k * 2 <= c){
		cout << n * k << endl ;
		return ;
	}
	else{
		cout << (n / 2) * c + (n - (n / 2) * 2) * k << endl ;
	}
}

int main(){
	t = read() ;
	while(t --){
		solve() ;
	}
	return 0 ;
}

B. Progressive Square

题意：给你n，c，d，你要生成n*n的矩阵，按照规则a_{i+ 1,j} = a_{i,j} + c , a_{i,j + 1} = a_{i,j} + d。给你n*n个数字，看看能否生成这样的矩阵并且包含所有数字。
题解：用最小数字开始枚举即可，n范围在500，轻松通过。
代码：
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 1e6 + 7 ;
inline ll read(){
	ll x = 0 , f = 1 ;
	char c = getchar() ;
	while(c > '9' || c < '0'){
		if(c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
ll t , n , k , c , a[maxn] ;
ll head[maxn] , nxt[maxn] , ver[maxn] , cnt , ans ;
ll b[550][550] ;
vector < ll > q ;
void solve(){
	q.clear() ;
	n = read() ;
	k = read() ;
	c = read() ;
	for(int i = 1 ; i <= n * n ; i ++){
		a[i] = read() ;
	}
	sort(a + 1 , a + n * n + 1) ;
	ll rt = a[1] ;
	b[1][1] = rt ;
	for(int i = 2 ; i <= n ; i ++){
		b[1][i] = b[1][i - 1] + c ;
  	}
	for(int i = 2 ; i <= n ; i ++){
		for(int j = 1 ; j <= n ; j ++){
			b[i][j] = b[i - 1][j] + k ;
		}
	}
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= n ; j ++){
			q.push_back(b[i][j]) ;
		}
	}
	sort(q.begin() , q.end()) ;
	ll Rt = 0 ;
	for(int i = 1 ; i <= n * n ; i ++){
		if(q[Rt] != a[i]){
			cout << "NO\n" ;
			return ;
		}
		Rt ++ ;
	}
	cout << "YES" << endl ;
}

int main(){
	t = read() ;
	while(t --){
		solve() ;
	}
	return 0 ;
}

C. Inhabitant of the Deep Sea

题意： 给你n个数字和k，每次怪兽都会按照攻击前面一次再攻击后面一次的顺序攻击，每次造成1滴血量伤害，问最多能击败多少个船。
题解：可以将k分解成两部分，然后枚举统计答案即可。
代码：
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 1e6 + 7 ;
inline ll read(){
	ll x = 0 , f = 1 ;
	char c = getchar() ;
	while(c > '9' || c < '0'){
		if(c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
ll t , n , k , c , a[maxn] ;
ll head[maxn] , nxt[maxn] , ver[maxn] , cnt , ans ;
vector < ll > q ;
void solve(){
	n = read() ;
	k = read() ;
	for(int i = 1 ; i <= n ; i ++){
		a[i] = read() ;
	}
	ll l = (k + 2 - 1) / 2 ;
	ll r = k / 2 ;
	ll rt = 1 ;
	ll ans = 0 ;
	while(l != 0){
		if(rt > n){
			break ;
		}
		if(l - a[rt] >= 0){
			l -= a[rt] ;
			ans ++ ;
			a[rt] = 0 ;
			rt ++ ;
		}
		else{
			a[rt] -= l ;
			l = 0 ;
			break ;
		}
	}
	rt = n ;
	while(r != 0){
		if(rt < 1){
			break ;
		}
		if(a[rt] == 0){
			break ;
		}
		if(r - a[rt] >= 0){
			r -= a[rt] ;
			ans ++ ;
			a[rt] = 0 ;
			rt -- ;
		}
		else{
			a[rt] -= r ;
			r = 0 ;
			break ;
		}
	}
	cout << ans << endl ;
}

int main(){
	t = read() ;
	while(t --){
		solve() ;
	}
	return 0 ;
}

D. Inaccurate Subsequence Search

题意：给你一个数组a和数组b，长度分别为n和m，看看有多少组可以满足1<=l<=n - m + 1满足至少有k个相同的数字？
题解：可以用STL里的map来统计数组b，然后先用map统计1-m的数字有多少相同的，定义l = 1, r = m，然后每次让l++，r++，统计有多少个相同数字，直接统计答案即可。
代码：
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 1e6 + 7 ;
inline ll read(){
	ll x = 0 , f = 1 ;
	char c = getchar() ;
	while(c > '9' || c < '0'){
		if(c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
ll t , n , k , c , a[maxn] , b[maxn] ;
ll head[maxn] , nxt[maxn] , ver[maxn] , cnt , ans ;
vector < ll > q ;
void solve(){
	map < ll , ll > mp , p ;
	n = read() ;
	k = read() ;
	c = read() ;
	for(int i = 1 ; i <= n ; i ++){
		a[i] = read() ;
	}
	for(int i = 1 ; i <= k ; i ++){
		b[i] = read() ;
		mp[b[i]] ++ ;
	}
	ll sum = 0 , ans = 0 ;
	for(int i = 1 ; i <= k ; i ++){
		p[a[i]] ++ ;
		if(p[a[i]] <= mp[a[i]]){
			sum ++ ;
		}
	}
	if(sum >= c){
		ans ++ ;
	}
	ll l = 1 , r = k ;
	while(1){
		if(r >= n){
			break ;
		}
		if(p[a[l]] - 1 < mp[a[l]]){
			sum -- ;
			p[a[l]] -- ;
		}
		else{
			p[a[l]] -- ;
		}
		if(p[a[r + 1]] + 1 <= mp[a[r + 1]]){
			sum ++ ;
			p[a[r + 1]] ++ ;
		}
		else{
			p[a[r + 1]] ++ ;
		}
		if(sum >= c){
			ans ++ ;
		}
		l ++ ;
		r ++ ;
	}
	cout << ans << endl ;
}

int main(){
	t = read() ;
	while(t --){
		solve() ;
	}
	return 0 ;
}

E. Long Inversions

题意：给你一个字符串s，可以选择一个k，每次修改i<=l<=i + k - 1，翻转里面所有的数字，将0变成1，将1变成0，目标是想要将序列全部变成1,。问能满足最大的k是多少。
题解：看到最大的k，先想到了二分，能否从小推大，但是发现不行，那么看到数据n<=5000，那么可以想到枚举即可，n^2logn可以通过，首先思考怎么看能否能将所有的数字变成1，很明显从前面到后面依次遍历，如果碰到了0，那么就翻转当前位置i到i + k - 1。那么现在的复杂度是n^3，很明显通过不了。那么就想到了数据结构，那么就想到用树状数组来维护。如果说当前为0，那么就让i<=j<=i + k - 1加1，如果说(a[i] + query(a[i]) mod 2) mod 2等于0，那么就区间增加1，如果说等于1那么就不修改，最后遍历一遍看看是否全为1即可。复杂度O(n^2logn)。

代码：

#include<bits/stdc++.h>
#define ll long long
const int maxn = 5000 + 7 ;
using namespace std;
ll t , n , m , p , l , r , a[maxn] , tree[maxn] ;
char s[maxn];
inline ll read(){
	ll x = 0 , f = 1 ;
	char c = getchar() ;
	while(c > '9' || c < '0'){
		if(c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
ll lowbit(ll x){
	return x & (-x) ;
}
void update(ll x , ll y){
	for( ;x <= n ; x += lowbit(x)){
		tree[x] += y ;
	}
}
ll Query(ll x){
	ll ans = 0 ;
	while(x != 0){
		ans += tree[x] ;
		x -= lowbit(x) ;
	}
	return ans ;
}
void solve(){
	n = read() ;
	scanf("%s" , s + 1) ;
	for(int i = 1 ; i <= n ; i ++) 
		a[i] = s[i] - '0' ;
	for(int i = n ; i >= 1 ; i --){
		for(int j = 0 ; j <= n ; j ++){
			tree[j] = 0 ;
		}
		bool f = 0 ;
		for(int j = 1 ; j + i - 1 <= n ; j ++){
			ll res = (a[j] + (Query(j) % 2)) % 2 ;
			if(res == 0){
				update(j , 1) ;
				update(j + i , -1) ;
			}
		}
		for(int j = 1 ; j <= n ; j ++){
			ll res = (a[j] + (Query(j) % 2)) % 2 ;
			if(res == 0){
				f = 1 ;
			}
		}
		if(f == 0){
			cout << i << endl ;
			return ;
		}
	}
	cout << 1 << endl ;
}
int main()
{
	t = read() ;
	while(t --){
		solve() ;
	}
	return 0;
}
注：也不知道为什么，我一开始用线段树写T了5发，也不知道是我常熟大吗！

F. Unfair Game

题意：给你四个数字，分别代表1,2,3,4的数量，Alice和Bob在进行游戏，如果说所有的数字异或和不为0那么Alice赢，如果说是0那么Bob赢，Eve每次会去掉一个数字，每次都用最优的方式去掉数字，问最多Bob能获胜多少次。
题解：这个题其实很好想，首先可以想到4只要有那么就一定和1，2,3没有任何关系，因为无法组成0，那么就将4的数量单独拿出来看，再看1，2,3的数量，可以想到1和2可以和3抵消掉，然后就可以想出一种方法，就是将1,2,3的数量取min，然后加上4的数量除以2，是一种情况，再看如果说每个的数字是偶数的话，那么很明显比1,2,3抵消要更优，因为每个数字是偶数，如果说是第一种情况最多是2，但是第二种情况每次减2的话答案可以增加3。最后就是特殊的情况，比如1,2，3的数量一样，并且全是奇数，那么答案要加1。如果说三个数字都是奇数，那么答案也要加1。这个题就迎刃而解了。复杂度非常低！
代码：
#include<bits/stdc++.h>
#define ll long long
const int maxn = 5000 + 7 ;
using namespace std;
ll t , n , m , p , l , r , tree[maxn] ;
char s[maxn];
inline ll read(){
	ll x = 0 , f = 1 ;
	char c = getchar() ;
	while(c > '9' || c < '0'){
		if(c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
ll a , b , c , d ;
void solve(){
	a = read() ;
	b = read() ;
	c = read() ;
	d = read() ;
	bool f = 0 ;
	if((a == b && b == c && a % 2 == 1) || ((a % 2 == 1) && (b % 2 == 1) && (c % 2 == 1))){
		f = 1 ;
	}
	ll res = (min(min(a , b) , c) + d / 2) ;
	ll Res = (a / 2) + (b / 2) + (c / 2) + (d / 2) + ((f == 1) ? 1 : 0) ;
	cout << max(res , Res) << endl ;
}                                                                                                                                                                                              
int main()
{
	t = read() ;
	while(t --){
		solve() ;
	}
	return 0;
}

喜欢作者的记得点赞收藏加关注哦~

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布