【LGR-204-Div.2】核桃编程 11 月月赛 I

T2题解

题面

给一个只有 <>= 的字符串 S ,一个字符串合法仅当该字符串不同时包含 < 和 > 且不能全是 =

问 S 有多少子串合法

题解

30pts

子串？暴力出奇迹！！！

code

#include<bits/stdc++.h>
using namespace std;
int t,n,ans;
char a[200010];
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;ans=0;
		for(int i=1;i<n;i++) cin>>a[i];
		for(int i=1;i<=n;i++)
		{
            //以 i 为一个端点，向左右枚举
			char op=' ';
			for(int j=i-1;j>=1;j--)
			{
				if(op==' '||a[j]==op||a[j]=='=')
				{
					if(op==' '&&a[j]!='=') op=a[j];
					if(op!=' ')ans++;
				}
				else break;
			}
			op=' ';
			for(int j=i;j<n;j++)
			{
				if(op==' '||a[j]=='='||a[j]==op) 
				{
					if(op==' '&&a[j]!='=') op=a[j];
					if(op!=' ')ans++;
				}
				else break;
			}
		}
		cout<<ans/2<<endl;
	} 
	return 0;
}

50pts

看 Subtask 3(20 pts) c[i]!=‘=’

那么肯定有一段连续的 < 或 > 对于一段连续的用组合数算贡献

结合上文 30pts 就能拿 50pts

code

#include<bits/stdc++.h>
using namespace std;
long long t,n,ans;
char a[200010];
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		bool flag=0;
		for(int i=1;i<n;i++) {
			cin>>a[i];
			if(a[i]=='=') flag=1;
		}
		if(flag)
		{
			ans=0;
			for(int i=1;i<=n;i++)
			{
				char op=' ';
				for(int j=i-1;j>=1;j--)
				{
					if(op==' '||a[j]==op||a[j]=='=')
					{
						if(op==' '&&a[j]!='=') op=a[j];
						if(op!=' ')ans++;
					}
					else break;
				}
				op=' ';
				for(int j=i;j<n;j++)
				{
					if(op==' '||a[j]=='='||a[j]==op) 
					{
						if(op==' '&&a[j]!='=') op=a[j];
						if(op!=' ')ans++;
					}
					else break;
				}
			}
			cout<<ans/2<<endl;
		}
		else
		{
			ans=0;
			for(int i=1;i<n;)
			{
				int temp=a[i],cnt=1;
				i++;
				while(i<n&&a[i]==temp)
				{
					i++;
					cnt++;
				}//算连续个数
				ans+=cnt*1ll*(cnt+1)/2;//算贡献
			}
			cout<<ans<<endl;
		}
	} 
	return 0;
}

100pts

考虑等号

把连续相同的字符去重

看等号位置

可能为 <=> 或 >=< (等号两端不相同) 则两端都可以连着等号一起算

还可能为 <=< 或 >=> (等号两端相同) 则这是一个整体,不能分开算 具体看代码

code

#include<bits/stdc++.h>
using namespace std;
long long t,n,ans,cnt,f[200010];
char a[200010],g[200010];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		memset(f,0,sizeof f);
		memset(g,0,sizeof g);
		cnt=0;ans=0;
		for(int i=1;i<n;i++) {
			cin>>a[i];
		}
		for(int i=1;i<n;)
		{
			int temp=a[i],c=1;
			i++;
			while(i<n&&temp==a[i])
			{
				i++;
				c++;
			}
			f[++cnt]=c;//个数
			g[cnt]=temp;//字符
		}//去重
		for(int i=1;i<=cnt;i++)
		{
			long long c=f[i],p=i-1;//可能下面 i 有变化，用 p 保存i-1
			char G=g[i];
			while(i+2<=cnt&&g[i+1]=='='&&g[i+2]==g[i])
			{
				c+=f[i+2]+f[i+1];
				ans-=f[i+1]*(f[i+1]+1)/2;
                //减去全是等号的
				i+=2;
			}//统计整体
			if(G!='=')
			{
				long long l=0,r=0;
				if(g[p]=='=') c+=f[p],l=f[p];
				if(g[i+1]=='=') c+=f[i+1],r=f[i+1];
                //如果左右有 = 号可以合起来算
				ans+=c*(c+1)/2-l*(l+1)/2-r*(r+1)/2;
                //减去全是等号的
			}
		}
		cout<<ans<<'\n';
	} 
	return 0;
}

有问题可以私聊我