CodeCraft-22 and Codeforces Round #795 (Div. 2)
A. Beat The Odds
题意：
给定一个序列a1,a2，…，an，找出要从该序列中移除的最小元素个数，使移除后每两个连续元素的和为偶数。
思路：
只有 偶数+偶数 或者 奇数+奇数 的值才能得到偶数。所以最终序列中剩下的只有偶数或者奇数。 统计偶数和奇数的个数，哪个较小就删除哪个。
代码：
#include <bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5+10;int n;void solve(){cin >> n;int odd = 0, even = 0;for(int i = 1; i <= n; i ++){int tmp;cin >> tmp;if(tmp % 2) odd ++;else even ++;}cout << min(odd, even) << endl;}signed main(){int T;scanf("%d", &T);while(T--) solve();}
B. Shoe Shuffling
题意：
输入n个学生和每个学生对应的鞋码大小。他们交换鞋子的原则是得到的鞋子的大小必须>=自己的鞋码。问能否得到一个交换方案最终每个人穿的都是别人的鞋子，输出这个方案，没有就-1.
思路：
每个鞋码的数量必须是>=2的，否则没法换。举个小例子，三个人的鞋码 38 41 41，无论如何换总有一个41码的学生得到38，不可行。三个人的鞋码 38 38 41，同理总会有个41码的同学得到38，不可行。
又因为题目给出的鞋码是不降序的，即同码的都是相邻的，只需要交换相同鞋码的就行。我们只需要将相邻鞋码的同学编号右移一位就可。
代码：
#include <bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5+10;int n;int a[N];void solve(){int ok = 1;scanf("%d", &n);map<int, int> mp;for(int i = 1; i <= n; i ++){scanf("%d", &a[i]);mp[a[i]] ++;}for(auto it : mp){if(it.second <= 1){ok = 0; break;}}if(!ok) {printf("-1\n");return;}int l = 1, r = 1, tmp = a[1];for(int i = 2; i <= n; i ++){if(a[i] == tmp) r = i;// 将连续相同的地方下标错开一位if(a[i] != tmp || n == i){printf("%d ", r);for(int p = l; p < r; p ++)printf("%d ", p);l = i, r = i;tmp = a[i];}}printf("\n");}signed main(){int T;scanf("%d", &T);while(T--) solve();}
C. Sum of Substrings
题意：
给一个二进制的字符串，f(x)函数表示将这个字符串每相邻的两位看做十进制（允许前导零）相加的值。每次操作可以交换相邻两位，问最多k次可以得到f(x)的最小值是多少。
思路：
每个字符对答案的贡献到底是什么？
会发现除了第一个字符和最后一个字符贡献分别只有上述一个分支，中间的字符的贡献都是有两个分支的，也就是说最优方案就是先把末尾变成1，再把首位变成1，中间无论如何变化都是两份贡献。
所以得到以下式子（这里字符串下标从1开始）
f(x) = s[1] * 10 + s[2] * 11 + s[3] * 11 +…+ s[n-1] * 11 + s[n] * 1
构建代码时只需要记录第一个1和最后一个1，让其在k次操作内先把末尾改成1，再把开头开成1即可。
代码：
#include <bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10;void solve(){int n, k;int ans = 0;// 记录第一个1的位置和最后一个1的位置int first = 0, last = 0, cnt = 0, temp = 0;scanf("%d %d", &n, &k);string s;cin >> s;s = '@' + s;for (int i = 1; i <= n; i++){if (first == 0 && s[i] == '1') first = i;if (s[i] == '1'){last = i;cnt ++;}}if(cnt && n - last <= k){k -= (n - last);temp += 1;cnt --;}if(cnt && first - 1 <= k){temp += 10;cnt --;}cout << cnt * 11 + temp << endl;}signed main(){int T;scanf("%d", &T);while (T--) solve();}
D. Max GEQ Sum
题意：
验证所给数列是否满足所有的子区间都满足下式：
max(ai,ai+1,…,aj−1,aj)≥ai+ai+1+⋯+aj−1+aj （1 ≤ i ≤ j ≤ n.）
思路：
如果a[i]是某段区间的最大值，只需要往前和往后找到大于a[i]的数，这两个比a[i]大的数中间的一段就是以a[i]为最大值的区间。再运用前缀和求出这一段的和，就可以判断是否满足题目的不等式。
如下图，
五角星是比a[i]大的数，设△x是前半段的前缀和，△y是后半段的前缀和，那么通过化简可以得到△x+△y<=0，即△x<=0，△y<=0. 所以可以前后分开计算， 只要出现大于0就直接NO了。
我们就去判断会不会以出现>0的情况，如果暴力枚举会成为O(n^2)。所以计算时加优化：
这里定义pre[]为前缀和数组。那么△x = pre[i] - pre[k] (k属于★~i之间)，因为△x>0时为NO，判断是不是△x>0，只需要pre[i] - max(pre[k], pre[k+1]…) > 0就行。
代码：
#include <bits/stdc++.h>#define int long long#define pii pair<int, int>using namespace std;const int inf = (1LL << 55);bool check(vector<int> a){int n = a.size();vector<int> p = a;for (int i = 1; i < n; i++)p[i] += p[i - 1];vector<pii> bf;bool flg = 1;for (int i = n - 1; i > -1; --i){int mx = -inf;while (bf.size() && bf.back().first <= a[i]){mx = max(mx, bf.back().second);bf.pop_back();}flg &= (mx - p[i] <= 0);mx = max(mx, p[i]);bf.push_back({a[i], mx});}return flg;}signed main(){int t;cin >> t;while (t--){int n; cin >> n;vector<int> a(n);for (int &x : a) cin >> x;vector<int> ra = a;reverse(ra.begin(), ra.end());if (check(a) && check(ra)) cout << "Yes";else cout << "No";puts("");}return 0;}
