“蔚来杯“2022牛客暑期多校训练营1（补题）——ADG

A：Villages: Landlines

链接：https://ac.nowcoder.com/acm/contest/33186/A
来源：牛客网

思

根据样例做题可以直观的了解题意，我只需要在做标范围内建立多个电力塔。那么在给定的范围（黑色线部分）中就可以通过电力塔or建筑物中转的方式来实现联系而不需要浪费电线，通俗点来说就是计算整个区间中的空白段（红色部分），我用区间合并做的：将所有片段通过左断点进行排序，再从头到尾扫描一遍

码

#include 
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;

struct node{
    int x,r;
    int left,right;
}a[N];

bool cmp(node p,node q){
    return p.left < q.left;
}

int main(){
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a[i].x >> a[i].r;
        a[i].left = a[i].x - a[i].r;
        a[i].right = a[i].x + a[i].r;
    }
    sort(a,a+n,cmp);
    int ans = 0;
    int end = a[0].right;
    for(int i=1;i<n;i++){
        //cout << a[i].left << endl;
        //cout << end << endl;
        if(a[i].left > end) {
            ans += a[i].left - end;
            end = a[i].right;
        }
        else{
            if(a[i].right > end) end = a[i].right;
        }
    }
    cout << ans << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

D：Mocha and Railgun

链接：https://ac.nowcoder.com/acm/contest/33186/D
来源：牛客网

思

几何题，数学渣渣的痛。
蓝色线段xx：给定Q点到圆心的距离
黄色线段：d + x
紫色线段：d - x
红色和绿色线段：r
题目所求的是IH之间弧长，求出两红色线段之间的圆心角乘以半径即可，区分cos函数和acos函数的区别。

cos(number)和acos(number)的区别

COS函数中的参数number表示求余弦的角度，用弧度格式表示，cos60°；
ACOS函数的参数number表示角度对应的余弦值，数值必须在-1~1之间，acos(1/2）。

码

# include 
using namespace std;
typedef long long ll;
const double pi = acos(-1);

int t;
ll r,x,y,d;

int main(){
    cin >> t;
    while(t--){
        cin >> r;
        cin >> x >> y >> d;
        double x = sqrt(x * x + y * y);
        double a1 = acos((d - x) / r);
        double a2 = acos((d + x) / r);
        double res = pi - a1 - a2;
        double l = res * r;
        printf("%.12lf\n",l);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

G：Lexicographical Maximum

链接：https://ac.nowcoder.com/acm/contest/33186/G
来源：牛客网

思

注意“9999”或“9”和“999998”这种特殊的全为9的就行，其余的都是字符串长度减一长度的“9”字符串。

码

#include 
using namespace std;

int main(){
    string n,ans;
    cin >> n;
    int f = 0;
    for(int i=0;i