如题,本地运行测试数据输出正确,但评测的时候显示WA
逻辑是将字符依次入栈,可以消除就出栈,计算每个元素入栈时栈中字符的和,如果相同表示中间的子串可以消除
测试点1输入
10
aaaaaaaaaa
输出25
#include <iostream>
#include <stack>
using namespace std;
typedef long long ll;
const int MAXN=2000000;
int n;
char str[MAXN];
int a[MAXN];
int sum[MAXN];
int ans[MAXN][2];
int main(){
cin >> n;
for (int i=0; i<n; i++) cin >> str[i];
for (int i=0; i<n; i++) a[i]=int(str[i]);
stack<int> stk;
sum[0]=int(str[0]);
stk.push(str[0]);
for (int i=1; i<n; i++){
if (stk.empty()||str[i]!=stk.top()){
stk.push(str[i]);
sum[i]=sum[i-1]+int(stk.top());
continue;
}
if (str[i]==stk.top()){
sum[i]=sum[i-1]-int(stk.top());
stk.pop();
continue;
}
}
for (int i=n; i>0; i--) sum[i]=sum[i-1];
sum[0]=0;
int temp;
for (int i=0; i<=n; i++){
for (int j=i+1; j<=n; j++){
if (sum[i]==sum[j]){
ans[temp][0]=i;
ans[temp][1]=j;
temp++;
}
}
}
cout << temp;
return 0;
}