CSP提高T2dp只有20分……
  • 板块学术版
  • 楼主BlinkSwiftie
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/10/24 15:58
  • 上次更新2023/11/2 11:35:43
查看原帖
CSP提高T2dp只有20分……
529468
BlinkSwiftie楼主2023/10/24 15:58

求大佬帮忙调一下

#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
using namespace std;
const int N=2e6+10;
int n;
LL dp[N];
int fa[N],a[N],cnt[30];
char c;
LL ans;
void write(int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int main()
{
	//freopen("game.in","r",stdin);
	//freopen("game.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;++i) 
	{
		cin>>c;
		a[i]=c-'a';
	}
	for(int i=1;i<=n;++i) fa[i]=i;
	fa[0]=1;
	a[0]=-1;
	for(int i=1;i<=n;++i)
	{
		if(a[i]==a[i-1])
		{
			fa[i]=i-1;
			dp[i]=dp[fa[i]-1]+1;
		}
		else if(dp[i-1])
		{
			int f=i;
			while(dp[f-1]&&a[f-1]!=a[i])
			{
				f--;
				f=fa[f];
			}
			if(a[f-1]==a[i])
			{
				fa[i]=f-1;
				dp[i]=dp[fa[f-1]-1]+1;
			}
			else dp[i]=0;
		}
		else 
			dp[i]=0;
			//cout<<i<<' '<<fa[i]<<endl;
		cout<<dp[i]<<endl;
	}
	for(int i=1;i<=n;++i)
		ans+=dp[i];
	printf("%lld",ans);
	return 0;
}

2023/10/24 15:58
加载中...