题意：

　　这一题给你一个数组，你可以调换某一个数的位置，使得这个数组可以分成2半，前半段的和等于后半段（严格的前半段和后半段）。问你能不能构成。

题解：

　　一开始读题的时候，被吓坏了，没有看到是移动一个，因为题目在output那里才有写是移动一个。

　　那么如果这个和是奇数的话，就无法分成2个相等的部分。则是NO。

　　如果这个数列里有一个数是sum/2的话也是YES。

　　如果是移动一个数，那么这个数一定在某一个大于sum/2的前缀和里或者是在某一个大于sum/2的后缀和里面。因为大于sum/2的时候一定要移动一个数，才能是前缀和为sum/2。

　　同理从后面来看也是这样。

　　我们就可以用一个set来保存前面出现过的a_i

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <string>
 7 #include <vector>
 8 #include <map>
 9 #include <set>
10 #include <stack>
11 #include <queue>
12 #include <sstream>
13 #include <algorithm>
14 using namespace std;
15 #define pb push_back
16 #define mp make_pair
17 #define ms(a, b)  memset((a), (b), sizeof(a))
18 #define eps 0.0000001
19 typedef long long LL;
20 typedef unsigned long long ULL;
21 const int inf = 0x3f3f3f3f;
22 const LL INF = 0x7fffffff;
23 const int maxn = 1e5+10;
24 const int mod = 1e9+7;
25 LL a[maxn];
26 void init()
27 {
28 
29 }
30 void solve()
31 {
32     ios::sync_with_stdio(0);
33 
34     int n;
35     LL sum = 0;
36     cin >> n;
37     for(int i = 1;i<=n;i++)     cin >> a[i], sum+=a[i];
38     if(sum%2==1){
39         cout << "NO" << endl;
40         return;
41     }
42     sum /= 2;
43     for(int i = 1;i<=n;i++){
44         if(a[i] == sum) {
45             cout << "YES" << endl;
46             return;
47         }
48     }
49     LL x = 0;
50     set<LL> S;
51     for(int i = 1;i<=n;i++){
52         x += a[i];
53         S.insert(a[i]);
54         if(S.count(x - sum)){
55             cout << "YES" << endl;
56             return;
57         }
58     }
59     S.clear();
60     for(int i= n;i>0;i--){
61         x -= a[i];
62         S.insert(a[i]);
63         if(S.count(sum-x)){
64             cout << "YES" << endl;
65             return;
66         }
67     }
68     cout << "NO" << endl;
69 }
70 int main() {
71 #ifdef LOCAL
72     freopen("input.txt", "r", stdin);
73 //      freopen("output.txt", "w", stdout);
74 #endif // LOCAL
75     solve();
76     return 0;
77 }

View Code

你努力的时候，比你厉害的人也在努力。