A. The Man who became a God

题意：

给定含有n个元素的数组，将数组分成m段，计算m段 f (l, r) 的最小值

思路：

容易发现 | a_i - a_{i + 1}| 是两个元素差的绝对值，分成m段，也就是有 m - 1个绝对值不用计算，所以只需要除去 m - 1 个最大差值外，把剩余的值相加。

代码：

 1 void solve() {
 2     vector<int> b;
 3     int n, k;
 4     cin>>n>>k;
 5     for (int i = 1; i <= n; i++) {
 6         cin>>a[i];
 7     }
 8     for (int i = 2; i <= n; i++) {
 9         b.push_back(abs(a[i] - a[i - 1]));
10     }
11     sort(b.begin(), b.end(), greater<int>());
12     int ans = 0;
13     for (int i = k - 1; i < b.size(); i++)
14         ans += b[i];
15     cout<<ans<<"\n";
16 }

B. Hamon Odyssey

题意：

给定含有n个元素的数组，可以将其分成若干段，找到满足 f 总和最小时，可以分成的最大段数。

思路：

简单思考可以知道，当只有一段时，其最终的值肯定是最小的，若取该值为x。所以我们从第一个元素开始计算，当值为x时，将这些元素分为第一段。因为 x + 0 = x，所以我们后几段的值都需要为0，所以每出现一个值为0的段，则该段为符合的新段。

代码：

 1 void solve() {
 2     int n;
 3     cin>>n;
 4     for (int i = 1; i <= n; i++) {
 5         cin>>a[i];
 6     }
 7     int res = a[1];
 8     for (int i = 1; i <= n; i++) {
 9         res &= a[i];
10     }
11     int ans = 0;
12     int sum = -1;
13     bool flag = false;
14     for (int i = 1; i <= n; i++) {
15         if (sum == -1)
16             sum = a[i];
17         else {
18             sum &= a[i];
19         }
20         if (!flag) {
21            if (sum == res) {
22                 ans++;
23                 sum = -1;
24                 flag = true;
25             } 
26         } else {
27             if (sum == 0) {
28                 ans++;
29                 sum = -1;
30             }
31         }
32     }
33     cout<<ans<<"\n";
34 }

C. Vampiric Powers, anyone?

题意：

给定含n个元素的数组，可以进行无限次操作。

操作：

选定第i个元素，把从第i个元素到最后一个元素的值进行异或，将得到的值作为一个新元素添加到数组末尾。

思路：

通过样例一，我们容易发现，我们可以在末尾添加和最后一个元素相同的数，计算时就可以将这两个元素抵消。如此，我们可以添加数组中任意后几个元素。所以最后就是求数组中一段连续子序列的最大值。利用前缀和可以把所以结果算出来。

代码：

 1 void solve() {
 2     int n;
 3     cin>>n;
 4     for (int i = 1; i <= n; i++) {
 5         cin>>a[i];
 6     }
 7     int ans = 0;
 8     int res = 0;
 9     set<int> st;
10     for (int i = 1; i <= n; i++) {
11         res ^= a[i];
12         ans = max(ans, res);
13         for (auto it : st) {
14             ans = max(ans, res ^ it);
15         }
16         st.insert(res);
17     }
18     cout<<ans<<"\n";
19     return ;
20 }

D. Professor Higashikata

题意：

给定个长度为n的二进制字符串，可以进行若干次操作，每次操作交换任意两个字符，给定m个 l, r ,将s[l]到s[r]添加到一个空的字符串的末尾，形成一个新的字符串。进行q次翻转，每次只翻转给定的一个字符（1变为0，0变为1），求每次翻转后，将新字符串转换为最大字典序所需最小操作次数。

这道题我完全看的Heltion佬的代码，琢磨的一个多小时，然后按照思路写了一遍。直接看代码吧。

代码：

 1 void solve() {
 2     map<int, int> mp;//坐标的出现顺序
 3     vector<int> p;//记录坐标
 4     int n, m, q;
 5     cin>>n>>m>>q;
 6     string s;
 7     cin>>s;
 8     s = ' ' + s;
 9     set<int> st;
10     for (int i = 1; i <= n; i++) {
11         st.insert(i);
12     }
13     for (int i = 1; i <= m; i++) {
14         int l, r;
15         cin>>l>>r;
16         //找到每个坐标第一次出现的顺序
17         for (auto it = st.lower_bound(l); it != st.end() && *it <= r; it = st.erase(it)) {
18             mp[*it] = p.size();
19             p.push_back(*it);
20         }
21     }
22     int one = count(s.begin() + 1, s.end(), '1');//1的数量，也就是说最后的目的是把这个些1与先出现的坐标交换
23     int ans = 0;//要交换的次数
24     for (int i = 0; i < p.size() && i < one; i++) {
25         if (s[p[i]] == '0')
26             ans++;//因为最终的目的是把p中前one个数全换成1，所以前one个数中，每出现一个0，就要把这个0和1进行一次交换
27     }
28     while (q--) {
29         int x;
30         cin>>x;
31         //如果这个坐标过，并且是在前one个中。说明会影响该坐标下字符的交换
32         if (mp.count(x) && mp[x] < one) {
33             if (s[x] == '1') {
34                 ans++;//若原本是1，则操作后变为了0。需要交换一次
35             } else {
36                 ans--;//操作后变为1。取消对该坐标的交换
37             }
38         }
39         s[x] ^= 1;
40         if (s[x] == '0') {
41             if (one <= p.size()) {
42                 if (s[p[one - 1]] == '0') {
43                     ans--;//第one个坐标不再需要交换
44                 }
45             }
46             one--;//1的个数减少
47         } else {
48             if (one <= p.size()) {
49                if (s[p[one]] == '0') {
50                     ans++;//第one + 1的坐标需要交换
51                 } 
52             }
53             one++;//1的个数增加
54         }
55         cout<<ans<<"\n";
56     }
57 }