uoj #31. 【UR #2】猪猪侠再战括号序列贪心

#31. 【UR #2】猪猪侠再战括号序列

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://uoj.ac/problem/31

Description

大家好我是来自百度贴吧的_叫我猪猪侠，英文名叫_CallMeGGBond。

我不曾上过大学，但这不影响我对离散数学、复杂性分析等领域的兴趣；尤其是括号序列理论，一度令我沉浸其中，无法自拔。至于OI算法竞赛，我年轻时确有参加，虽仅获一枚铜牌，但我素性淡泊，毫不在意，毕竟那所谓FFT、仙人掌之类，只是些雕虫小技罢了，登不上大雅之堂的；只有括号序列才会真正激发我的研究热情。

我曾天真地以为，凭借我的学识与才能，足可以在这世间安身立命；然而直到沦落街头后，我终才领悟现实的残酷。迫于生计，我只得转向道德与哲学的研究；但我与括号序列之间情愫依旧，难以剪断。

理性的传播总是不顺的，研究的道路也是曲折的，但轻易放弃决不是我的风格；为了继续实现自己的理想，现在我向大家提出一道括号序列的超级大难题。

有一个由

我希望使用不超过

众所周知，合法括号序列的定义如下：

() 是合法括号序列；
如果 A 是合法括号序列，则 (A) 是合法括号序列；
如果 A，B 是合法括号序列，则 AB 是合法括号序列。

自从来到 UOJ 这个宝地，我的视野变得开阔了，也见识了更多富有人类智慧的人士。我相信各位一定能给我更加满意的答案！

Input

一行一个长度为

Output

对于给出的字符串，输出调整成合法的括号序列的方案。如果不存在这样的方案输出一行一个整数

否则，第一行一个整数

接下来

请保证

如果有多组方案，输出任意一组即可。

Sample Input

)))()(((

Sample Output

2
1 6
5 8

HINT

题意

题解：

贪心

有很多种贪心方法，我说两种

直接看代码吧

代码：

//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <bitset>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 320051
#define mod 10007
#define eps 1e-9
int Num;
//const int inf=0x7fffffff;   //нчоч╢С
const int inf=0x3f3f3f3f;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//**************************************************************************************

int tot;
int ansl[maxn],ansr[maxn];
char s[maxn];
int sum = 0;
int flag = -1;
int main()
{
    scanf("%s",s);
    int len = strlen(s);
    for(int i=0;i<len;i++)
    {
        sum += s[i] == '(' ? 1 : -1 ;
        if(sum==0&&flag!=-1)
        {
            ansl[tot]=flag;
            ansr[tot++]=i+1;
            flag=-1;
        }
        if(sum<0&&flag==-1)
            flag = i+1;
    }
    printf("%d
",tot);
    for(int i=0;i<tot;i++)
        printf("%d %d
",ansl[i],ansr[i]);
}

#include<cstring>
#include<cstdio>
using namespace std;
char s[500005];
int main() {
    scanf("%s",s+1);int tot=0;
    int len = strlen(s+1);
    printf("%d
",len/2);
    for (int i=1;i<=len;++i)if (s[i]=='(')printf("%d %d
",++tot,i);
    return 0;
}

uoj #31. 【UR #2】猪猪侠再战括号序列 贪心

#31. 【UR #2】猪猪侠再战括号序列

uoj #31. 【UR #2】猪猪侠再战括号序列贪心