C. Vasya and Golden Ticket
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Recently Vasya found a golden ticket — a sequence which consists of n digits a1a2…an. Vasya considers a ticket to be lucky if it can be divided into two or more non-intersecting segments with equal sums. For example, ticket 350178 is lucky since it can be divided into three segments 350, 17 and 8: 3+5+0=1+7=8. Note that each digit of sequence should belong to exactly one segment.

Help Vasya! Tell him if the golden ticket he found is lucky or not.

Input
The first line contains one integer n (2≤n≤100) — the number of digits in the ticket.

The second line contains n digits a1a2…an (0≤ai≤9) — the golden ticket. Digits are printed without spaces.

Output
If the golden ticket is lucky then print “YES”, otherwise print “NO” (both case insensitive).

Examples
inputCopy
5
73452
outputCopy
YES
inputCopy
4
1248
outputCopy
NO
Note
In the first example the ticket can be divided into 7, 34 and 52: 7=3+4=5+2.

In the second example it is impossible to divide ticket into segments with equal sum.

這個題求插板之后分成的區(qū)間，能否使區(qū)間和相等，我第一時間是想2分，但是后來發(fā)現(xiàn)實(shí)現(xiàn)不了。我跟隊友同時開題，我想到了他們的區(qū)間和一定是區(qū)間總和的因子，然后開始做。最后卡在了55組數(shù)，隊友直接全部暴力枚舉過了?？梢匝芯课业拇a，要是過了給我留個言。
不AC代碼

#include<cstring> #include<iostream> #include<cmath> #include<set> #include<cstdio> #include<algorithm> using namespace std; void fj(int a);int a[120],rq[1000],num;bool flag;char c;int sum1=0,w; int main() {rq[0]=1;int n,i,sum=0;cin>>n;for(i=1;i<=n;i++){scanf(" %c",&c);a[i]=c-'0';sum=sum+a[i];}if(sum==0) {cout<<"YES"<<endl;return 0;}fj(sum);sort(rq,rq+num+1);//for(int k=0;k<=num;k++) cout<<rq[k]<<endl;for(int k=0;k<=num;k++){sum1=0;flag=1;for(i=1;i<=n;i++){sum1+=a[i];if(sum1>rq[k]){flag=0;break;}else if(sum1==rq[k]){sum1=0;}}if(sum1!=0) flag=0;if(flag==1) break;}if(flag==1) cout<<"YES"<<endl;else cout<<"NO"<<endl; return 0; } void fj(int a) {int k=1;for(int i=2;i<a;i++){if(a%i==0) rq[k++]=i;}num=k-1; }

AC代碼

#include<bits/stdc++.h> using namespace std; char a[105]; int n,sum=0; bool judge(){bool flag=0;for(int i=0;i<=sum/2;i++){int s=0;if(flag) break;for(int j=0;j<n;j++){ s+=a[j]-'0';if((a[j]-'0')>i||s>i) break;if(s==i) {flag=1;s=0;}}if(s!=0) flag=0;}return flag; } int main(){cin>>n;scanf("%s",a);for(int i=0;i<n;i++)sum+=(a[i]-'0');if(judge()) cout<<"YES";else cout<<"NO";}

總結(jié)

以上是生活随笔為你收集整理的CodeForces 1058C C. Vasya and Golden Ticket的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。