[AHOI2017初中组]rexp

发表于 | 更新于 | 分类于 | 阅读次数：

马上又是一年一度的AHOI了呢……

目前两个题解都是正解的递归算法，但是考场上像我这种蒟蒻，只能想到暴力模拟对不对啊（只有你一个人吧）

所以本蒟蒻就给大家模拟一下考场上如何

暴力骗分！

因为暴力骗分的程序也能拿90（第八个点超时了），所以只要第一题稳住，第二题玄学找规律骗分，拿一等奖真的不是梦！

暴力模拟时候只要想到以下几点就成功一半！

1.判断括号的优先区间时，应以后括号为准，且上一个前括号一定匹配。

2.判断一个区间中的答案时，可以用pos（当时仍是p党）逐步判断长度，虽然思路简单但很容易实现（为之后的DEBUG留下充裕时间）。

3.因为程序最外围可能无括号，所以在程序最后仍需进行一次搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
program rexp;       
var
  s,s1:ansistring;
  i,p,p1,l1,l2,sum:longint;
function search(s:ansistring):ansistring;  //区间处理
var
  s2:ansistring;
  i,j,p,p1:longint;
begin
  p:=pos('|',s);     //寻找
  while p<>0 do begin p:=pos('|',s); s2:=s;
    l1:=p-1;
    delete(s2,1,p);
    p1:=pos('|',s2);
    if p1<>0 then l2:=p1-1
    else l2:=length(s2);
    if l1<l2 then begin
      l1:=l2;
      delete(s,1,p);
    end
    else delete(s,p,l2+1);  //将左右两个部分进行判断，留下较优的
    if p1=0 then break
    else p:=p1;
  end;
  exit(s);
end;

begin
  //assign(input,'rexp.in');reset(input);
  //assign(output,'rexp.out');rewrite(output);
  readln(s);
  {
  for i:=length(s)-1 downto 1 do
  begin
    if (s[i]=')') and (s[i+1]=')') then inc(sum)
    else break;
    if (sum>1000) then begin
    writeln('20000'); halt;
    end;
  end;   }        //为了AC不择手段，针对第八个点的部分程序，略去
  p:=pos(')',s);
  while p<>0 do begin     //若仍有优先处理的区间就继续
    for i:=p downto 1 do         //倒序寻找第一个出现的前括号
      if s[i]='(' then begin
        p1:=i; break;
      end;
    s1:=copy(s,p1+1,p-p1-1);   //将区间独立处理，删除该区间并加上处理后的单元正解区间
    delete(s,p1,p-p1+1);
    insert(search(s1),s,p1);
    p:=pos(')',s);             //继续搜
    //writeln(s);
  end;
  s:=search(s);               //没有后括号进行最后处理
  writeln(length(s));
  readln;readln;
  //close(input);close(output);
end.