cf1248 D1. The World Is Just a Programming Task (Easy Version)
2022/4/18 6:17:12
本文主要是介绍cf1248 D1. The World Is Just a Programming Task (Easy Version),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意:
给定一个括号串。若把子串 \([1,i]\) 换到子串 \([i+1,n]\) 的后面,得到的新串合法,则称 \(i\) 为一个特殊位置。
现在交换两个位置,问交换哪两个位置可使特殊位置最多。
串长 500
思路:
n^2 枚举位置进行交换,然后 \(O(n)\) 数特殊位置数:
求括号串的平衡前缀数组,即把左括号看成 1,右括号看成 -1,然后做前缀和。
首先总左括号数要等于总右括号数,即 \(s_n=0\),否则答案是 0。
如果我们把子串 \([1,i]\) 换到子串 \([i+1,n]\) 的后面,那么 \(s[i+1,n]\) 要消除 \(s[1,i]\) 的影响,即 \(s[i+1,n]\) 中的所有 \(s\) 减去 \(s_i\);
然后 \(s[1,i]\) 放到后面后,要加上 \(s[i+1,n]\) 的影响,即 \(s[1,i]\) 中的所有 \(s\) 加上 \(s_n\)。注意到经过上一步后,这个 \(s_n=-s_i\),所以这步操作也是把 \(s[1,i]\) 中的所有 \(s\) 减去 \(s_i\)
综上,就是要把所有数减去 \(s_i\) 。
众所周知,括号序列合法要求所有前缀和非负,所以特殊位置只能取 \(s_i\) 最小的 \(i\)
所以每次数最小的 \(s_i\) 的有几个即可
const signed N = 503; int n, s[N], ans, l=1, r=1; char a[N]; int cal() { for(int i = 1; i <= n; i++) s[i] = s[i-1] + (a[i] == '(' ? 1 : -1); if(s[n]) return 0; int mn = *min_element(s+1, s+1+n), cnt = 0; for(int i = 1; i <= n; i++) cnt += s[i] == mn; return cnt; } signed main() { iofast; cin >> n >> a + 1; for(int i = 1; i <= n; i++) for(int j = i; j <= n; j++) { swap(a[i], a[j]); int res = cal(); if(ans < res) ans = res, l = i, r = j; swap(a[i], a[j]); } cout << ans << endl << l << ' ' << r; }
这篇关于cf1248 D1. The World Is Just a Programming Task (Easy Version)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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功能效果提升