社区讨论

求大佬,死活TLE

P1944最长括号匹配参与者 2已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mi7wimve
此快照首次捕获于
2025/11/21 04:46
4 个月前
此快照最后确认于
2025/11/21 04:46
4 个月前
查看原帖
RT,TLE #2,#9,#10三个点,请大佬帮忙看看是否可以优化
下面献上丑陋的代码:
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
struct node{
    int id;
    char bracket;
};
stack<node> stk;
char bracket;
int i;
int ansbegin=-999999;
int anslen=0;
int ansend=-999999;
int sanslen;
char str[1200001];
bool vis[1200001];
bool matching(node ca,node cb){
    if(ca.bracket==')')return cb.bracket=='(';
    if(ca.bracket==']')return cb.bracket=='[';
    return false;
}
inline int __max(int a,int b){
    return a>b?a:b;
}
int Find_LongestRegular(){
    int ansid=0;
    for(i=0;i<strlen(str);++i)
    {
        if(!vis[i]){
            sanslen=0;
            ansid=i+1;
        }
        else{
            sanslen++;
            if(sanslen>anslen){
                ansbegin=ansid;
                ansend=i;
                anslen=sanslen;
            }
        }
    }
}
int main()
{
    int match=0;
    scanf("%s",&str);
    for(i=0;i<strlen(str);++i)
    {
        bracket=str[i];
        node b;
        b.bracket=bracket;
        b.id=i;
        stk.push(b);
        //stk.ergodic();
        if(bracket==')'||bracket==']'){
            if(stk.size()==1){
                continue;
            }
            stk.pop();
            node top=stk.top();
            stk.push(b);
            if(matching(b,top)){
                match++;
                stk.pop();
                stk.pop();
                vis[b.id]=true;
                vis[top.id]=true;
                
            }
        }
    }
    Find_LongestRegular();
    for(i=ansbegin;i<=ansend;++i)
    {
        printf("%c",str[i]);
    }
    printf("\n");
    return 0;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...