题目
思路来源
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;
}