[ 考试 ] 7.12

第二题——match（bzoj4936）

<哈希+栈+分治>

用栈和哈希预处理出$str[l]$所能匹配的最远位置$x=lst[a[l]][s[l-1]]$。

分治，$l$和$x$组成一对左右括号。递归被划分的区间$[x+1,r]$和$[l+1,x-1]$。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e5+5,TT=1e9+7;
 4 int n,top,hash,a[N],p[N],st[N],s[N],nxt[N];
 5 map<int,int>lst[30];
 6 char str[N],ans[N];
 7 
 8 void solve(int l,int r) {
 9     if(l>=r) return ;
10     int x=lst[a[l]][s[l-1]];
11     while(ans[x]) x=nxt[x];
12     lst[a[l]][s[l-1]]=nxt[x];
13     ans[l]='(',ans[x]=')';
14     solve(x+1,r); solve(l+1,x-1); 
15 }
16 
17 int main() {
18 //  freopen("match.in","r",stdin);
19 //  freopen("match.out","w",stdout);
20     scanf("%s",str); n=strlen(str);
21     p[0]=1;
22     for(int i=1;i<=n;i++)
23      a[i]=str[i-1]-'a'+1,p[i]=1ll*p[i-1]*97%TT;     
24     for(int i=1;i<=n;i++) {
25         if(st[top]==a[i]) 
26          hash=(hash-1ll*st[top]*p[--top]%TT)%TT;
27         else {
28             st[++top]=a[i];
29             hash=(hash+1ll*a[i]*p[top-1]%TT)%TT;
30         }
31         s[i]=(hash+TT)%TT; 
32     }
33     if(top) return puts("-1"),0;
34     for(int i=1;i<=n;i++) 
35      nxt[i]=lst[a[i]][s[i]],lst[a[i]][s[i]]=i;      
36     solve(1,n);
37     for(int i=1;i<=n;i++) putchar(ans[i]);
38     return 0;
39 }

第三题——ernd（LOJ#6075）

点这里