专业模板网站制作,衡水做wap网站价格,现在什么网站做推广比较好,有赞商城传送门http://uoj.ac/problem/31 大家好我是来自百度贴吧的_叫我猪猪侠#xff0c;英文名叫_CallMeGGBond。 我不曾上过大学#xff0c;但这不影响我对离散数学、复杂性分析等领域的兴趣#xff1b;尤其是括号序列理论#xff0c;一度令我沉浸其中#xff0c;无法自拔。至…传送门http://uoj.ac/problem/31 大家好我是来自百度贴吧的_叫我猪猪侠英文名叫_CallMeGGBond。 我不曾上过大学但这不影响我对离散数学、复杂性分析等领域的兴趣尤其是括号序列理论一度令我沉浸其中无法自拔。至于OI算法竞赛我年轻时确有参加虽仅获一枚铜牌但我素性淡泊毫不在意毕竟那所谓FFT、仙人掌之类只是些雕虫小技罢了登不上大雅之堂的只有括号序列才会真正激发我的研究热情。 我曾天真地以为凭借我的学识与才能足可以在这世间安身立命然而直到沦落街头后我终才领悟现实的残酷。迫于生计我只得转向道德与哲学的研究但我与括号序列之间情愫依旧难以剪断。 理性的传播总是不顺的研究的道路也是曲折的但轻易放弃决不是我的风格为了继续实现自己的理想现在我向大家提出一道括号序列的超级大难题。 有一个由 nn 个左括号 “(” 和 nn 个右括号 “)” 组成的序列。每次操作时可以选定两个数 l,rl,r然后把第 ll 到第 rr 个括号的顺序翻转括号的朝向保持不变。例如将 “()((()(” 翻转第 33 到第 77 个括号后的结果为 “()()(((”。 我希望使用不超过 nn 次操作将这个序列变为一个合法的括号序列。 众所周知合法括号序列的定义如下 () 是合法括号序列如果 A 是合法括号序列则 (A) 是合法括号序列如果 AB 是合法括号序列则 AB 是合法括号序列。自从来到 UOJ 这个宝地我的视野变得开阔了也见识了更多富有人类智慧的人士。我相信各位一定能给我更加满意的答案 输入格式 一行一个长度为 2n2n 的非空字符串表示初始序列。保证字符串只包含左括号和右括号且左右括号的个数均为 nn。 输出格式 对于给出的字符串输出调整成合法的括号序列的方案。如果不存在这样的方案输出一行一个整数 −1−1。 否则第一行一个整数 mm 表示要进行 mm 次翻转操作。 接下来 mm 行每行两个整数 l,rl,r 表示要翻转区间 [l,r][l,r] 内的括号顺序。翻转操作会按你输出的顺序执行。 请保证 m≤nm≤n 以及 1≤l≤r≤2n1≤l≤r≤2n否则会被判 0 分。 如果有多组方案输出任意一组即可。 样例一 input )))()((( output 2
1 6
5 8 explanation 第一次操作后序列变为 “()()))((”。 第二次操作后序列变为 “()()(())”。 限制与约定 测试点编号nn的规模1n≤4n≤42n≤100n≤1003456n≤100000n≤10000078910 时间限制1s1s 空间限制256MB 扫描 构造 脑洞题 显然最方便的结果是((()))的形式。 维护双指针扫描head指向第一个右括号tail指向head后面的第一个左括号每步将两个位置的括号交换。 显然是 $ O(n) $的 1 #includeiostream2 #includecstring3 #includecstdio4 using namespace std;5 char s[200010];6 int ans0,L[100010],R[100010];7 int main(){8 int i;9 scanf(%s,s1);
10 int nstrlen(s1);
11 int hd1;
12 for(i1;in;i){
13 if(s[i](){
14 while(hdi s[hd]!))hd;
15 if(hd^i){
16 swap(s[hd],s[i]);
17 ans;
18 L[ans]hd;R[ans]i;
19 }
20 }
21 }
22 printf(%d\n,ans);
23 for(i1;ians;i){
24 printf(%d %d\n,L[i],R[i]);
25 }
26 return 0;
27 } 转载于:https://www.cnblogs.com/SilverNebula/p/7061334.html
