Codeforces Round #692 (Div. 1, based on Technocup 2021 Elimination Round 3) C.(思维题-贪心)
2021/7/6 23:06:13
本文主要是介绍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.(思维题-贪心)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-07Dify + TiDB Vector,快速构建你的AI Agent
- 2024-07-06有没有什么开源的py项目可以对图像进行分类-icode9专业技术文章分享
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享