https://codeforces.com/contest/1760
【赛时A-E代码】
A. Medium Number
题目大意：
三个数字，求第二大的数字。
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<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
LL a[N];
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
LL T=1;
cin>>T;
while(T--)
{
for(int i=1;i<=3;i++)
cin>>a[i];
sort(a+1,a+1+3);
cout<<a[2]<<endl;
}
return 0;
}
B. Atilla's Favorite Problem
题目大意：
求一个字符串中最大字符的ASCII值在字母上排第几个？
input
5
1
a
4
down
10
codeforces
3
bcf
5
zzzzz
output
1
23
19
6
26
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
LL a[N];
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
LL T=1;
cin>>T;
while(T--)
{
LL n;
cin>>n;
string s;
cin>>s;
sort(s.begin(),s.end());
cout<<(int)s[s.size()-1]-96<<endl;
}
return 0;
}
C. Advantage
题目大意：
最大值用最大值减去次大值，其余减去最大值
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<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
LL a[N],b[N];
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
LL T=1;
cin>>T;
while(T--)
{
LL n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i];
}
sort(a+1,a+1+n);
LL max1=a[n],max2=a[n-1];
for(int i=1;i<=n;i++)
{
if(b[i]==max1) cout<<b[i]-max2<<" ";
else cout<<b[i]-max1<<" ";
}
cout<<endl;
}
return 0;
}
D. Challenging Valleys
题目大意：
给定数组如图两种正确情况所示即可
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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
LL a[N],b[N];
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
LL T=1;
cin>>T;
while(T--)
{
LL n;
cin>>n;
for(LL i=1;i<=n;i++)
{
cin>>a[i];
}
bool flag=true;
for(LL i=1;i<=n;i++)
{
if(a[i]>a[i-1]) ;
else
{
flag=false;
break;
}
}
if(flag==true) cout<<"YES"<<endl;
else
{
LL l=1,r=n;
while(a[l+1]<=a[l]&&l<=n) l++;
while(a[r-1]<=a[r]&&r>=1) r--;
//cout<<l<<" "<<r<<endl;
if(l>=r) flag=true;
if(flag==true) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
return 0;
}
E. Binary Inversions
题目大意：
单步操作：0变1 或者 1变0；
满足最大的反转数量：i<j and ai>aj.
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
- 直接猜结论就行（具体思路我赛时没证明哈哈，直接猜了个结论就冲了）
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
LL a[N],zero[N],one[N];
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
LL T=1;
cin>>T;
while(T--)
{
LL n;
cin>>n;
zero[0]=0;
one[0]=0;
LL idx0=n+1,idx1=-1;
LL maxn=0,sum=0;
for(LL i=1;i<=n;i++)
{
cin>>a[i];
zero[i]=zero[i-1];
one[i]=one[i-1];
if(a[i]==0)
{
zero[i]=zero[i-1]+1;
sum+=one[i];
idx0=min(idx0,i);
}
else if(a[i]==1)
{
one[i]=one[i-1]+1;
idx1=max(idx1,i);
}
}
//cout<<"sum "<<sum<<endl;
//cout<<" 0 1::"<<idx0<<" "<<idx1<<endl;
maxn=max(maxn,sum);
//最后一个1改成0
sum=0;
a[idx1]=0;
for(LL i=1;i<=n;i++)
{
zero[i]=zero[i-1];
one[i]=one[i-1];
if(a[i]==0)
{
zero[i]=zero[i-1]+1;
sum+=one[i];
}
else if(a[i]==1)
{
one[i]=one[i-1]+1;
}
}
maxn=max(maxn,sum);
//cout<<"sum "<<sum<<endl;
//第一个0改成1
sum=0;
a[idx1]=1;
a[idx0]=1;
for(LL i=1;i<=n;i++)
{
zero[i]=zero[i-1];
one[i]=one[i-1];
if(a[i]==0)
{
zero[i]=zero[i-1]+1;
sum+=one[i];
}
else if(a[i]==1)
{
one[i]=one[i-1]+1;
}
}
maxn=max(maxn,sum);
cout<<maxn<<endl;
//cout<<endl;
}
return 0;
}
补题：
https://codeforces.com/contest/1760/problem/F
F. Quests（二分）
题目大意：
给定一个长度为n的序列a表示有n个任务，我们每次完成了一个任务就可以获得ai个金币
问我们最多间隔k天能够在期限为d天的时间内总共获得>=c个金兵？
求最大k，k无限大输出Infinity，k不存在输出Impossible,否则输出最大k值
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
- 因为k如果是0那么我们一直选最大的任务就好，k是1我们可以先选最大的任务再选次大的任务，我们可以发现k越小越好（直接填充大数，在特判Impossible情况后处于绝对满足的状态），所以具有单调性；
- 当前二分出来的k，在这个k下，我们看看一共有多少整数回合，这些回合肯定是用1--k这段，
- 然后最后会有一个不完整的回合，这个回合加的值是剩下还有多少次操作（假设是x，那么这回合加的值会是前x个最大的）
- 【k表示前缀和序列中取前k个作为是一个周期，也就是check部分的x】
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=5000200,M=2002;
LL a[N],b[N];
LL n,c,d;
bool check(LL x)//x为一个周期
{
LL res1=b[min(x+1,n)]*(d/(x+1));
LL res2=b[min(n,d%(x+1))];
cout<<x<<" "<<res1<<" "<<res2<<endl;
if((res1+res2)>=c) return true;
else return false;
}
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
LL T=1;
cin>>T;
while(T--)
{
cin>>n>>c>>d;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
reverse(a+1,a+1+n);//从大到小
LL maxn=a[1];
for(int i=1;i<=n;i++)//前缀和
{
if(i==1) b[i]=a[i];
else b[i]=b[i-1]+a[i];
}
//先特判掉全部最大的都填不满的情况
if(maxn*d<c) cout<<"Impossible"<<endl;
else
{
LL l=-1,r=d+1;
while(l<r)
{
LL mid=(l+r+1)>>1;
if(check(mid)) l=mid;//满足条件，往后压缩区间
else r=mid-1;//不满足条件
}
if(l>=d+1) cout<<"Infinity"<<endl;
else cout<<l<<endl;
}
}
return 0;
}