“蔚来杯“2022牛客暑期多校训练营1

Fly

G.Lexicographical Maximum

题意：

给出一个数字n（n可能会很大），求出1-n之间字典序最大的数字。

思路：

要实现字典序最大，那么肯定以9开头。 先考虑特殊情况，只有一位数字时，那么肯定就是n。
否则，设数字n的位数为len,那么先是len-1位的9，再看如果数字n的前n-1位都是9，那么最后再加上n的最后一位，就是字典序最大的，就是n。如果不是，那么就输出n-1位的9。
因为n可能很大，所以以字符串形式输入。

考察：
字典序最大

代码：

#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;
}

A.Villages: Landlines

题意：

给出一个发电站和多个建筑物的一维坐标，需要通过电塔和电线将它们全部连接起来，实现所用电线长度最短。在发电站/建筑物半径范围内可以直接与电塔相连，电塔与电塔之间通过电线相连。

思路：

将每个坐标及半径转化为区间，将相交的区间进行合并(按左端点对区间进行排序，从左到右依次合并，这样得到的大区间之间一定不会相交)，最后要实现相连，就是每个大区间之间的距离相加。如果最后合并得到的只有一个区间，那么所用电线长度为0.

考察：
区间合并

Notice:

因为r范围位-1e9~1e9，所以要边界要比2e9要大，我用的是3e9,并且用了long long。最开始错误是因为在从左到右只考虑了右端点，而不是考虑的区间，因此容易出现当后面的覆盖前面时造成所求距离缩短的情况。因此需要先实现区间的合并，再求大区间之间的距离。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
vector<PII> p,q;
struct node{
	ll x,r;
}a[200005];

inline void solve(){
   ll n;
   scanf("%lld",&n);
   for(ll i=0;i<n;i++){
   	    scanf("%lld%lld",&a[i].x,&a[i].r);
   	    p.push_back({a[i].x-a[i].r,a[i].x+a[i].r});//将坐标和半径转化为区间
   	    
   }
   sort(p.begin(),p.end());//按左端点排序
   
   ll st=-3e9,ed=-3e9;//设置初始边界
   for(auto num:p)                   
    {
        if(ed<num.first)        //单独成段的                    
        {
            if(ed!=-3e9) q.push_back({st,ed}) ;  //如果ed<num.first 且ed!=-3e9,说明区间不能再合并了 
            st=num.first,ed=num.second ;            //更新st和ed
        }
        
        else if(ed<num.second)  //能合并的，更新ed
            ed=num.second ;                         
    }  

    if(st!=-3e9&&ed!=-3e9) q.push_back({st,ed});//把最后一个区间加入
    if(q.size()==1) puts("0");//最后只剩一个区间
    else{//累计大区间之间的距离
    	ll ans=0;
    	ll l=q[0].second;
    	for(ll i=1;i<q.size();i++){
    		ll r=q[i].first;
    		ans+=(r-l);
    		l=q[i].second;
		}
		printf("%lld\n",ans);
	}
	
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	ll t;
	t=1;
	while(t--){
		solve();
	}
	return 0;
}

区间合并模板：

 sort(p.begin(),p.end());//按左端点排序
   
   ll st=-3e9,ed=-3e9;//设置初始边界
   for(auto num:p)                   
    {
        if(ed<num.first)        //单独成段的                    
        {
            if(ed!=-3e9) q.push_back({st,ed}) ;  //如果ed<num.first 且ed!=-3e9,说明区间不能再合并了 
            st=num.first,ed=num.second ;            //更新st和ed
        }
        
        else if(ed<num.second)  //能合并的，更新ed
            ed=num.second ;                         
    }  

    if(st!=-3e9&&ed!=-3e9) q.push_back({st,ed});//把最后一个区间加入

D.Mocha and Railgun

题意：
给出一个圆心为C(0,0)的圆墙，一个点Q(x,y)和d，Q为线段AB的中心，线段的长度为2d。求能够映射的弧的最长长度。线段AB端点严格在圆墙内。

思路：
在弧度制下，若弧所对的圆心角为θ，则有公式l=Rθ。
rsinθ=L+d
θ=arcsin((L+d)/r)

考察：
平面计算几何

代码：

#include <bits/stdc++.h>
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;
}