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

时间:2021-11-20 16:59:14

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

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://uoj.ac/problem/31

Description

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

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

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

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

有一个由 n 个左括号 “(” 和 n 个右括号 “)” 组成的序列。每次操作时可以选定两个数 l,r,然后把第 l 到第 r 个括号的顺序翻转(括号的朝向保持不变)。例如将 “()((()(” 翻转第 3 到第 7 个括号后的结果为 “()()(((”。

我希望使用不超过 n 次操作,将这个序列变为一个合法的括号序列。

众所周知,合法括号序列的定义如下:

  1. () 是合法括号序列;
  2. 如果 A 是合法括号序列,则 (A) 是合法括号序列;
  3. 如果 A,B 是合法括号序列,则 AB 是合法括号序列。

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

Input

一行一个长度为 2n 的非空字符串表示初始序列。保证字符串只包含左括号和右括号,且左右括号的个数均为 n。

Output

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

否则,第一行一个整数 m 表示要进行 m 次翻转操作。

接下来 m 行每行两个整数 l,r 表示要翻转区间 [l,r] 内的括号顺序。翻转操作会按你输出的顺序执行。

请保证 m≤n 以及 1≤l≤r≤2n,否则会被判 0 分。

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

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=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
//************************************************************************************** int tot;
int ansl[maxn],ansr[maxn];
char s[maxn];
int sum = ;
int flag = -;
int main()
{
scanf("%s",s);
int len = strlen(s);
for(int i=;i<len;i++)
{
sum += s[i] == '(' ? : - ;
if(sum==&&flag!=-)
{
ansl[tot]=flag;
ansr[tot++]=i+;
flag=-;
}
if(sum<&&flag==-)
flag = i+;
}
printf("%d\n",tot);
for(int i=;i<tot;i++)
printf("%d %d\n",ansl[i],ansr[i]);
}
#include<cstring>
#include<cstdio>
using namespace std;
char s[];
int main() {
scanf("%s",s+);int tot=;
int len = strlen(s+);
printf("%d\n",len/);
for (int i=;i<=len;++i)if (s[i]=='(')printf("%d %d\n",++tot,i);
return ;
}