2022牛客暑期多校第一场G、A、D

G、 Lexicographical Maximum

题目大意：

• 给定一个n(1 ≤ n ≤ 10 ^ 1e6)
• 输入1 ~ n按字典序排列的最大的数

解法：

• 首先把n当作字符串对待
• 如果len(n) == 1，那么答案就是n
• 如果len(n) >= 2，如果答案不是n的话，那么答案一定是len(n) - 1个9。如果答案是n的话，那么n一定前len(n) - 1个是9。那么就只需要判断n的前len(n) - 1个是不是9。

#include 
#include 

using namespace std;

int main()
{
    string s;
    cin >> s;
    if(s.size() == 1) cout << s << endl;
    else 
    {
        int flag = 0;
        for(int i = 0;i < s.size() - 1;i ++)
                if(s[i] != '9')
                {
                    flag = 1;
                    break;
                }
        if(!flag) cout << s << endl;
        else 
        {
            for(int i = 1;i < s.size();i ++) cout << "9";
            cout << 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

A、 Villages: Landlines

题目大意：

• 现有一根数轴，在上面有n个点，其中1个为发电站，剩下n - 1个为建筑物
• 任务是通过在数轴上放电力塔，使得所有发电站和建筑物相连通
• 发电站和建筑物之间不能直接连通，必须通过电力塔作为连通介质
• 发电站和建筑物都具有一个半径属性，代表和它距离小于这个半径的电力塔，可以直接相连不需要电线，不然就需要电线。
• 求至少需要多少电线，可以使得所有建筑相连

解法：

1. 把发电站和建筑物抽象成一个个的圆，就形成了如图的形状：
   
   其中红色为发电站，蓝色为建筑物，可以发现，如果建筑物和发电站有交点，那么在交点处设立一个电力塔，就可以使得2者相连，并且无需电线。但是如果无交点的话，就必须在中间设立一个电力塔，把他们相连起来，需要的电线长度就是中间的那段距离。然后建筑物之间，如果有交点就在交点处设立，否则也就是需要电线。建筑物到发电站可以通过很多个电力塔到达。
2. 那么问题再简化，就是有很多个区间，有交点的区间可以进行合并。最后求剩下区间之间的距离之和就是答案。

#include 
#include 
#include 

using namespace std;

typedef pair<int, int> pii;

bool cmp(pii a, pii b)
{
    if(a.first == b.first)
        return a.second < b.second;
    return a.first < b.first;
}

int main()
{
    vector<pii> q;
    int n;
    cin >> n;
    for(int i = 1;i <= n;i ++)
    {
        int x, d;
        cin >> x >> d;
        q.push_back({x - d, x + d});
    }
    sort(q.begin(), q.end(), cmp);
    vector<pii> p;
    int l = q[0].first, r = q[0].second;
    for(int i = 1;i < q.size();i ++)
    {
        if(q[i].first <= r) 
        {
            r = max(r, q[i].second);
        }
        else
        {
            p.push_back({l, r});
            l = q[i].first, r = q[i].second;
        }
         if(i == q.size() - 1)
                p.push_back({l, r});
    }
    int res = 0;
    for(int i = 1;i < p.size();i ++) res += (p[i].first - p[i - 1].second);
    cout << res << 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
40
41
42
43
44
45
46
47
48

D、Mocha and Railgun

题目大意：

• 给定一个圆心为原点的圆，以及一个在圆内的点Q
• 并且指定圆的半径r以及一个整数d
• 可以首先指定一个角度，然后形成一个角度为α，中点为Q，长度为2d的线段，然后把这个线段投影到圆边上形成一个弧。
• 可以任意选择角度，问这个弧最长可以是多少

解法：

1. 对于给定的参数，任选一个角度然后投影的弧如图：

1. 然后旋转坐标系可以变成下图：
   
2. 可以发现，对于任意角度形成的线段，都可以通过Q点以原点为中心进行旋转，然后使得线段与x轴平行，并且投影的弧长不变。
3. 当线段与x轴平行之后，就可以直接用线段在x轴上的投影来确定弧长了
4. 而不同角度，通过旋转然后投影到x轴上的区别就在于Q点在x轴上的投影
   
5. 连接原点和Q点，假设这个距离为dist，可以发现，Q点在旋转过程中投影在x轴上的点坐标范围为(-dist, 0) ~ (dist, 0)，那么问题就变成了在这个范围内选择一个点，然后以这个点为中心形成一个长度为2d的线段，向上投影，然后求出最长的弧长。
6. 假设现在取点坐标为(x, 0)，那么它对应的弧长如图：
   
7. 想要弧长越长，那么就必须A点和B点的距离越远
   $$A=(x-d,\sqrt{r^2-(x-d{)}^2})$$
   $$B=(x+d,\sqrt{r^2-(x+d{)}^2})$$
   $$dist(AB)=\sqrt{4d^2+(\sqrt{r^2-(x-d{)}^2}-\sqrt{r^2-(x+d{)}^2}{)}^2}$$
   其中d是固定的，并且根号是单调递增函数，所以式子可以简化成
   $$r^2-(x-d{)}^2-r^2+(x+d{)}^2$$
   $$-x^2+2dx-d^2+x^2+2dx+d^2=4dx$$
   所以最后只需4dx很大，AB的距离就可以很大，那么x就取最大的正数
   $$x=dist$$
   x确定之后，就变成了下图：
   
   那么现在的问题就变成了求α和β的角度，这里利用反三角函数就可以解出。

#include 
#include 
#include 

using namespace std;

int main()
{
    int t;
    scanf("%d", &t);
    while(t --)
    {
        double r, x, y, d;
        scanf("%lf %lf %lf %lf", &r, &x, &y, &d);
        double dist = sqrt(x * x + y * y);
        double d1 = acos((dist - d) / r);
        double d2 = acos((dist + d) / r);
        printf("%.12lf\n", r * (d1 - d2));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20