Luogu p1241 括号序列

括号序列题目连接

这是一道与dp毫无半点关系的题

本来是去找的题来着，结果并没有找到，然后看到了这道题。

（本来以为会是很好写的一道题结果因为题意不清直接原地去世了）

思路很简单，基本没有技术含量。

因为数据范围很小，我们可以直接进行暴搜；

定义bool 数组add表示第i个字符所对应的括号有没有被匹配，如果没有匹配需手动补全；

从左往右扫描，如果扫描到‘]‘or‘)‘，从当前位置开始向左扫描，寻找配对括号，如果找到，将左右括号的add都置为1，break；

然后这么找大概就可以ac了叭？

#include<cstdio>
#include<cstring>
#include<algorithm>
#define mk make_pair

using namespace std;

char t[110];
bool add[110];

int main(){
    scanf("%s",t+1);
    int len=strlen(t+1);
    for(int i=1;i<=len;i++){
        if(t[i]==']'){
            for(int j=i-1;j>=1;j--){
                if(add[j]==0&&t[j]=='[') {
                    add[j]=add[i]=1;
                    break;
                }
            }
        }
        if(t[i]==')') {
            for(int j=i-1;j>=1;j--) {
                if(add[j]==0&&t[j]=='(') {
                    add[i]=add[j]=1;
                    break;
                }
            }
        }
    }
    for(int i=1;i<=len;i++) if(!add[i]){
        if(t[i]==')'||t[i]=='(') printf("()");
        if(t[i]=='['||t[i]==']') printf("[]");
    }else printf("%c",t[i]);
    return 0;
}

但是

当我们交上去：

可以说是听取wa声一片了；

为什么呢？！

题面很毒瘤我们看不懂它wr；

现在好像可以意会了但并不能言传因此就假装没看懂叭（自己去悟

像是括号序列([)]，在我方程序判断是合法的，而实际上是不合法的，需要补成()[()]；

所以我们需要加上：

if(t[j]=='['&&add[j]==0) break;//t[i]==')';
if(t[j]=='('&&add[j]==0) break;//t[i]==']';

来判断被不同的括号横插一刀的情况

然后这样就可以ac了！？

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

char t[110];
bool add[110];

int main(){
    scanf("%s",t+1);
    int len=strlen(t+1);
    for(int i=1;i<=len;i++){
        if(t[i]==']'){
            for(int j=i-1;j>=1;j--){
                if(t[j]=='('&&add[j]==0) break;
                if(add[j]==0&&t[j]=='[') {
                    add[j]=add[i]=1;
                    break;
                }
            }
        }
        if(t[i]==')') {
            for(int j=i-1;j>=1;j--) {
                if(add[j]==0&&t[j]=='[') break;
                if(add[j]==0&&t[j]=='(') {
                    add[i]=add[j]=1;
                    break;
                }
            }
        }
    }
    for(int i=1;i<=len;i++) if(!add[i]){
        if(t[i]==')'||t[i]=='(') printf("()");
        if(t[i]=='['||t[i]==']') printf("[]");
    }else printf("%c",t[i]);
    return 0;
}

end-

Luogu p1241 括号序列

原文：https://www.cnblogs.com/zhuier-xquan/p/11482931.html