欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

CodeForces - 1030C Vasya and Golden Ticket(思维题)

程序员文章站 2022-06-29 08:45:32
...

CodeForces - 1030C Vasya and Golden Ticket(思维题)
题意:给你一个字符串。问你能不能划分成几段 使得每段的数字和相等 最少有2段。
思路:算出每位的前缀和 相等的数字和肯定是某位的前缀和 枚举每一位前缀和

#include<iostream>
#include<string.h>
using namespace std;
int main()
{
	int n,a[101],t=0;
	string s;
	cin>>n>>s;
	for(int i=0;i<s.length();i++)
		a[++t]=s[i]-'0';
	int sum[101];
	memset(sum,0,sizeof(sum));
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+a[i];
		
	for(int i=1;i<n;i++)
	{
		int ans=0,cnt=0;
		bool flag=true;
		for(int j=i+1;j<=n;j++)
		{
			ans+=a[j];
			if(ans==sum[i])
			{
				flag=true;
				ans=0;
				cnt++;
			}
			if(ans&&ans>sum[i])flag=false;
			if(ans&&ans<sum[i])flag=false;
			if(cnt==0)flag=false;
		}
		if(flag)
		{
			cout<<"YES"<<endl;
			return 0;
		}
	}
	cout<<"NO"<<endl;
}