C/C++教程

Codeforces Round #692 (Div. 1, based on Technocup 2021 Elimination Round 3) C.(思维题-贪心)

本文主要是介绍Codeforces Round #692 (Div. 1, based on Technocup 2021 Elimination Round 3) C.(思维题-贪心),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目

思路来源

https://blog.csdn.net/hzerotole/article/details/111478668

题解

首先,要证明①倒数第二个一定是减②倒数第一个一定是加

③还要证明前面的符号可以任意选,

感觉思路来源证明的很好,自己在做的时候只是手动找了一下规律,

数学归纳法可以证明①-②,但是自己不会证③

证明完之后,对于要凑的t,贪心即可

代码1

类似钟摆,最终的目的是0,如果为正就减,为负就加,

由于成倍数关系,所以远0的方向仍然需要后续被走回,一定不优

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m;
ll t,a[N];
char s[N]; 
ll cal(char x){
	return 1<<(x-'a');
}
int main(){
	scanf("%d%lld",&n,&t);
	scanf("%s",s+1);
	t-=cal(s[n]);
	t+=cal(s[n-1]);
	m=n-2;
	for(int i=1;i<=m;++i){
		a[i]=cal(s[i]);
	}
	sort(a+1,a+m+1,greater<ll>());
	for(int i=1;i<=m;++i){
		if(t>=0)t-=a[i];
		else t+=a[i];
	}
	puts(!t?"Yes":"No");
	return 0;
}

代码2

考虑n个数先全减,然后对于那些原本需要加的数,需要加2倍

这样就变成了一个套路问题,剩下需要加的值贪心加即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m;
ll t,a[N];
char s[N]; 
ll cal(char x){
	return 1<<(x-'a');
}
int main(){
	scanf("%d%lld",&n,&t);
	scanf("%s",s+1);
	t-=cal(s[n]);
	t+=cal(s[n-1]);
	m=n-2;
	for(int i=1;i<=m;++i){
		a[i]=cal(s[i]);
		t-=a[i];
		a[i]<<=1;
	}
	sort(a+1,a+m+1,greater<ll>());
	t=-t;
	for(int i=1;i<=m;++i){
		if(t>=a[i]){
			t-=a[i];
		}
	}
	puts(!t?"Yes":"No");
	return 0;
}

这篇关于Codeforces Round #692 (Div. 1, based on Technocup 2021 Elimination Round 3) C.(思维题-贪心)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!