Codeforces Global Round 2 A B C D

链接：Codeforces Global Round 2

A:Ilya and a Colorful Walk

从后往前找到第一个不等于a[1]的长度，从前往后找到第一个不等于a[n]的长度；取最大值

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 3e5 + 7;
int a[MAXN] , n;

signed main(){
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d",&a[i]);
    int ans = 0;
    for(int i = 1 ; i <= n ; ++i){
        if(a[i] != a[1]) ans = max(ans , i - 1);
        if(a[i] != a[n]) ans = max(ans , n - i);
    }
    cout << ans;
    return 0;
}

B:Alyona and a Narrow Fridge

二分可装瓶子数量+贪心

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e3+10;
int n,h,a[N],b[N];

int ff(int x){
	long long sum =0;
	for(int i=0;i<x;i++){ b[i]=a[i]; }
	sort(b,b+x);
	int i;
	for(i=x-1;i>1;i-=2){
		sum+=(long long )max(b[i],b[i-1]);
	}
	if(i==1) sum+=(long long)b[1];
	else sum+=(long long )b[0];
	if(sum>h) return 0;
	else return 1;
}
signed main(){
	cin>>n>>h;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int l=0,r=n,mid;
	while(l<=r){
		mid=(l+r)/2;
		if( ff(mid) )  l=mid+1;
		else  r=mid-1;
	}
	cout<<r<<endl;
    return 0;
}

C:Ramesses and Corner Inversion

变换前后同行同列和的奇偶不变。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[510][510],b[510][510],ra,ca,rb,cb;

int main (){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			scanf("%d",&a[i][j]);
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			scanf("%d",&b[i][j]);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			ra+=a[i][j];
			rb+=b[i][j];
		}
		if(ra%2!=rb%2){
			printf("No\n");
			return 0;
		}
	}
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			ca+=a[j][i];
			cb+=b[j][i];
		}
		if(ca%2!=cb%2){
			printf("No\n");
			return 0;
		}
	}
	printf("Yes\n");
	return 0;
}

D:Frets On Fire

前缀和+差分+二分

详情：看大佬

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
int n,m;
const int N=1e5+10;
ll a[N];
ll b[N];;
ll sum[N];//前缀和;

int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    m=unique(a+1,a+1+n)-a-1;//去重
    for(int i=1;i<m;++i)
        b[i]=a[i+1]-a[i];
    sort(b+1,b+m);
    for(int i=1;i<m;++i)
        sum[i]=sum[i-1]+b[i];

    int q;
    scanf("%d",&q);
    while(q--){
        ll l,r;
        scanf("%lld%lld",&l,&r);
        ll xl=1,xr=m-1,mid;
        while(xl<=xr){//二分找最后一个小于或等于r-l+1的位置;
            mid=(xl+xr)>>1;
            if(b[mid]<=r-l+1) xl=mid+1;
            else xr=mid-1;
        }
        printf("%lld\n",sum[xr]+(m-1-xr-1+1)*(r-l+1)+r-l+1);
    }
    return 0;
}