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

题目大意：

• 给定一个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;
}

题目大意：

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

解法：

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

#include 
#include 
#include 

using namespace std;

typedef pair 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 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 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;
}

题目大意：

• 给定一个圆心为原点的圆，以及一个在圆内的点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 , r 2 − ( x − d ) 2 ) A = (x - d, sqrt{r^2-(x-d)^2}) A=(x−d,r2−(x−d)2 ​)
   B = ( x + d , r 2 − ( x + d ) 2 ) B= (x + d, sqrt{r^2-(x+d)^2}) B=(x+d,r2−(x+d)2 ​)
   d i s t ( A B ) = 4 d 2 + ( r 2 − ( x − d ) 2 − r 2 − ( x + d ) 2 ) 2 dist(AB) = sqrt{4d^2+( sqrt{r^2-(x-d)^2}- sqrt{r^2-(x+d)^2})^2} dist(AB)=4d2+(r2−(x−d)2 ​−r2−(x+d)2 ​)2 ​
   其中d是固定的，并且根号是单调递增函数，所以式子可以简化成
   r 2 − ( x − d ) 2 − r 2 + ( x + d ) 2 r^2-(x-d)^2-r^2+(x+d)^2 r2−(x−d)2−r2+(x+d)2
   − x 2 + 2 d x − d 2 + x 2 + 2 d x + d 2 = 4 d x -x^2+2dx-d^2+x^2+2dx+d^2=4dx −x2+2dx−d2+x2+2dx+d2=4dx
   所以最后只需4dx很大，AB的距离就可以很大，那么x就取最大的正数
   x = d i s t x=dist 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("%.12lfn", r * (d1 - d2));
    }
}

题目大意：

• 定义一个麻将规则，这个麻将具有34种不同类型的牌，每一种类型的牌具有4张
• 首先会拿到其中的13张牌，相同牌至多出现2张，然后每一轮操作，会在剩下的牌中摸一张，然后选择要或者不要。要的话就还需要打出手中13张牌中的一张，不要的话这张牌废弃，并且不会再被摸到
• 如果在执行操作的时候，摸到一张牌和手中的13张牌组成了7个对子，那么就糊了
• 给定初始手牌，求出采取最优策略的情况下达到七对子的期望轮数

解法：

1. 首先求出最优策略，题意说相同牌至多出现2张，那么也就代表一开始只有单牌或者对子，设单牌为x，对子为y，于是就有
   x = 13 − 2 y ( 0 ≤ y ≤ 6 ) x=13-2y(0le yle 6) x=13−2y(0≤y≤6)

2. 那么单牌的数量一定是奇数，所以最优策略就是摸到一张牌，能凑出对子就要并且丢单牌，不能就不要。

3. 然后期望轮数的公式是：
   E ( X ) = ∑ x P ( x ) ( 1 ≤ x ≤ 121 ) E(X)=sum xP(x) (1le xle 121) E(X)=∑xP(x)(1≤x≤121)
   x的值代表轮数，P(x)为第x轮出七对子的概率
   13张牌肯定无七对子，所以 x ≥ 1 xge 1 x≥1
   发完牌之后还剩 34 × 4 − 13 = 123 34times4-13=123 34×4−13=123张牌，在最坏情况下就是摸完了其他所有牌（120张），到最后才从3张一样的牌中摸到一张组成七对子，所以 x ≤ 121 x le 121 x≤121

4. 那么问题的主要就是求这个概率，第x轮出七对子的概率，换句话也就是说第x轮把所有单牌去掉的概率

5. 因为最优策略采取的方法，每一次选择都只需要关注当前手牌的情况，所以就可以使用DP求解了

6. 设 d p [ i ] [ j ] dp[i][j] dp[i][j]代表第 i 轮把 j 张单牌去掉的概率
   状态转移方程为：
   d p [ i ] [ j ] = d p [ i − 1 ] [ j − 2 ] × 3 × ( k − j + 2 ) 124 − i + d p [ i − 1 ] [ j ] × 124 − i − 3 × ( k − j ) 124 − i dp[i][j]=dp[i-1][j-2]times frac{3times (k-j+2)}{124-i}+dp[i-1][j]times frac{124-i-3times (k-j)}{124-i} dp[i][j]=dp[i−1][j−2]×124−i3×(k−j+2)​+dp[i−1][j]×124−i124−i−3×(k−j)​
   特殊情况：
   当 i = 0 , j = 0 i=0, j=0 i=0,j=0的时候， d p [ i ] [ j ] = 1 dp[i][j]=1 dp[i][j]=1，代表初始局面去掉0张单牌的概率为1
   当 i ≥ 1 , j = 0 ige 1, j=0 i≥1,j=0的时候， d p [ i ] [ j ] = d p [ i − 1 ] [ j ] × 124 − i − 3 × ( k − j ) 124 − i dp[i][j]=dp[i-1][j]times frac{124-i-3times (k-j)}{124-i} dp[i][j]=dp[i−1][j]×124−i124−i−3×(k−j)​
   公式中的 k = k= k= 初始局面单牌的数量

7. 通过dp求出来概率之后，就可以直接利用概率算出期望了(题中是对最后的答案 % 1e9+7，所以还需要求逆元)

#include 
#include