1606A - AB Balance(构造性算法+字符串+级)
2021/10/30 14:12:23
本文主要是介绍1606A - AB Balance(构造性算法+字符串+级),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1606A - AB Balance(源地址自⇔CF1606A)
Problem
tag:
⇔构造性算法、⇔字符串、⇔级(*)
题意:
对于给定的只包含 \(a\) 和 \(b\) 的字符串,请你通过最少的修改次数,使得新的字符串中 \(ab\) 和 \(ba\) 的子串数量相同。输出这个新的子串
思路:
显然的,连续的 \(a\) 和连续的 \(b\) 交界处才有一次 \(ab\) ,连续的 \(b\) 和连续的 \(a\) 交界处才有一次 \(ba\) 。所以只要给定的字符串有偶数个交界,即符合题意。所以对于奇数个交界的字符串,只需要修改开始元素即可(使得交界变成偶数个)。可以证明,这种方法恒为最优的。
(附错误思路:如给定的字符串有奇数个交界,则去寻找字符串中最短的连续 \(a\) 或连续 \(b\) ,并修改这一整段。可以证明,这种方法不是最优的。)
AC代码:
//A WIDA Project #include <bits/stdc++.h> using namespace std; long long T, num; string s; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> T; while(T -- > 0) { num = 0; cin >> s; for(int i = 1; i < (int)s.size(); i ++) { if(s[i] != s[i - 1]) { num ++; } } if(num % 2 == 1) s[0] == 'a'? s[0] = 'b': s[0] = 'a'; cout << s << endl; } return 0; }
错误次数:4次
原因:思路完全错误(错误思路见上)。
文 / WIDA
2021.10.30成文
首发于WIDA个人博客,仅供学习讨论
更新日记:
2021.10.30 成文
这篇关于1606A - AB Balance(构造性算法+字符串+级)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-08测试人员在 Scrum 中的角色是什么?
- 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专业技术文章分享