2023寒假算法集训营1

题意：

给定一个长度为 10 的01串，表示 A、B 双方的点球情况，1 表示罚进，0 表示罚不进。

A 先手，交替罚点球，各罚五次。

得分多者获胜。若在罚完某个球后，后续的罚球无论如何都不会影响最终的结果，则比赛结束。

判断会在踢完第几个球时结束，若踢满 10 球仍未分出胜负则输出 -1.

思路：

依次枚举，每次记录下当前的得分，然后分别假设 A 和 B 在最优情况下的后续得分（即后面每次点球都罚进），再将情况合并后判断能否分出胜负。

用 A 和 B 分别表示当前 A 和 B 的得分， Abest 表示 A 的最优情况，Bbest 表示 B 的最优情况，两者得分相减，可得到两个式子：

对于 A ：后面 A 全罚进，B 全罚不进，即 (A + Abest) - B

对于 B ：后面 B 全罚进，A 全罚不进，即 (B + Bbest) - A

如果能分出胜负，那么就 有一方即使在最优情况下的最终得分也没有对方高。

即两式之间必有一个 <0 ，相乘后判断结果即可。

代码：

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    string s;
    cin >> s;
    s = ' ' + s;
    
    int A = 0, B = 0;
    for (int i = 1; i <= 10; i++){
        if (s[i] == '1'){
            if (i % 2) A++;
            else B++;
        }
        
        int Abest = (10 - i) / 2, Bbest = (11 - i) / 2;
        if ((A + Abest - B) * (B + Bbest - A) < 0){
            cout << i << endl;
            return;
        }
    }
    
    cout << -1 << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--){
        solve();
    }
    
    return 0;
}

题意：

教授发表论文，定义 H 表示 ”该教授发表的所有论文中，有至少 $H$ 篇论文的引用量大于等于 $H$ “。

给定 n 位教授，和长度为 n 的数组，表示每个人的引用量，每人都有一篇写好的论文未发表。

规定每篇论文只能被一位教授发表，一位教授可以发表多篇论文。

求重新分配每个教授发表的论文数后，所有教授的 H 指数之和的最大值。

思路：

分析 H 的定义，换句话来说，就是如果引用量不为 0 的话，则至少有 1 篇论文的引用量大于等于 1，即 H 表示最小值，如果这个人论文的引用量不为 0，其 H 指数为 1.

再根据其定义，发现 H 不可能多于总的引用非0论文数，所以最好的分配方案就是不分配。

依次枚举，如果引用量非0，则 H + 1，否则就跳过。

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;

void solve()
{
    int n;
    cin >> n;
    
    int res = 0;
    for (int i = 1; i <= n; i++){
        int x;
        cin >> x;
        if (x) res ++;
    }
    
    cout << res << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--){
        solve();
    }
    
    return 0;
}

题意：

在第一象限内给定两个坐标 (x, y) 和 (x_p, y_p)，其中第一个表示由 (0, 0), (x, y) 两点确定的目标框，第二个表示由 (x_p, y_p) 和某个点确定的预测框。

要求 目标框和预测框两个矩形交集部分的面积除以并集部分的面积的最大值。

思路：

要使情况最优，则预测框的另一个顶点一定是目标框的四个顶点 ABCD 之一。

可以以点 (x, y) 为中心，分为 ”左上、右上、左下、右下“ 四个部分分类讨论，取最大值。

如下图所示：

1. 左下，即目标框内部：
   枚举 A、B、C、D 作为另一顶点的四种情况，取最大值。

2. 左上：
   枚举 A、B 作为另一顶点的两种情况，取最大值。

3. 右上：
   取 A 作为另一顶点。

4. 右下：
   枚举 A、D 作为另一顶点的两种情况，取最大值。

代码：

#include <bits/stdc++.h>
using namespace std;

int x, y, xp, yp;

void solve()
{
    cin >> x >> y >> xp >> yp;
    
    double res = 0;
    if (xp <= x && yp <= y)  //左下
    {
        res = max(res, 1.0 * (xp * yp) / (x * y));  //A
        res = max(res, 1.0 * (x - xp) * yp / (x * y));  //B
        res = max(res, 1.0 * (x - xp) * (y - yp) / (x * y));  //C
        res = max(res, 1.0 * (xp) * (y - yp) / (x * y));  //D

        printf("%.9f\n", res);
        return;
    }
    if (xp <= x)  //左上
    {
        res = max(res, 1.0 * (xp * y) / (x * y + xp * (yp - y)));  //A
        res = max(res, 1.0 * (x - xp) * y / (x * y + (x - xp) * (yp - y)));  //B        
        
        printf("%.9f\n", res);
        return;
    }
    if (yp <= y) //右下
    {
        res = max(res, 1.0 * (x * yp) / (x * y + (xp - x) * yp));  //A
        res = max(res, 1.0 * (x) * (y - yp) / (x * y + (xp - x) * (y - yp)));  //D

        printf("%.9f\n", res);
        return;
    }
    
    //右上
    res = max(res, 1.0 * (x * y) / (xp * yp)); //A
    printf("%.9f\n", res);
}

int main()
{
    int t;
    cin >> t;
    while (t--){
        solve();
    }

    return 0;
}

题意：

有一个拼图游戏，由 n × n 个大小为 1 × 1 的拼图块组成，每个拼图块都是在正方形的 1 × 1 拼图块基础上生成的

生成方法为：对于每一条边，可以选择不变、向里削出一个半圆形的缺口、向外补上一个半圆形的凸出三种操作之一。

因此，一个拼图块可以由一个长度为 4 的字符串描述，四个字符分别表示上、右、下、左四条边进行的操作，上述三种操作依次记 0, 1, 2.

如下图所示：

每块拼图还有一个制作成本 p ，制作成本正比于面积，而拼图中削去的缺口和补上的凸出面积又相同，因此对于一块削去了 x 个半圆、补上了 y 个半圆的 1 × 1 拼图，其制作成本 p = 10 − x + y 。如上图中拼图的成本为 p = 10 − 1 + 1 = 10。

现给出 n × n - 1 块表示拼图形状的字符串，要求出缺少的那块拼图的制作成本。

思路：

观察一下就会发现，所有小拼图组成一块大拼图，每块小拼图的形状都不一样，但是组成的大拼图一定是个正方形，其中的小拼图每条边都可能存在互补关系，缺口可由凸口补上。

因为 拼图总成本 = 给出拼图的成本 + 缺失拼图的成本，且大拼图总成本为 $10n^2$ .

所以要求缺少的拼图的成本，只需 用总成本减去已知拼图的成本 即可。

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;

void solve()
{
    int n;
    cin >> n;
    
    int res = 10 * n * n;
    for (int i = 1; i <= n * n - 1; i++){
        string s;
        cin >> s;
        int x = 0, y = 0;
        for (int j = 0; j < 4; j++){
            if (s[j] == '1') x++;
            if (s[j] == '2') y++;
        }
        
        res -= (10 - x + y);
    }
    
    cout << res << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--){
        solve();
    }
    
    return 0;
}

题意：

给定 5 个团体，每个团体都有 4 个人。

要求找到一个人，问在最优策略下，需要猜多少次，输出期望次数。

有 100 个选项，编号从 1 至 100，第 $i$ 个选项为 $3.45+0.05\ast i$ ，输出与答案最接近的选项编号。

思路：

因为每个团、每个人之间都一样，所以最佳策略就是依次猜，先猜出团，再猜出团里的人。

先猜团：5 个团，第一次猜中的概率为 0.2，第二次为 0.2，第三次为 0.2，第四次为 0.4 .

再猜团：4 个人，第一次猜中的概率为 0.25，第二次为 0.25，第三次为 0.5 .

再用计算数学期望的方法计算一下，得到最终答案为：

  0.2 × 1 + 0.2 × 2 + 0.2 × 3 + 0.4 × 4
+ 0.25 × 1 + 0.25 × 2 + 0.5 × 3
= 5.05

即 $5.05=3.45+0.05\times i$ ，得 $i=32$ .

代码：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    cout << 32 << endl;

    return 0;
}