7.18 牛客多校联赛第一场部分题解

即给定x坐标以及其半径，问你从最左边到最右边的区间里， 有几个点没有被覆盖到。比如给定 1，2   和  4，3  那么最左边是1-2=-1 最右边是4+3=7 ，区间总长度为7- -1 = 8， 那么我们覆盖的区域有 1-2到1+2， 以及 4-3到4+3  即 -1到3 和 1到7 合并一下就是-1到7 覆盖长度为8 所以输出位覆盖的长度为0。

就是记录区间，合并区间，计算合并后的区间长度，再用总长度-合并后的区间长度即可。合并区间的方法： 将所有区间按照左端点排序，再遍历所有区间， 分情况区间和上一个区间的重叠情况，具体见代码。

#include
using namespace std;

int n;
pair a[200010];  //用pair存区间左端点和右端点

int main()
{
    cin>>n;
    int x,rr;
    int minl = 999999999, maxr = -999999999; 
    for(int i=0;i>x>>rr;
		a[i] = {x-rr, x+rr};  //转换成区间
        minl = min(minl, x-rr); //求最左和最右
        maxr = max(maxr, x+rr);
    }
    
    sort(a, a+n); //将所有区间按照左端点排序 pair即按照first排序
    
    // 合并区间的过程记录长度
    int l = a[0].first,r = a[0].second;
    int len = r-l; //第一个区间
    
    for(int i=1;ir){
			len += (a[i].second - r);
			r = a[i].second;
		}
		
		else if(a[i].first>=r){
			len += (a[i].second - a[i].first);
			l = a[i].first, r = a[i].second;
		}
	}
	
	cout< 
 
G题 
题目大意 
输入一个数字n，1-n所有数字按照字典序排序，最大的是哪个数? 
 
求解思路 
了解字典序比较方法：从左往右逐个比较字符的ASCII码值（0-9升高），一旦能判定出来字符大小就退出。 对于输出的k位数字，检测前k-1位是否全为9， 若是，那么这个数本身是最大序， 若否，那就是k-1个9组成的数是最大序，当然，如果只有1位，那一定是这个数本身。
 
#include
#include
#include
#include
#include
 
using namespace std;
 
string s;
 
int main(){
    cin>>s;
    if(s.size()==1) cout< 
 
D题 
题目大意 
在以0，0为圆点的半径为R的圆内部，有一条以Q为中间的可以绕着中点Q旋转的线段，问从线段两端垂直射出去的直线能割到的圆弧的最大长度是多少？(只求单侧)、 
 
求解思路 
旋转到何时割出的狐最大，一定是有一个规律的，结论是 线段与圆心O到Q的直线OQ垂直时最大。通过几何关系即可求解圆弧，弧长l=θr=2*r*arcsin(h/2r)   其中 h为弦长 r为半径 θ为圆心角
 
 
 
#include
#include
#include
#include
#include
 
using namespace std;
 
typedef long long ll;
int T;
double r;
double x,y,d;
 
double dist(double x1,double y1,double x2,double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
 
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%lf",&r);
        scanf("%lf%lf%lf",&x,&y,&d);
        double b=sqrt(r*r-(dist(x,y,0,0)+d)*(dist(x,y,0,0)+d));
        double g=sqrt(r*r-(dist(x,y,0,0)-d)*(dist(x,y,0,0)-d))-b;
        double xian=sqrt(g*g+(2*d)*(2*d));
        double thea=2*asin(xian/2/r);
        printf("%.8lfn",thea*r);
    }
    return 0;
}