题目链接
A. Medium Number
题意：
给三个数 a , b , c a,b,c a,b,c，找出中间的那个数
eg. a ≤ b ≤ c a \leq b \leq c a≤b≤c 输出 b b b
Example
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
题解：
#include <iostream>
#include <algorithm>
using namespace std;void sove(void){int a[3];cin>>a[0]>>a[1]>>a[2];sort(a,a+3);cout<<a[1]<<endl;
}int main(void){int _=1;cin>>_;while(_--)sove();return 0;
}
B. Atilla’s Favorite Problem
Example
input
5
1
a
4
down
10
codeforces
3
bcf
5
zzzzz
output
1
23
19
6
26
题意：
找出字符串中在字母序中最大的，并输出其在字母序中的位置
题解：
#include <iostream>
#include <algorithm>
using namespace std;void sove(void){int t;cin>>t;string s;cin>>s;int ans=0;for(int i=0;i<s.size();i++)if(s[i]-'a'>ans)ans=s[i]-'a';cout<<ans+1<<'\n';
}int main(void){int _=1;cin>>_;while(_--)sove();return 0;
}
C. Advantage
Example
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
题意：
依此输出当前数字和在数组中除本身的最大数的差值
题解：
个人认为，先排序更好，然后再排序回来
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2*1e5+10;
struct node{int x,i;int cha;
};
node a[N];
inline bool cmp(node x,node y){return x.x<y.x;
}
inline bool cmp2(node x,node y){return x.i<y.i;
}
void sove(void){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i].x;a[i].i=i;}sort(a+1,a+n+1,cmp);for(int i=1;i<n;i++){a[i].cha=a[i].x-a[n].x;}a[n].cha=a[n].x-a[n-1].x;sort(a+1,a+n+1,cmp2);for(int i=1;i<=n;i++)cout<<a[i].cha<<' ';cout<<'\n';
}int main(void){int _=1;cin>>_;while(_--)sove();return 0;
}
By Hhaarrsshhiitt：
#include<bits/stdc++.h>
using namespace std;
int t;
int main()
{cin>>t;while(t--){int n;cin>>n;int a[n+1],b[n+1];for(int i=0;i<n;i++)cin>>a[i],b[i]=a[i];sort(a,a+n);for(int i=0;i<n;i++)cout<<b[i]-a[n-1-bool(b[i]==a[n-1])]<<" ";cout<<endl;}
}D. Challenging Valleys
Example
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
题意：
给一个数组，定义”山谷“为子数组 [ l , r ] [l,r] [l,r]
并且满足以下四个条件
- 0 ≤ l ≤ r ≤ n − 1 0\leq l \leq r \leq n-1 0≤l≤r≤n−1
2. a l = . . . = a r a_l=...=a_r al=...=ar(具体看上图)
3. l = = 0 ∣ ∣ a [ l − 1 ] > a [ l ] l==0 || a[l-1]>a[l] l==0∣∣a[l−1]>a[l]
4. a [ r + 1 ] > a [ r ] ∣ ∣ r = = n − 1 a[r+1]>a[r]||r==n-1 a[r+1]>a[r]∣∣r==n−1
如果该数组恰好有一个山谷，那么输出"YES"否则输出"NO"
题解：
根据题目来就行，这里使用了双指针的做法
如果有符合山谷条件的就+1，最后判断是否恰好为1个即可
#include <iostream>
#include <algorithm>
//#define int long long
using namespace std;
const int N = 2*1e5+10;int a[N];void sove(void){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];int l=1,r=1;int sum=0;while(r<=n){while(a[l]!=a[r])l++;if((l==1||a[l-1]>a[l])&&(r==n||a[r+1]>a[r]))sum++;r++;}if(sum==1)cout<<"YES\n";else cout<<"NO\n";
}signed main(void){int _=1;cin>>_;while(_--)sove();return 0;
}
//1
//6
//10 10 8 10 10 4
E. Binary Inversions
Example
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
题解：
直接分情况讨论，偶数个最简单，再分两种情况，从前往后和从后往前的。直接贪心，
最佳情况就是前1后0（分前半段和后半段）
最后取最大值即可
时间复杂度都是线性的
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N = 2*1e5+10;bool a[N];
bool b[N];
void sove(void){int n;cin>>n;if(n&1){int flag=1,flag2=1;int ling=0,ling2=0;for(int i=1;i<=n;i++){cin >> a[i];b[i]=a[i];}for(int i=1;i<=n;i++) {if (flag && ((i <= n / 2 && (!a[i])) || (i > n / 2 && a[i]))) {a[i] ^= 1;flag--;}if(!a[i])ling++;int j=n-i+1;if (flag2 && ((j <= n / 2 && (!b[j])) || (j > n / 2 && b[j]))) {b[j] ^= 1;flag2--;}if(!b[j])ling2++;}int ans1=0,ans2=0;for(int i=1;i<=n;i++){if(a[i]){ans1+=ling;}else ling--;if(b[i]){ans2+=ling2;}else ling2--;}cout<<max(ans1,ans2)<<'\n';}else {int flag=1,flag2=1;int ling=0,ling2=0;for(int i=1;i<=n;i++){cin >> a[i];b[i]=a[i];}for(int i=1;i<=n;i++) {if (flag && ((i <= n / 2 && (!a[i])) || (i > n / 2 && a[i]))) {a[i] ^= 1;flag--;}if(!a[i])ling++;int j=n-i+1;if (flag2 && ((j <= n / 2 && (!b[j])) || (j > n / 2 && b[j]))) {b[j] ^= 1;flag2--;}if(!b[j])ling2++;}int ans1=0,ans2=0;for(int i=1;i<=n;i++){if(a[i]){ans1+=ling;}else ling--;if(b[i]){ans2+=ling2;}else ling2--;}cout<<max(ans1,ans2)<<'\n';}}signed main(void){int _=1;cin>>_;while(_--)sove();return 0;
}
//1
//6
//10 10 8 10 10 4
F. Quests
Example
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
official：
#include <bits/stdc++.h>using namespace std;const int MAX = 200007;
const int MOD = 1000000007;void solve() {int n, d;long long c;cin >> n >> c >> d;long long a[n];for (int i = 0; i < n; i++) {cin >> a[i];}sort(a, a + n, greater<long long>());int l = 0, r = d + 2;while (l < r) {int m = l + (r - l + 1) / 2;long long tot = 0;int curr = 0;for (int i = 0; i < d; i++) {if (i % m < n) {tot += a[i % m];}}if (tot >= c) {l = m;}else {r = m - 1;}}if (l == d + 2) {cout << "Infinity\n"; return;}if (l == 0) {cout << "Impossible\n"; return;}cout << l - 1 << '\n';
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}// solve();
}
