2022牛客多校第一场

A Villages：Landlines

题意：

在一维坐标上存在着 n 个建筑物，其中一个为发电站，剩余 n-1 个为用电建筑物 ，你可以建造一些电塔来联通发电站与建筑物。发电站与用电建筑物都有自己的接收范围，在该范围中建造电塔使该建筑物联入电力系统（无需电线），电塔之间的连接需要电线，当所有建筑物联入时，需要最短的电线长度。

思路：

将接受范围看作区间，区间出现交集则不需要加电线。将区间排序后，将所有区间连通，注意更新区间右端。

代码：


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int n;
ll x,y,ans,zo,yo;
struct node {
    ll l,r;
}s[N];
bool cmp(node a,node b){
    if(a.l!=b.l) return a.l<b.l;
    else return a.r>b.r;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        s[i].l=x-y;
        s[i].r=x+y;
    }
    sort(s,s+n,cmp);
    
    for(int i=0;i<n;i++){
        if(i==0){
            yo=s[i].r;
        }
        else {
            if(s[i].l>yo) {
                ans+=s[i].l-yo;
                yo=s[i].r;
            }
            else yo=max(yo,s[i].r);
        }
        
    }
    cout<<ans<<endl;
    
}

G Lexicographical Maximum

题意：

求1 ∼ n 中字典序最大的数。

思路： 让构造出的数中9尽可能的多，同时考虑特例一位的话就是本身，全为9也是本身。

代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	int len=s.size();
	if(len==1){
		cout<<s; 
		return 0;
	}
	int f=0;
	string ss="";
	for(int i=0;i<len-1;i++){
		cout<<"9";
		if(s[i]!='9') f=1;
	}
	if(f==0) cout<<s[len-1];
	return 0;
}

D Mocha and Railgun

题意：

题意：给你一个中心为(0,0)半径为r的圆，你有一个长度为2d的线段，你可以让其绕中心(x,y)旋转，让其左侧的圆弧在其的射影的弧长最大，求弧长。

思路：

让线段旋转延申成穿过圆心时，投影的弧长最大。剩下就是推公式了。

多组输出，最后输出要注意换行！

代码：

using namespace std;
typedef long long ll;

inline void solve(){
	double r,x,y,d;
	scanf("%lf%lf%lf%lf",&r,&x,&y,&d);
	double h=sqrt(x*x+y*y);
    printf("%.10lf\n",r*(asin((d+h)/r)-asin((h-d)/r)));
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	scanf("%d",&t);
	while(t--){
		solve();
	}
	return 0;
}