P3015 [USACO11FEB]最好的括号Best Parenthesis
2024-09-02 07:35:53
P3015 [USACO11FEB]最好的括号Best Parenthesis
题解
一定要开 long long !!!
通过阅读英文题面我们知道所给出的字符串是已经匹配好的,所以我们只是计算就好了
考虑栈模拟实现,每一个括号都视作一层
设数组 s[ i ] 为栈中第 i 层左括号所积累的得分
(1)当输入0,也就是入栈一个左括号,那么我们s[ ]数组就往下开拓新的一层
(2)当输入1,也就是入栈一个右括号,当前层为右括号,此时有两种情况:
<1> 上一层的左括号本身没有得分,也就是我们当前的右括号与最近的也就是上一层的左括号匹配,凑出一个()这样的括号,所以把上一层的左括号出栈,它的贡献值为1,添加到上上层的左括号里(因为上上层左括号可能本身就有得分),有:
<2> 上一层的左括号本身有得分,实际上我们当前的右括号并不是与最近的也就是上一层的左括号匹配,而是与上上层的括号匹配,即我们得到 (())括号套括号(灰色括号代表已经出栈消掉了),所以内部括号得分*2添加到上上一层左括号里,有:
注意上一层的左括号出栈时候清空其得分
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<queue> using namespace std; typedef long long ll; inline int read()
{
int ans=;
char last=' ',ch=getchar();
while(ch<''||ch>'') last=ch,ch=getchar();
while(ch>=''&&ch<='') ans=ans*+ch-'',ch=getchar();
if(last=='-') ans=-ans;
return ans;
} const int maxn=1e5+;
const ll mod=;
int x,n;
ll s[maxn],top=; int main()
{
n=read();
for(int i=;i<=n;i++){
x=read();
if(!x) top++;
else{
if(s[top]==) s[top-]=(s[top-]+)%mod,top--;
else{
s[top-]=(s[top-]+s[top]*)%mod,s[top]=,top--;
}
}
}
printf("%lld\n",s[]);
return ;
}
最新文章
- XML 序列化与反序列化
- css3的新特性transform,transition,animation
- C#:向exe传值
- 关于计算机的ID和用户ID之间的关系
- cocos2d-x内存管理(见解)
- TCP协议RST:RST介绍、什么时候发送RST包
- 使用graphics2D给图片上画字符
- SGU 145.Strange People(无环K短路)
- SQL Server中的临时表和表变量 Declare @Tablename Table
- Host &#39;hello-PC&#39; is not allowed to connect to this MySQL server远程连接mysql授权
- tensorflow官方文档中的sub 和mul中的函数已经在API中改名了
- java构建学生管理系统(一)
- antd form 自定义验证表单使用方法
- day 24 二十四、组合、继承、方法重写和重用、super()
- PHPMailer出现SMTP connect() failed.
- 记一次yarn导致cpu飙高的异常排查经历
- default construction
- maven配置私服
- centos7:mysql-5.7.23安装(二进制安装)
- SQL语句常见视图操作部分试题(一)
热门文章
- 【2017-12-12】Winform----Datagirdview使用
- NLP学习(2)----文本分类模型
- 通过字节码分析this关键字以及异常表的重要作用
- 0002SpringBoot整合Junit
- Java并发包--LinkedBlockingDeque
- 前端知识体系:JavaScript基础-原型和原型链-理解 es6 中class构造以及继承的底层实现原理
- combogrid下拉方法封装
- C语言定义数组时使用枚举作为数组的下标 ——c99功能
- 2019牛客多校D move——乱搞&;&;思维题
- BZOJ 2229 / Luogu P3329 [ZJOI2011]最小割 (分治最小割板题)