InTheBloodHorse

每日一题(29)codeforces 1058C

字数统计: 233阅读时长: 1 min
2018/10/12 Share

题目地址

题意

给n个数字,每个数字只能用一次,并且有序,问你能否拆成 2或更多段,使得每段的位数总和相同。

思路

因为最多100个数字,暴力一下就好了。一开始题目读错了,还以为每次拆出来的数字序列要非递增(瞎了瞎了)。
AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
int a[10001];
int main()
{
int n;
cin >> n;
string s;
cin >> s;
int sum=0;
for(int i=0;i<n;i++){
a[i]=s[i]-'0';
sum+=a[i];
}
for(int i=2;i<=n;i++){
if(sum%i==0){
vector<int>v;
v.clear();
int need=sum/i;
int index=-1;
int cur_sum=0;
for(int j=0;j<n;j++){
cur_sum+=a[j];
if(cur_sum==need){
cur_sum=0;
v.push_back(index);
index=j;
}else if(cur_sum>need){
break;
}
}
if(v.size()==i){
cout << "YES"<< endl;
return 0;
}
}
}
cout << "NO" << endl;
}

原文作者:InTheBloodHorse

原文链接:http://pyking.cn/2018/10/12/每日一题-29-codeforces-1058C/

发表日期:October 12th 2018, 2:55:22 pm

更新日期:October 12th 2018, 2:58:55 pm

版权声明:Have a fun

CATALOG
  1. 1. 题意
  2. 2. 思路