求助昨晚abc D复杂度问题
  • 板块学术版
  • 楼主wan_yy
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/6/25 10:07
  • 上次更新2023/11/3 12:28:10
查看原帖
求助昨晚abc D复杂度问题
577834
wan_yy楼主2023/6/25 10:07

rt,这份代码会T两个点,下面的是标程。

想问一下是什么导致这两份代码的用时差别很大呢

#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#define ll long long
#define ull unsigned long long
using namespace std;
//================================
int N;
char c[200005];
vector< pair<char,int> >v;
signed main(){
#ifdef LOCAL
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
//================================
    cin>>N;
    cin>>(c+1);
    for(int i=1;i<=N;i++){
        if(c[i]=='(')v.push_back(make_pair('(',i));
        else if(c[i]==')'){
            if(v.empty())continue;
            auto x=v.back();
            v.pop_back();
            int l=x.second;
            for(int j=l;j<=i;j++)c[j]='&';
        }
    }
    for(int i=1;i<=N;i++){
        if(c[i]=='&')continue;
        else cout<<c[i];
    }
//================================
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
 
int main(){
	int n;
	cin >> n;
	string s;
	cin >> s;
	string ans;
	int depth=0;
	for(auto c:s){
		if(c==')'&&depth>0){
			while(ans.back()!='(')ans.pop_back();
			ans.pop_back();
			depth--;
		}else{
			ans+=c;
			if(c=='(')depth++;
		}
	}
	cout << ans << endl;
}
2023/6/25 10:07
加载中...