CodeForces - 1030C Vasya and Golden Ticket(思维题)
程序员文章站
2022-06-29 08:45:32
...
题意:给你一个字符串。问你能不能划分成几段 使得每段的数字和相等 最少有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;
}
上一篇: JPA的多表复杂查询
下一篇: ESP8266学习历程——GPIO配置