社区讨论

求助为什么本地NOILinux和洛谷没有RE

学术版参与者 1已保存回复 0

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@lo17y1t1
此快照首次捕获于
2023/10/22 16:40
2 年前
此快照最后确认于
2023/10/22 16:43
2 年前
查看原帖
rt,cspT2bf,代码中字符串的下标明显到负数了。
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N=2e6+10,P=1e9+7;
int rd(){
	static int fu,num;static char c;fu=0,num=0;
	while(!isdigit(c))if((c=getchar())=='-')fu=1;
	while(isdigit(c))num=num*10+c-'0',c=getchar();
	return fu?-num:num;
}
#ifdef LOCAL
#define D if(1)
#define print(x) cout<<__LINE__<<#x<<": "<<x<<endl;
#else
#define D if(0)
#define print(x)
#endif
int n,ans;
string s;
int f[N],lp[N];
int st[N];
signed main(){
	// freopen(R"(game.in)","r",stdin);
	// freopen(R"(game.out)","w",stdout);
	n=rd();cin>>s;s=" "+s;
	// iota(lp,lp+n+1,0);
	memset(lp,-1,sizeof(lp));
	for(int i=1;i<=n;i++){
		// if(s[i]==s[lp[i-1]])lp[i]=lp[i-1]-1;
		// if(s[i]==s[i-1])lp[i]=i-2;
		st[0]=0;
		for(int j=i,R=i-(n<=8000?8000:500);j>=R;j--){
			if(st[st[0]]==s[j])st[0]--;
			else st[++st[0]]=s[j];
			if(st[0]==0){
				lp[i]=j-1;
				break;
			}
		}
	}
	for(int i=1;i<=n;i++)if(lp[i]!=-1){
		int tmp=1+f[lp[i]];
		f[i]=tmp;ans+=tmp;
		// cout<<i<<":"<<lp[i]<<" "<<f[i]<<"\n";
	}
	cout<<ans<<endl;
	fclose(stdin);
	fclose(stdout);
	return 0;
}

回复

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

正在加载回复...