2015 湘潭大学程序设计比赛(Internet)H题-括号匹配
2024-08-25 21:56:57
括号匹配 |
||
Accepted : 30 | Submit : 234 | |
Time Limit : 10000 MS | Memory Limit : 65536 KB |
题目描述有一串括号(只包含"(", ")", "[", "]", "{", "}"), 保证这一括号串是匹配的, 长度小于100000, 有m个询问, 每个询问为一个整数x;对于每一个询问, 要求输出一行四个整数y, a, b, c; 表示第x个括号是跟第y个配对的, x和y之间有a对小括号, b对中括号, c对大括号。 输入约200个样例, 每个样例第一行为一个只包含括号的长度小于100000的字符串, 第二行一个小于100000的整数m, 接下来m行每行一个整数x,x不大于括号字符串的长度, x > 0; 输出每个询问输出一行四个整数y, a, b, c,用空格隔开。每个样例之后输出一个空行 样例输入(){}[] 样例输出2 0 0 0 SourceCKBoss |
代码如下:
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stack>
#define N 100100
using namespace std; struct node
{
int index,k,pre,r[];//k是看它是哪种括号,pre是对应的另一半下标,r[1]是小括号,其次是中括号,大括号;
}; char str[N];
node a[N]; int main()
{
node q,t;
int i,m,x,j;
int b[]={}; b['(']=;b['[']=;b['{']=;
b[')']=;b[']']=;b['}']=; while(scanf("%s",str+)!=EOF)
{
stack<node>sta;
memset(a,0,sizeof(a));
for(i=;str[i];i++)
{
a[i].index=i;
a[i].k=b[str[i]];
if(a[i].k<=)
{
sta.push(a[i]);
}
else
{
q=sta.top();
sta.pop();
a[i].pre=q.index;
q.pre=i;
if(sta.size())
{
t=sta.top();
sta.pop();
t.r[]+=q.r[];t.r[]+=q.r[];t.r[]+=q.r[];
t.r[q.k]+=;
sta.push(t);
}
a[q.index]=q;
}
}
scanf("%d",&m);
for(i=;i<m;i++)
{
scanf("%d",&x);
j=min(x,a[x].pre);
printf("%d %d %d %d\n",a[x].pre,a[j].r[],a[j].r[],a[j].r[]);
}
}
return ;
}
http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1232
最新文章
- php正则预查
- 51nod1069(nim博弈)
- mysql varchar
- appfabric 简单应用
- CSS边框阴影效果
- dubbo 线程池
- 小程序2-基本架构讲解(一)WXML 模板
- 绑定Oracle Database 到 ActiveReport
- 移动网络应用开发中,使用 HTTP 协议比起使用 socket 实现基于 TCP 的自定义协议有哪些优势?
- SWT中ole/activex实践--操作word的一个例子
- Netbeans配置Java SE嵌入式平台(树莓派)
- linux 检查补丁包是否安装 名称 版本 release号
- Visual Event :快速查看 DOM 上绑定的 JS 事件
- Java多线程(六) —— 线程并发库之并发容器
- ASP.NET MVC 编程参考
- mac下的安装神奇 brew --例子 安装 mysql
- Maven及POM文件
- 【bzoj3672】[Noi2014]购票 斜率优化dp+CDQ分治+树的点分治
- Leecode刷题之旅-C语言/python-26.移除元素
- 第十章 用户数据报协议和IP分片
热门文章
- [Command] wc
- 手机CPU天梯图2018年5月最新版
- windows下dump文件调试
- java基础思维导图大全
- 【转】Reason: The specified virtual disk needs repair.
- php获取ios或android通过文件头(header)传过来的坐标,通过百度接口获取具体城市和地址,并存入到session中。
- 【Spring Boot&;&;Spring Cloud系列】提高数据库访问性能
- Excel中用countif和countifs统计符合条件的个数 good
- JavaScript怎样学
- SOA面向服务的架构