频道栏目
首页 > 考试 > 其他 > 正文
编程开发练习题——match
2017-10-27 09:55:12         来源:cgh_Andy's Blog  
收藏   我要投稿

编程开发练习题——match。

#include
using namespace std;
typedef pair pi;
const int N=100002,mod0=1e9+7,mod1=998244353;
char B[1<<14],*S=B,*T=B;
#define gc (S==T&&(T=(S=B)+fread(B,1,1<<14,stdin),S==T)?-1:*S++)
inline int read(){
    int x=0,f=1; char ch=gc;
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1; ch=gc;}
    while(ch>='0' && ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=gc;}
    return x*f;
}
mapp[26];
char s[N],ans[N];
int b[N][2],st[N],tp,L[N];
pi sum[N];
void solve(int l,int r){
    if(l>r)return; ans[l]='(';
    int pos=p[s[l]-'a'][sum[l-1]];
    while(ans[pos]=='(' || ans[pos]==')') pos=L[pos];
    p[s[l]-'a'][sum[l-1]]=L[pos];
    ans[pos]=')';
    solve(pos+1,r),solve(l+1,pos-1);
}
int main(){
    scanf("%s",s+1); int i,n=strlen(s+1);
    b[0][0]=b[0][1]=1;
    for(i=1;i<=n;++i)
        b[i][0]=1ll*b[i-1][0]*27%mod0,
        b[i][1]=1ll*b[i-1][1]*27%mod1;
    int c0=0,c1=0; sum[0]=make_pair(0,0);
    for(i=1;i<=n;++i){
        if(tp && s[st[tp]]==s[i]){
            c0=(c0-1ll*(s[st[tp]]-'a'+1)*b[tp-1][0]%mod0+mod0)%mod0;
            c1=(c1-1ll*(s[st[tp]]-'a'+1)*b[tp-1][1]%mod1+mod1)%mod1;
            tp--;
        }
        else{
            c0=(c0+1ll*(s[i]-'a'+1)*b[tp][0]%mod0)%mod0;
            c1=(c1+1ll*(s[i]-'a'+1)*b[tp][1]%mod1)%mod1;
            st[++tp]=i;
        }
        sum[i]=make_pair(c0,c1);
    }
    if(tp) return puts("-1"),0;
    for(i=1;i<=n;++i){
        L[i]=p[s[i]-'a'][sum[i]];
        p[s[i]-'a'][sum[i]]=i;
    }
    solve(1,n);
    for(i=1;i<=n;++i)printf("%c",ans[i]); puts("");
    return 0;
}
点击复制链接 与好友分享!回本站首页
上一篇:输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,
下一篇:字符串的数量 V2 dp+矩阵乘法解析
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站