CF1506G 题解
2022/8/27 23:22:46
本文主要是介绍CF1506G 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言
题目传送门!
更好的阅读体验?
校内考试题目。写一篇题解。
思路
首先记录每个字符出现了多少次,然后创建单调栈。
看当前字符是否入栈,如果没有入栈,就不停 pop()
,直到:
- 栈空了。
- 栈顶字典序大于当前字符。
- 栈顶元素已经被删掉了(因为栈外面用
cnt[i]
记录了每个数的次数)。
满足单调栈要求后,压入当前字符。
不管是不是将当前字符压入栈了,都要将对应计数器减一。
最后,整个栈从下往上就是答案了。
如果使用 STL 的 stack
,需要反着输出,这一点自己模拟一下栈的操作,就能理解了。
完整代码
#include <iostream> #include <cstdio> #include <cstring> #include <stack> #include <algorithm> using namespace std; void fastio() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); } const int N = 30; int cnt[N]; bool instk[N]; void solve() { memset(cnt, 0, sizeof(cnt)); //多测不清空,爆零两行泪!!! memset(instk, false, sizeof(instk)); string s; cin >> s; int len = s.length(); for (int i = 0; i < len; i++) cnt[s[i] - 'a']++; stack <int> stk; //单调栈 for (int i = 0; i < len; i++) { int x = s[i] - 'a'; if (!instk[x]) { while (!stk.empty() && cnt[stk.top()] && x > stk.top()) instk[stk.top()] = false, stk.pop(); stk.push(x), instk[x] = true; //没进栈就进栈 } cnt[x]--; //删除掉一个 } string ans = ""; while (!stk.empty()) ans += (stk.top() + 'a'), stk.pop(); reverse(ans.begin(), ans.end()); cout << ans << '\n'; } int main() { fastio(); int T; cin >> T; while (T--) solve(); return 0; }
希望能帮助到大家!
首发:2022-08-09 16:16:44
这篇关于CF1506G 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升