题目：
A.Beat The Odds
B.Shoe Shuffling
C.Sum of Substrings
A.Beat The Odds.
题目大意：
给定一个数组，找到最小的删除数，使得删除之后的新数组，每两个相邻位置的数字和为偶数。
思路：
如果想让每两个相邻位置上的数字和为偶数，那么，只有两种可能，要么同为偶数，要么同为奇数，答案就可以转化为，求原数组中偶数和奇数的个数，找到最小的那个数就是最小删除个数。
代码如下：
/*author : Mzx*/#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef long double ld;typedef pair<int,int> PII;const ll mod=1e9+7;const int inf=0x3f3f3f3f;const int maxn=1e5+10;#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define x first#define y secondint read () {int k=0,f=1;char c=getchar ();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar ();}while (c>='0'&&c<='9') {k=k*10+c-'0';c=getchar ();}return k*f;}int a[maxn];void solve() {int n;cin>>n;int num1 = 0,num2 = 0;for(int i = 1;i <= n;i ++) {cin >> a[i];if(a[i] % 2 == 0) num1++;else if(a[i] % 2 == 1) num2++;}//cout<<num1<<" "<<num2<<endl;cout<<min(num1,num2)<<endl;}int main(){ios;int t;cin >> t;while(t--){solve();}return 0;}
B.Shoe Shuffling
题目大意：
一个班级里有n个学生，给你一个长度为n的非递减的s数组，s(i)表示第i个学生的鞋子的尺码，现在进行洗鞋，若此次洗鞋是合法的那么要求是每个学生穿的鞋子都不是自己的并且每个学生拿到的鞋子的尺码大于等于他自己原来的尺码。输出一个序列p（p是由1-n组成的序列，并且无重复数字）表示第i个学生穿的是第pi个学生的鞋子，如果不存在合法的洗鞋，那么输出-1；
思路：
考虑到s数组是非递减的，那么在s数组中出现的每个鞋码的个数必须大于1，若有一个鞋码出现的次数是1的话，就不存在合法的洗鞋序列。（证明：假设第一个鞋码和第二个鞋码不同，由于该数列是非递减数列，那么第一个人洗鞋后的鞋子只能是自己的，故不合法，其他位置同理，这里不再赘述）所以，在s序列中只需要找到相同的鞋子的初始位置和末尾位置，并将其顺序打乱，这里有一个小技巧，由于题目要求若有多组答案，输出一组即可，所以在相同的鞋码序列中将最后一个放在初始位置，其他的按顺序排列即可符合题意。（不懂的同学可看样例一）。
代码如下:
/*author : Mzx*/#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef long double ld;typedef pair<int,int> PII;const ll mod=1e9+7;const int inf=0x3f3f3f3f;const int maxn=1e5+10;#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define x first#define y secondint read () {int k=0,f=1;char c=getchar ();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar ();}while (c>='0'&&c<='9') {k=k*10+c-'0';c=getchar ();}return k*f;}int a[maxn];map<int,int> vis;void solve() {int n;cin>>n;vector<PII> ans;vis.clear();bool ok = true;for(int i = 1;i <= n;i ++){cin>>a[i];vis[a[i]]++;}int st = 1,en = 1;for(int i = 2;i <= n;i ++){if(a[i] == a[i - 1]) en = i;else{ans.push_back({st,en});st = en = i;}if(i == n) ans.push_back({st,en});// cout<<st<<" "<<en<<endl;}//for(auto x:ans) cout<<x.first<<" "<<x.second<<endl;for(auto x : vis){if(x.second == 1){ok = false;break;}}if(ok) {for (auto x: ans) {cout << x.second << " ";for (int i = x.first; i < x.second; i++) cout << i << " ";}cout << endl;}else{cout<<"-1"<<endl;}}int main(){ios;int t;cin >> t;while(t--){solve();}return 0;}
C.Sum of Substrings
题目大意：
给一个长度为n的二进制字符串s，定义di为sisi+1的一个长度为2的字符串，定义f(s)为所有合法的di的和。f(s) =;
在一次操作中，你可以交换字符串中任意两个相邻位置的数字，最后找到最小的f(s)，操作数不超过k;
思路：
通过打表可以看出第一个位置上和最后一个位置上的1是最优的位置，可以推出该式子:
f(s) = s[0]*10 + s[1] * 11 + s[2] * 11 + ..... + s[n-2] * 11 + s[n - 1] * 1;
所以很容易可以想到通过交换位置把1放在最后的位置或者最前面的位置，剩余在中间的1移动之后对最后的答案无贡献，考虑到操作次数有限，所以把最后的1通过交换放在最后面，把最前面的1通过交换放在最前面。
代码如下：
/*author : Mzx*/#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef long double ld;typedef pair<int,int> PII;const ll mod=1e9+7;const int inf=0x3f3f3f3f;const int maxn=1e5+10;#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define x first#define y secondint read () {int k=0,f=1;char c=getchar ();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar ();}while (c>='0'&&c<='9') {k=k*10+c-'0';c=getchar ();}return k*f;}void solve() {int n,k;cin>>n>>k;string s;cin>>s;int last_one = -1;for(int i = 0;i < n;i ++){if(s[i]=='1')last_one = i;}if(last_one == -1){cout<<0<<endl;return;}if(n - 1 - last_one <= k && s[n-1] == '0'){k -= (n - 1 - last_one);swap(s[n-1],s[last_one]);}int first_one = -1;for(int i = 0;i < n;i ++){if(s[i] == '1'){first_one = i;break;}}if(first_one <= k && s[0]=='0' && first_one != n-1){swap(s[0],s[first_one]);}ll ans=0;for(int i = 1;i <= n - 2;i ++){ans += (s[i] - '0')* 11;}ans = ans + (s[0]-'0') * 10 + (s[n-1]-'0') * 1;cout<<ans<<endl;}int main(){ios;int t;cin >> t;while(t--){solve();}return 0;}
