A. Medium Number
题意：输入三个不同的数字，输出中位数
思路：没啥说的，比较一下大小即可
代码：
<bits/stdc++.h>
using namespace std;
int main()
{
int _;
cin >> _;
while( _ -- ){
int a[3];
for(int i = 0 ; i < 3; i ++ ) cin >> a[i];
sort(a,a + 3);
cout << a[1] << endl;
}
}
B. Atilla's Favorite Problem
题意：给定一个字符串，输出其中最大字母
思路：水水水，遍历字符串比较一遍即可
代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int _;
cin >> _;
while( _ -- ){
int n;
string s;
cin >> n;
cin >> s;
int ans = -1;
for(int i = 0 ; i < s.size(); i ++ ){
ans = max(ans,s[i] - 'a' + 1);
}
cout << ans << endl;
}
}
C. Advantage
题意：给定一个序列，求出每个数字与该序列中除了自身最大的值的差
思路：对于最大值来说只用减去第二大数，其余的数则减去最大值。开两个数组记录一下即可。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n;
struct node{
int id;
int val;
bool operator<(const node & a){
return val < a.val;
}
}a[N],b[N];
int main()
{
int _;
cin >> _;
while( _ -- ){
cin >> n;
for(int i = 1; i <= n; i ++ ){
cin >> a[i].val;
a[i].id=i;
b[i]={i,a[i].val};
}
sort(b+1,b+n+1);
for(int i = 1; i <= n; i++ ){
int k = n;
while(a[i].id == b[k].id) k--;
cout << a[i].val - b[k].val <<' ';
}
puts("");
}
return 0;
}
D. Challenging Valleys
题意：给定一个序列，判断是否只存在一个序列满足\(a[l...r]\)满足\(0 <= l <= r <= n-1\),\(a_l = a_{l+1} = a_{l+2}=...=a_r\),\(l = 0\)or \(a_{l-1} > a_l\),\(r=n-1\)or\(a_r < a_{r+1}\)
思路：仔细分析题目可以发现，其实只需我们判断该序列只要出现一个极大值点则该序列就不为“valley”
一开始按着满足要求的条件算wa了好几次，我傻了QAQ
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n;
int a[N];
int main()
{
int _;
cin >> _;
while( _ -- ){
cin >> n;
for(int i = 0; i < n; i++ ) cin >> a[i];
bool ok = true;
bool up = false,down = false;
for(int i = 0; i < n - 1; i ++ ){
if(a[i] < a[i+1]) up = true;
if(a[i] > a[i+1]){
down = true;
if(up){
ok = false;
break;
}
}
}
if(ok) puts("YES");
else puts("NO");
}
return 0;
}
E. Binary Inversions
题意：给定一个01序列，你可以进行至多一次翻转操作使0变1或者1变0，请你求出最多有多少对满足\(i <j \ and \ a_i>a_j\)
思路：用f[N][2]表示该数后面0，1的数量，先预处理求个每个数后面的0，1数量，在求出没有进行翻转操作符合要求的对数量。由于只进行一次操作，所以我们直接遍历序列对每个数进行一次翻转操作求出最大值。如果该数为0则答案减去该数之前的 1的数量加上之后0的数量即\(f[1][1] - f[i][1]+f[i][0]\),反之亦然。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n;
LL a[N];
int main()
{
int _;
cin >> _;
while( _ -- ){
cin >> n;
vector<vector<int>>f(n+10,vector<int>(2));
for(int i = 1; i <= n; i ++ ) cin >> a[i];
for(int i = n; i >= 1; i --){
for(int j = 0; j <= 1; j ++ ){
f[i][j] = f[i+1][j] + (j == a[i]);
}
}
LL ans = 0;
for(int i = 1; i <= n; i ++ ){
if(a[i] == 1){
ans += f[i][0];
}
}
LL maxn = ans;
for(int i = 1; i <= n; i ++ ){
LL tmp = ans;
if(a[i] == 1){
tmp -= f[i][0];
tmp += f[1][1] - f[i][1];
}else {
tmp += f[i][0] - 1; //包含自身需要-1
tmp -= f[1][1] - f[i][1];
}
maxn = max(maxn,tmp);
}
cout << maxn << endl;
}
return 0;
}
F. Quests
题意：给定n个任务，第i个任务完成后会获得\(a_i\)个硬币，一旦完成该任务，那么该任务只能k天后在做该任务。先让你求出最大的k使得d天内之后获得c个硬币。
思路：在d天内能获得的最多硬币即k=0且每天做硬币最多的任务，最少的硬币即k=n-1且只做前d天能做的任务。如果最小值大于等于c即取可以取任意k，如果最大值小于c即不存在该k。
再看一般情况，要尽可能的使k更大，可以获得的硬币越小，可以看出获得的硬币存在单调性，所以我们可以对k进行二分答案，便可以容易求解。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL n,c,d;
int a[N],b[N];
bool cmp(int a,int b)
{
return a > b;
}
bool check(int x)
{
int group = (x + 1); //几个一组
int num = d / group;//数量
int res = d - num * group; //多出来的任务数量
LL groupans = 0;
for(int i = 1; i <= group; i ++ ) groupans += b[i];
groupans = groupans * num;
for(int i = 1; i <= res; i ++ ) groupans += b[i];
return groupans >= c;
}
int main()
{
int _;
cin >> _;
while( _ -- ){
memset(b,0,sizeof b);
cin >> n >> c >> d;
LL minsum = 0;
for(int i = 1;i <= n ;i ++ ){
cin >> a[i];
b[i] = a[i];
}
sort(b+1,b+n+1,cmp);
for(int i =1; i <= d; i ++ )
minsum += b[i];
LL fir = b[1];
LL maxsum = fir * d;
if(minsum >= c) cout << "Infinity" << endl;
else if(maxsum < c) cout << "Impossible" << endl;
else
{
int l = 0,r = d - 1;
while(l < r){
int mid = (l + r + 1) >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
}
return 0;
}
G. SlavicG's Favorite Problem
题意：给定一个无环的连通的权值树，给出两个顶点a，b，如果你可以从a到b必须满足该路径上权值XOY之后为0，在路径中你可以传送至任意一点（除了b），请你判断是否能从a到达b。
思路：只能传送一次那必然不能选择b点之后的顶点，所以我们可以先处理求出由b点拓展到其余点异或之后的值。然后我们在由a点向其他点进行拓展，如果该点的异或值已经存在则表示可以由a传送到该点在到达b点。如果由a点到达b点时异或值为0则表示不需要进行传送便可以到达。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n,a,b;
int d[N],f[N];
vector<pair<int,int>> g[N];
map<int,int> mp;
queue<int> q;
int main()
{
int _;
cin >> _;
while( _ -- ){
cin >> n >> a >> b;
for(int i = 1;i <= n; i ++ ) g[i].clear();
for(int i = 1;i < n; i ++ ){
int u,v,w;
cin >> u >> v >> w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
for(int i = 1; i <= n; i ++ ) d[i] = 0,f[i] = 0;
mp.clear();
q.push(b);
while(q.size()){
auto x = q.front();
q.pop();
for(int i = 0 ; i < g[x].size();i ++ ){
auto v = g[x][i].first,w = g[x][i].second;
if(!f[v] && v != b) d[v] = d[x] ^ w, f[v] = 1, mp[d[v]] = 1,q.push(v);
}
}
for(int i = 1; i <= n; i ++ ) d[i] = 0,f[i] = 0;
q.push(a);
bool ok =false;
while(q.size()){
auto x = q.front();
q.pop();
if(x == b && d[x] == 0) ok = true;
if(x == b) continue;
if(mp[d[x]]) ok = true;
if(ok) break;
for(int i = 0 ; i < g[x].size();i ++ ){
auto v = g[x][i].first,w = g[x][i].second;
if(!f[v] && v != a) d[v] = d[x] ^ w, f[v] = 1,q.push(v);
}
}
while(q.size()) q.pop();
if(ok) puts("YES");
else puts("NO");
}
return 0;
}