Compressed Bracket Sequence(cf1556C)
2021/9/4 23:35:46
本文主要是介绍Compressed Bracket Sequence(cf1556C),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Compressed Bracket Sequence
(https://codeforces.com/contest/1556/problem/C)
题意:
给定一个数组,下标为奇数的表示左括号连续数目,反之则表示右括号连续数目,求有多少个区间满足的括号满足正则表达式
思路:
我们可以计算从l+1到r−1段上的最小支架平衡。最小括号平衡是我们必须放置在括号序列之前的最小开始括号数量,以使它是规则的,前提是我们可以在末尾放置任意数量的结束括号。让我们将这个数字表示为minBalance,并将- cl+1+cl+2 - cl+2+…的总和表示为balance。
下观察,如果我们解决开括号取自cl的数量,然后我们可以计算括号的数量,我们应该从cr。使用这些观察我们可以计算的答案l . . r使用以下公式:min (cl, cr−balance)−max(minBalance) + 1。
代码:
#include <bits/stdc++.h> using namespace std; #define lowbit(x) x & -x #define int long long const int N=1100; int a[N]; signed main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } int cnt=0; for(int i=1;i<=n;i+=2){ int sum=0;int l=0; for(int j=i+1;j<=n;j++){ if(j%2==0){ int ll=-l; ll=max(1ll,ll); ll=max(ll,1-sum); int r=min(a[i],a[j]-sum);//a[j]减去之前留下的左括号代表还剩的右括号和a[i]的左括号取小值; if(r>=ll) cnt+=r-ll+1;//减去最少要添加左括号的数目后 } if(j%2) sum+=a[j]; else sum-=a[j]; l=min(l,sum);//在最前面至少要添加多少有个左括号 } } cout<<cnt<<endl; }
这篇关于Compressed Bracket Sequence(cf1556C)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级