求证此代码时间复杂度
查看原帖
求证此代码时间复杂度
529229
lrmlrm_楼主2023/11/1 19:46
#include<bits/stdc++.h>
#include<string>
using namespace std;
int n,ans;
string st;
bool check(string ts){
	if(ts==" ")return false;
	return true;
}
int main(){
	scanf("%d",&n);
int CSP_J_RP=100,CSP_S_RP=100;
CSP_S_RP+=CSP_J_RP,CSP_J_RP=0;
	cin>>st;
	st=' '+st;
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j+=2){
			string stne=st.substr(i,j-i+1);
			stne=' '+stne;
			while(check(stne)){
				int ln=stne.size()-1;
				int p=0;
				if(ln+1<=2)break;
				for(int k=1;k<ln;k++){
					if(stne[k]==stne[k+1]){
						stne.erase(k,2);
						k--,p=1;
						ln-=2;
					}
				}
				if(p==0)break;
			}
			if(stne==" ")
				ans++;
		}
	printf("%d",ans);
	return 0;
}

此代码理论可以被十分轻松的卡成 n4n^4 ,类似 这个。

但是这份代码却拿到了 3535 分,这是为什么?

2023/11/1 19:46
加载中...