括弧のマッチング
6097 ワード
括弧のマッチング
Acceepted:30
Submit:225
Time Limit:10000 MS
メモリLimit:65536 KB
http://202.197.224.59/OnlineJudge2/index.php/Contest/read_problem/cid/38/pid/1232
テーマの説明
括弧があります。この括弧はマッチしています。長さは100000以下で、m個の問い合わせがあります。各問い合わせは整数xです。各クエリについては、1行4つの整数y,a,b,cを出力することが要求される。x番目の括弧はy番目と対になっています。xとyの間にはa対小かっこ、b対中かっこ、c対大括弧があります。
入力
約200のサンプルでは、各サンプルの第一行為は括弧の長さが100000以下の文字列を含み、第二行は100000以下の整数mであり、次のm行は整数xであり、xは括弧文字列の長さより大きくない。x>0;
出力
各クエリは、行の4つの整数yを出力します。a、b、cは、スペースで区切られます。サンプルごとに空行を出力します。
サンプル入力
Acceepted:30
Submit:225
Time Limit:10000 MS
メモリLimit:65536 KB
http://202.197.224.59/OnlineJudge2/index.php/Contest/read_problem/cid/38/pid/1232
テーマの説明
括弧があります。この括弧はマッチしています。長さは100000以下で、m個の問い合わせがあります。各問い合わせは整数xです。各クエリについては、1行4つの整数y,a,b,cを出力することが要求される。x番目の括弧はy番目と対になっています。xとyの間にはa対小かっこ、b対中かっこ、c対大括弧があります。
入力
約200のサンプルでは、各サンプルの第一行為は括弧の長さが100000以下の文字列を含み、第二行は100000以下の整数mであり、次のm行は整数xであり、xは括弧文字列の長さより大きくない。x>0;
出力
各クエリは、行の4つの整数yを出力します。a、b、cは、スペースで区切られます。サンプルごとに空行を出力します。
サンプル入力
(){}[]
3
1
3
5
[([{()[]}])][()]
5
1
2
5
13
14
サンプル出力2 0 0 0
4 0 0 0
6 0 0 0
12 2 2 1
11 1 2 1
6 0 0 0
16 1 0 0
15 0 0 0
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<queue>
#include<stack>
using namespace std;
#define maxn 100005
char s[maxn];
struct node
{
int k, index;// 0, 1, 2
int r[4], pre;
};
node a[maxn];
int main()
{
while(scanf("%s", s+1) != EOF)
{
int i, x;
int val[200]={0};
node q;
stack <node> sta;
memset(a, 0, sizeof(a));
val['('] = 1;val['['] = 2;val['{'] = 3;
val[')'] = 4;val[']'] = 5;val['}'] = 6;
for(i=1; s[i]; i++)
{
a[i].k = val[s[i]];
a[i].index = i;
if(a[i].k <= 3)
sta.push(a[i]);
else
{
q = sta.top();sta.pop();
a[i].pre = q.index;
q.pre = i;
if(sta.size())
{
node t = sta.top();sta.pop();
t.r[1] += q.r[1], t.r[2] += q.r[2], t.r[3] += q.r[3];
t.r[ q.k ] += 1;
sta.push(t);
}
a[q.index] = q;
}
}
int N, j;
scanf("%d", &N);
for(i=0; i<N; i++)
{
scanf("%d", &x);
j = min(x, a[x].pre);
printf("%d %d %d %d
", a[x].pre, a[j].r[1], a[j].r[2], a[j].r[3]);
}
printf("
");
}
return 0;
}
:
#include<iostream>
#include<stdio.h>
using namespace std;
#define min(a, b)(a < b ? a : b)
#define N 100009
char str[N];
struct node
{
int y, a, b, c;
}P[N];
int main()
{
int i, j, m, x, y, a, b, c, d, q, A, B, C;
while(scanf("%s", str) != EOF)
{
for(j = 0; str[j]; j++)
{
d = 1;
q = 0;
P[j].y = P[j].a = P[j].b = P[j].c = 0;
a = b = c = A = B = C = 0;
if(str[j] == '(')
{
for(i = j+1; str[i]; i++)
{
if(str[i] == '(')
d++;
else if(str[i] == ')')
{
q++;
if(q == d)
{
y = i;
break;
}
}
}
}
if(str[j] == '[')
{
for(i = j+1; str[i]; i++)
{
if(str[i] == '[')
d++;
else if(str[i] == ']')
{
q++;
if(q == d)
{
y = i;
break;
}
}
}
}
if(str[j] == '{')
{
for(i = j+1; str[i]; i++)
{
if(str[i] == '{')
d++;
else if(str[i] == '}')
{
q++;
if(q == d)
{
y = i;
break;
}
}
}
}
for(i = j; i < y; i++)
{
if(str[i] == ')')
a++;
else if(str[i] == '(')
A++;
else if(str[i] == '{')
c++;
else if(str[i] == '}')
C++;
else if(str[i] == '[')
b++;
else if(str[i] == ']')
B++;
}
a = min(a, A);
b = min(b, B);
c = min(c, C);
P[j].y = y+1, P[j].a = a, P[j].b = b, P[j].c = c;
}
cin >> m;
while(m--)
{
cin >> x;
printf("%d %d %d %d
", P[x-1].y, P[x-1].a, P[x-1].b, P[x-1].c);
}
}
return 0;
}
ideas:
,well,well,well