A 题目链接：https://codeforces.com/contest/1760/problem/A
input：
9
5 2 6
14 3 4
20 2 1
1 2 3
11 19 12
10 8 20
6 20 3
4 1 3
19 8 4
output：
5
4
2
2
12
10
6
3
8
题意：
给三个数，输出中间值。
思路：
sort 取第二个即可。
代码如下：
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=2e5+10;int t,n;
int a[10];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;while(t--){cin>>a[1]>>a[2]>>a[3];sort(a+1,a+4);cout<<a[2]<<endl;}return 0;
}
B 题目链接：https://codeforces.com/contest/1760/problem/B
input：
5
1
a
4
down
10
codeforces
3
bcf
5
zzzzz
output：
1
23
19
6
26
题意：
给一个小写字母字符串，输出其中最大的字母的数值（ A ~ Z 对应 1 ~ 26 ）。
思路：
开一个maxn变量，遍历字符串找最大值即可。
代码如下：
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=2e5+10;int t,n;
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;while(t--){cin>>n;string s;cin>>s;int ans=0;for(int i=0;i<n;i++){ans=max(ans,s[i]-96);}cout<<ans<<endl;}return 0;
}
C 题目链接：https://codeforces.com/contest/1760/problem/C
input：
5
4
4 7 3 5
2
1 2
5
1 2 3 4 5
3
4 9 4
4
4 4 4 4
output：
-3 2 -4 -2
-1 1
-4 -3 -2 -1 1
-5 5 -5
0 0 0 0
题意：
给一个长度为 n 的数组 a ，对于每一个数，输出其与最大值的差，对于最大值本身，输出其与第二大值的差。
思路：
遍历一次找最大值，再遍历找与其的差值，最小的差值即为最大值本身要输出的数。最后遍历输出即可。
代码如下：
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=2e5+10;int t,n;
int a[N];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;while(t--){cin>>n;int maxn=0;int k=0;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]>maxn){maxn=a[i];k=i;}}int minn=0x3f3f3f3f;for(int i=1;i<=n;i++){if(i==k)continue;else{minn=min(minn,a[k]-a[i]);}}for(int i=1;i<=n;i++){if(i==k){cout<<minn<<" ";}else{cout<<a[i]-a[k]<<" ";}}cout<<endl;}return 0;
}
D 题目链接：https://codeforces.com/contest/1760/problem/D
input：
6
7
3 2 2 1 2 2 3
11
1 1 1 2 3 3 4 5 6 6 6
7
1 2 3 4 3 2 1
7
9 7 4 6 9 9 10
1
1000000000
8
9 4 4 5 9 4 9 10
output：
YES
YES
NO
YES
YES
NO
题意：
给 n 个数的数组 a ，如果存在图中 “ 凹陷 ” 现象，输出 NO，否则输出 YES 。
思路：
如果记录到相邻两数存在上升现象时，每次记录较大值，此后如果记录到有数小于记录值，输出NO，遍历结束后若合法，输出YES
代码如下：
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=2e5+10;int t,n;
int a[N];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}bool f=0,flag=1;int k=0;for(int i=1;i<n;i++){if(a[i]<a[i+1]){f=1;k=a[i+1];continue;}if(f==1){if(a[i+1]<k){flag=0;break;}}}if(flag)cout<<"YES"<<endl;elsecout<<"NO"<<endl;}return 0;
}
E 题目链接：https://codeforces.com/contest/1760/problem/E
input：
5
4
1 0 1 0
6
0 1 0 0 1 0
2
0 0
8
1 0 1 1 0 0 0 1
3
1 1 1
output：
3
7
1
13
2
题意：
给一个由 n 个 0，1组成的数组 a ，该数组的 inversions 指 下标大小关系与自身大小关系相反的元素对的数量。问最多可以操作一次，使某一位元素自相反。问修改（或不修改）得到的最大值是多少
思路：
贪心，只存在三种情况
1.不修改
2.修改从左往右第一个0
3.修改从右往左第一个1
三种情况比较最大值即可
inversions计算方式也很简单，就是每一个0前面所有1的总和
代码如下：
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=2e5+10;ll t,n;
int a[N];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;while(t--){cin>>n;ll cnt1=0,cnt0=0;bool f=0;ll pos1=n+1,pos0=0;ll ans=0;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]==1){cnt1++;pos1=i;}else{cnt0++;if(f==0){f=1;pos0=i;}ans+=cnt1;}}ans=max(ans,ans+max(cnt0-1-pos0+1,cnt1-1-n+pos1));cout<<ans<<endl;}return 0;
}
F 题目链接：https://codeforces.com/contest/1760/problem/F
input：
6
2 5 4
1 2
2 20 10
100 10
3 100 3
7 2 6
4 20 3
4 5 6 7
4 100000000000 2022
8217734 927368 26389746 627896974
2 20 4
5 1
output：
2
Infinity
Impossible
1
12
0
题意：
有 n 种工作，每种工作做完可以获得 ai 元，每天只能完成一种工作。每做完一种工作， k 天内不能再做，给定 c 和 d ，意为在 d 天内获得 c 元，问能够接受最大的 k 约束是多少，输出 k 的值。如果不能约束，输出 “ Impossible ” 如果任意约束都能完成目标 ，输出 “ Infinity ”
思路：
贪心处理。先按价值从大到小排序，在限制条件下，我们一定是优先选最大的，限制解除后继续选最大的
首先看一下两种特殊情况处理
1. 如果说在不加限制的条件下，也就是每次选择价值最大的工作，完成 d 天，依然无法达成目标，那么可以输出 Impossible
2.如果说限制无限大，也就是说每种工作只能做一次，且总时间不超过 d 天的情况下，依然可以达成目标，那么可以输出 Infinity
3.正常情况下，直接二分答案k即可。对于一个限制 k ，我们的工作模式是 k + 1天的循环，取模每次做价值最大的工作即可（也有可能不工作），然后check判断当前 k 能不能达成目标
注意对价值序列进行前缀和化出力，能降一维复杂度
代码如下：
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=2e5+10;ll t,n,c,d;
ll a[N],s[N];
inline bool cmp(ll a,ll b)
{return a>b;
}inline bool check(ll k)
{k++;ll time=d/k;ll m=d%k;if(time*s[min(k,n)]+s[min(m,n)]<c)return false;elsereturn true;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;while(t--){cin>>n>>c>>d;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){s[i]=s[i-1]+a[i];}if(a[1]*d<c){cout<<"Impossible"<<endl;continue;}if(s[min(d,n)]>=c){cout<<"Infinity"<<endl;continue;}ll l=0,r=d,mid=0;while(l<r){mid=(l+r+1)>>1;if(check(mid)){l=mid;}else{r=mid-1;}}cout<<l<<endl;}return 0;
}
G 题目链接：https://codeforces.com/contest/1760/problem/G
input：
3
5 1 4
1 3 1
2 3 2
4 3 3
3 5 1
2 1 2
1 2 2
6 2 3
1 2 1
2 3 1
3 4 1
4 5 3
5 6 5
output：
YES
NO
YES
题意：
有一个 n 个点的树，每条边都有权值 w ，现在给定起点 a ，终点 b ，一开始 x = 0 ，每次由一个点到另一个点时 ，x与这条边的权值异或 ，问能否在到达 b 的时候 ，x = 0（有一次机会，可以从任意点跳到除点 b 外的任意点，不经过异或）
思路：
从点 a 开始 dfs ，每次进行异或，将当前异或值存入 set。
然后从点 b 开始 dfs ，每次进行异或，如果当前值能在 set 中 找到，那么输出YES
否则输出NO
代码如下：
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=2e5+10;struct node{ll f,w;
};
int t,n=0,a,b;
bool flag;vector<node> vec[N];
set<ll> st;void dfs_a(int from,int to,ll sum)
{if(to==b){return;}st.insert(sum);for(auto &x:vec[to]){if(x.f==from)continue;dfs_a(to,x.f,sum^x.w);}
}void dfs_b(int from,int to,ll sum)
{if(flag){return;}if(st.count(sum)&&to!=b){flag=1;return;}for(auto &x:vec[to]){if(x.f==from)continue;dfs_b(to,x.f,sum^x.w);}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;while(t--){st.clear();for(int i=1;i<=n;i++){vec[i].clear();}cin>>n>>a>>b;int u,v;ll w;for(int i=1;i<n;i++){cin>>u>>v>>w;vec[u].push_back({v,w});vec[v].push_back({u,w});}flag=0;dfs_a(0,a,0);dfs_b(0,b,0);if(flag)cout<<"YES"<<endl;elsecout<<"NO"<<endl; }return 0;
}
