CodeForces Edu171

8个月前更新

Perpendicular Segments

CodeForces Link

Difficulty:900

#include<bits/stdc++.h>
using namespace std;
int t,x,y,k;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    cin>>t;
    while(t--){
        cin>>x>>y>>k;
        int pos=min(x,y);
        cout<<"0 "<<pos<<" "<<pos<<" 0\n";
        cout<<"0 0 "<<pos<<" "<<pos<<'\n';
    }
    return 0;
}

构造是简单的，最主要的是证明 \(k\) 的最大值一定是 \(\sqrt 2 \min(x,y)\)。其实是简单的，假设存在一个比 \(k\) 更大的使得存在一个长度相同的线段与之垂直，那么这个线段所对的直角三角形的一个边一定会超出 \(\sqrt 2 \min(x,y)\)。随便画图即可。

Black Cells

CodeForces Link
Difficulty:1300

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
const long long inf=2e18;
int t,n;
long long a[N],b[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;++i){cin>>a[i];}
		if(n%2==0){
			long long ans=0;
			for(int i=1;i<=n;i+=2){
				ans=max(ans,a[i+1]-a[i]);
			}
			cout<<ans<<'\n';
		}
		else if(n==1){
			cout<<1<<'\n';
		}
		else{
			long long ans=inf;
			for(int i=1;i<=n;++i){
				long long maxn=0;
				for(int j=1;j<i;j+=2){
					maxn=max(maxn,a[j+1]-a[j]);
				}
				for(int j=i+1;j<=n;j+=2){
					maxn=max(maxn,a[j+1]-a[j]);
				}
				ans=min(ans,maxn);
			}
			cout<<ans<<'\n';
		}
	}
	return 0;
}

要点：