题目链接

A、Three Pairwise Maximums

给定x、y、z三个数，其中x=max(a,b)，y=max(a,c)，z = max(b,c)，求出a、b、c。
思维题，想了半天，根据xyz的关系来判断的，具体看代码。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+10;
int a[N],b[N];
int main(){int t,n;cin >> t;while(t--){ll x,y,z;cin >> x >> y >> z;if(x==y&&x==z){cout << "YES" <<endl;cout << x << " " << y << " " << z <<endl;}else if(x==y){if(z>x)cout << "NO" <<endl;else{cout << "YES" <<endl;cout << x << " " << z << " " << z <<endl;}}else if(x!=y){if(z==max(x,y)){cout << "YES" <<endl;cout << min(x,y) << " " << min(x,y) << " " << z <<endl;}elsecout << "NO" <<endl;}}return 0;
}

B、Restore the Permutation by Merger

给出2*n长度的数组，里面只包含了1到n之间的数，输出数组中1到n相应的顺序。
记录每个数字先出现的顺序，出现重复就跳过。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+10;
int a[N],b[N],pd[N];
int main()
{int t,n;cin >> t;while(t--){cin >> n;memset(pd,0,sizeof pd);int temp=0;for(int i=1; i<=2*n; i++){cin >> a[i];if(pd[a[i]]==0){b[temp++] = a[i];pd[a[i]] = 1;}}for(int i=0;i<temp;i++)cout << b[i] << " ";cout <<endl;}return 0;
}

C、Make It Good

给出一个长度为n的序列，问你删除最少的前缀，使其变为一个good序列。
所谓good序列是指通过删除a序列的头部或尾部添加到c序列，使得c序列单调不减。
其实分析一下什么时good序列，只要把good序列从头或者从尾拿放入c数组中，使其成为上升的序列，怎么能够成为这种good序列呢，只有当good序列中先增后减， ^ 像这个山峰的样子，又因为是删除前缀找到good序列，所以从后向前找一个先增后减的序列就可以了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+10;
int a[N],b[N],pd[N];
int main()
{int t,n;cin >> t;while(t--){cin >> n;for(int i=0;i<n;i++)cin >> a[i];int sum=1;bool flag1=1,flag2=0;for(int i=n-2;i>=0;i--){if(a[i]>a[i+1]){if(flag1)sum++;elsebreak;}else if(a[i]==a[i+1])sum++;else{if(flag1){flag1 = 0;flag2 = 1;}if(flag2)sum++;elsebreak;}}cout << n-sum <<endl;}return 0;
}

D、a-Good String

一个字符串如果长度为1 并且为 a 那么就是 a -good 字符串，
当长度大于1时，需要满足将总区间划分成一半，其中一半全是a，另一半必须为b-good字符串，以此类推。
这道题参考了大佬的博客。
这道题其实是用分治与来解决，从不断的将字符串一分为二，然后递归，，查找应该替换的数量即可。
看题解看了很长时间才明白。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+10;
const int mod = 1e9+7;
char str[N];
int go(char c, int l, int r)
{if (l == r - 1)return str[l] != c ? 1 : 0;int mid = (l+r) >> 1;int c1 = 0, c2 = 0;for (int i = l; i < mid; ++i)if (str[i] != c)++c1;for (int i = mid; i < r; ++i) if (str[i] != c) ++c2;return min(c1 + go(c+1, mid, r), c2 + go(c+1, l, mid));
}
int main()
{int t,n;cin >> t;while(t--){cin >> n >> str;cout << go('a', 0, n) <<endl;}return 0;
}