前言

出题人主观难度顺序（由易到难）：

题目	难度
B.雨和卡布奇诺	easy
F.帮我给这道题起一个帅气的名字
A.夕凪、某处、烟火
D.Eimy	medium
C.鹦鹉螺号
H.Zuma's Revenge
G.?	hard
E.小憨的矩阵

但是呢，出题人主观难度并不一定和实际难度相符，所以下面的题解顺序就直接按照题目字母顺序来写了。

题解目录

• A.夕凪、某处、烟火
  • 分析
  • 动态规划（完全背包问题）
    • 代码实现
• B.雨和卡布奇诺
  • 分析
  • 具体做法
    • 代码实现
• C.鹦鹉螺号
  • 代码实现
• D.Eimy
  • 分析
  • 具体做法
    • 代码实现
• E.小憨的矩阵
  • 分析
  • 具体做法
    • 代码实现
• F.帮我给这道题起一个帅气的名字
  • 分析
  • 方法一
    • 代码实现
  • 方法二
    • 代码实现
• G.?
  • 分析
  • 具体做法
    • 代码实现
• H.Zuma's Revenge
  • 分析：
  • 参考做法：
  • 参考代码

题解

A.夕凪、某处、烟火

分析

首先先把题意翻译成人话：

你有一个只包含 0 和 1 的字符串。一次操作你可以选择一段连续的 0 但这段 0 的长度必须恰好等于 a 或 b 或 c，然后把这一整段 0 全部变成 1，目标是用最少的操作次数，把整个字符串都变成 1；如果根本做不到，输出 -1

关键发现：已经是 1 的地方完全不用管，因为操作只能对连续的 0 生效，所以我们完全可以把原串拆成若干段连续 0 的区间：

比如

111000110000100

我们可以把它视作

111 000 11 0000 1 00
     ↑      ↑      ↑
    长度3  长度4  长度2

只处理 0 的部分即可，而且每段 0 之间是互不影响的，所以可以独立处理，这样的话对于每段，子问题就变成了：

给你一个数 $len$，你是否能用若干个 $a$ 和 $b$ 和 $c$ 的和表示它？如果能，最少需要多少个数？

只要有一段 0 是无法表示的，那么整个字符串就无法操作成功，输出 -1 即可；否则把每段 0 的最少操作次数加起来就是答案。

动态规划（完全背包问题）

这个问题可以用动态规划来解决，思路是：

• 定义一个数组 $\text{dp}$，其中 $\text{dp}[i]$ 表示长度为 $i$ 的连续 0 最少需要多少次操作才能全部变成 1。如果无法变成 1，则 $\text{dp}[i]$ 为无穷大。

• 初始化 $\text{dp}[0] = 0$，表示长度为 0 的连续 0 不需要任何操作。

• 对于每个长度 $i$ 从 1 到 $len$，我们检查是否可以通过从 $i - a$ 的位置添加长度为 $a$ 或从 $i - b$ 的位置添加长度为 $b$ 或从 $i - c$ 的位置添加长度为 $c$的块转移到长度 $i$。具体来说：

  • 如果 $i >= a$，则更新 $\text{dp}[i] = \min(\text{dp}[i], \text{dp}[i - a] + 1)$。

  • 如果 $i >= b$，则更新 $\text{dp}[i] = \min(\text{dp}[i], \text{dp}[i - b] + 1)$。

  • 如果 $i >= c$，则更新 $\text{dp}[i] = \min(\text{dp}[i], \text{dp}[i - c] + 1)$。

• 最终，$\text{dp}[len]$ 就是长度为 $len$ 的连续 0 最少需要的操作次数。如果 $\text{dp}[len]$ 仍为无穷大，则表示无法将其全部变成 1。

代码实现

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

static const int INF = 1e9;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    int a, b, c;
    cin >> a >> b >> c;
    string s;
    cin >> s;
    vector<int> dp(n + 1, INF);
    dp[0] = 0;

    for (int i = 1; i <= n; i++)
    {
        if (i >= a)
            dp[i] = min(dp[i], dp[i - a] + 1);
        if (i >= b)
            dp[i] = min(dp[i], dp[i - b] + 1);
        if (i >= c)
            dp[i] = min(dp[i], dp[i - c] + 1);
    }

    long long ans = 0;
    int i = 0;

    while (i < n)
    {
        if (s[i] == '1')
        {
            i++;
            continue;
        }
        int j = i;
        while (j < n && s[j] == '0') j++;
        int len = j - i;

        if (dp[len] == INF)
        {
            cout << -1 << '\n';
            return 0;
        }

        ans += dp[len];
        i = j;
    }

    cout << ans << '\n';
    return 0;
}

B.雨和卡布奇诺

分析

题目大意：

一开始有个矩阵，对它进行 $k$ 次操作，每次选择一个点，将这个点所在的行和列的所有元素加 $x$; 然后给你最终矩阵，问你最初的矩阵是什么？

由于加法运算和减法运算互为逆运算且加法满足交换律和结合律，我们可以把问题反过来想

具体做法

从最终矩阵出发，进行 $k$ 次操作，每次选择一个点，将这个点所在的行和列的所有元素减 $x$，最终得到的矩阵就是最初的矩阵。

我们可以记录每行每列总共需要减去多少，在输出前再算出原来的值即可。时间复杂度为 $O(nm + k)$。

代码实现

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n,m,k;
    cin >> n >> m >> k;
    vector<vector<int>> v(n + 1, vector<int>(m + 1));

    for(int i{}; i < n; ++i)
    {
        for(int j{}; j < m; ++j)
        {
            cin >> v[i + 1][j + 1];
        }
    }
    vector<int> r(n + 1), c(m + 1);
    for(int i{}; i < k; ++i)
    {
        int x{},y{},z{};
        cin >> x >> y >> z;
        r[x] += z;
        c[y] += z;
        v[x][y] += z;
    }

    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            v[i][j] -= r[i];
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            v[i][j] -= c[j];
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            cout << v[i][j] << ' ';
        }
        cout << '\n';
    }
}

C.鹦鹉螺号

不难发现，随着分割线 $x$ 坐标的增加，线左侧面积是单调递增的。

如果我们要寻找最小的 $b$ 使得左侧面积大于等于总面积的一半，这样的话 $x < b$ 一定不满足条件，而 $x \geq b$ 一定满足条件。显然我们可以使用二分答案来寻找满足条件的 $x$ 坐标。

假设当前的选择的答案为 $mid$，我们需要计算左侧面积是否大于等于总面积的一半。计算过程只需要遍历一遍所有矩形，将位于 $mid$ 左侧的部分面积累加起来即可，最后判断是否大于等于总面积的一半，若大于等于则说明 $mid$ 是一个可行解，我们尝试缩小右边界，否则增大左边界。

时间复杂度为 $O(n \log M)$，其中 $M$ 是 $x$ 轴的最大坐标值。

代码实现

#include <bits/stdc++.h>
using namespace std;
#define double long double
struct loc {
    double x1, y1, x2, y2;
};

int main()
{
    int n;
    cin >> n;
    vector<loc> arr(n);

    double total_area = 0.0;
    for (auto& i : arr)
    {
        cin >> i.x1 >> i.y1 >> i.x2 >> i.y2;
        double w = abs(i.x2 - i.x1);
        double h = abs(i.y2 - i.y1);
        total_area += w * h;
    }

    auto check = [&](double b) {
        double left_area = 0.0;
        for (auto& r : arr)
        {
            double xl = min(r.x1, r.x2);
            double xr = max(r.x1, r.x2);
            double h = abs(r.y1 - r.y2);

            if (b <= xl)
                continue;
            else if (b >= xr)
                left_area += (xr - xl) * h;
            else
                left_area += (b - xl) * h;
        }
        return left_area * 2 >= total_area;
    };

    double l = -1e9, r = 1e9;
    for (int i = 0; i < 100; i++)
    {
        double mid = (l + r) / 2.0;
        if (check(mid))
            r = mid;
        else
            l = mid;
    }

    cout << fixed << setprecision(10) << r << "\n";
    return 0;
}

D.Eimy

分析

题目大意：

找一对整数 $a,b$ 表达出 $a \div b = x$，其中 $x$ 为整数部分为 $0$ 的无限循环小数，循环节长度为 $n$。

具体做法

将循环节表示为 $s$，那么此时小数 $x = 0.sss...$。将小数 $x$ 乘以 $10^{n}$ 得到小数 $s.sss..$。相减可得等式 $10^{n} x - x = s$,化简可得:

$$x = \frac{s}{10^{n} - 1} = \frac{s}{\underbrace{9\dots 9}_{n}}$$

输出循环节和 $n$ 个 $9$ 即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    string str;
    cin >> str;
    string ans;
    for(int i = 0; i < n; i++) {
        ans += '9';
    }
    cout << str << ' ' << ans << endl;
    return 0;
}

E.小憨的矩阵

分析

题目大意：

给出一个矩阵，其中由若干个障碍物，问是否能从左上角走到右下角。

具体做法

观察数据范围可发现这道题并不能建图跑bfs。手搓几个样例可观察到一些性质，上边缘或右边缘没有与下边缘或左边缘相连时一定存在一条可行的路径，等价于这张图不存在一个最小割（网络流定理）。此时只需要将通过障碍物来判断上边缘或右边缘是否与下边缘或左边缘联通即可，使用bfs或并查集均可达成。时间复杂度 $O(k)$

代码实现

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

// solve using BFS

auto main() -> int
{
    int n, m, k;
    cin >> n >> m >> k;

    map<P, int> mp;

    queue<P> q;

    for (int i{}; i < k; ++i)
    {
        int x, y;
        cin >> x >> y;
        mp[{x, y}] = 0;

        if (x == 1 || y == m)
        {
            q.emplace(x, y);
            mp[{x, y}] = 1;
        }
    }

    int dx[]{1, 0, -1, 0, 1, 1, -1, -1}, dy[]{0, -1, 0, 1, 1, -1, 1, -1};

    while (q.size())
    {
        auto [x, y] = q.front();
        q.pop();
        if (x == n || y == 1)
        {
            cout << "No";
            return 0;
        }

        for (int i{}; i < 8; ++i)
        {
            int xx = x + dx[i], yy = y + dy[i];
            if (mp.contains({xx, yy}))
            {
                if (mp[{xx, yy}] == 0)
                {
                    q.emplace(xx, yy);
                    mp[{xx, yy}] = 1;
                }
            }
        }
    }

    cout << "Yes";
}

F.帮我给这道题起一个帅气的名字

分析

题目大意：

可以不停的射靶子，每次射中概率为 $p$，射中一次得一分，但只要没射中就结束并且分数清零。问应该射几次能使得期望分数最大。

注意到，射 $n$ 次想要得分的话中途一定不能出现任何一次没射中，也就是说 $n$ 次射击必须全部命中，概率为 $p^n$，得分为 $n$，因此期望分数为：$E(n) = n \cdot p^n$。若 $p=1$，则期望分数无穷大。

问期望的最大值， 将 $E(n)$ 对 $n$ 求导得：

$$E'(n) = p^n + n \cdot p^n \ln p = p^n (1 + n \ln p)$$

不难发现这个导数在 $n = -\frac{1}{\ln p}$ 处取零，且当 $n < -\frac{1}{\ln p}$ 时 $E(n)$ 单调递增，$n > -\frac{1}{\ln p}$ 时 $E(n)$ 单调递减。

方法一

根据求导结果发现在 $n = -\frac{1}{\ln p}$ 处取得极大值。

但是题目要求 $n$ 必须为整数，因此我们需要比较 $E(\lfloor -\frac{1}{\ln p} \rfloor)$ 和 $E(\lceil -\frac{1}{\ln p} \rceil)$ 的大小，取较大值对应的 $n$ 即为答案。

代码实现

#include <bits/stdc++.h>
using namespace std;
int main(){
    int pp;
    cin >> pp;
    // 特殊情况：命中率为 100%，期望无穷大
    if(pp == 100){
        cout << "inf" << endl;
        return 0;
    }
    double p = pp / 100.0;
    // 计算 -1 / ln(p)
    double x = -1.0 / log(p);
    int k1 = floor(x);
    int k2 = ceil(x);
    // 计算 E(k1) 和 E(k2)
    double e1 = k1 * pow(p, k1);
    double e2 = k2 * pow(p, k2);
    // 输出期望较大的 k
    if(e1 >= e2){
        cout << k1 << endl;
    }else{
        cout << k2 << endl;
    }
}

方法二

根据导数已知 $E(n)$ 的单调性是先递增后递减的，因此我们可以从 $n=1$ 开始枚举，直到发现 $E(n+1) \leq E(n)$ 并且 $E(n-1) \leq E(n)$ 为止，即：

$$np^n \geq (n - 1)p^{n - 1} \Rarr p \geq \frac{n - 1}{n}\\ ~ \\ np^n \geq (n + 1)p^{n + 1} \Rarr p \leq \frac{n}{n + 1}$$

代码实现

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

int main() {
    int pp;
    if (cin >> pp) {
        // 特殊情况：如果命中率为 100%，射得越多分越高，期望无穷大
        if (pp == 100) {
            cout << "inf" << endl;
            return 0;
        }
        double p = pp / 100.0;
        int k = 1;
        for(;; ++k) {
            // 检查是否满足停止条件
            if (p >= 1.0 * (k - 1) / k && p <= 1.0 * k / (k + 1)) {
                cout << k;
                break;
            }
        }
    }
}

G.?

分析

题目大意：

Alice 和 Bob 拿到一棵树，每个人可以选择切掉一条边并将不含根的边丢弃。最先无法操作的人失败。alice先手。

具体做法

首先，我们容易发现，这道题中的胜负关系是和 1 号节点相连接的所有子树的形态有关。

于是，受 $SG$ 函数影响，我们不妨把这个游戏分割成若干个子游戏，也就是 1 号点的每一棵子树都分开来考虑，并将每个子树的根与 1 号点相连。

很显然，每一个子游戏都是有向图游戏，根据有向图游戏的知识，我们不妨假设每一棵子树的 $SG$ 值求出来，再将 $SG$ 值异或起来，根据定义，当且仅当异或值为 0 时先手必败。

现在我们来考虑如何求出每一棵子树的 $SG$ 值，下面使用归纳法求解：

• 叶节点的 $SG$ 值为 $0$（先手必败）；

• 现在沿着连接叶节点的边向根走，假设目前的结点为 $x$，它有 $y_1,y_2,y_3 \dots y_k$ 的叶子节点，根据 $SG$ 值的定义，有：

$$SG(x) = mex\{SG(y_1),SG(y_2),SG(y_3),\dots SG(y_k)\}$$

• 容易推出，$SG(x)=1$；

再次归纳，如果删了 $x$ 结点的子树内的一条边，是不是相当于整个子树变小了，但是 $SG(x)$ 值仍不为 $0$；如果删了 $x$ 结点到其父亲的边呢？很明显，$SG(x)$ 变成了 $0$；

又根据 $SG$ 的定义，如果 $SG(x)$ 不为 $0$，那从 $x$ 的子结点出发形成的子游戏的 $SG$ 值一定包含了 $0∼SG(x)−1$ 的所有数；

综上所述，操作完一步后的子游戏的 $SG$ 值可以是 $0∼SG(x)$ 中的任何数；

根据刚刚那个式子，可以得到这个有向图子游戏传递给父亲的的 $SG$ 值为 $SG(x)+1$，从而得出结论。

那么，代码只要通过 $DFS$ 求出每个子树的 $SG$ 值就可以了，记得加上 $1$。

代码实现

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n{};
    cin >> n;
    vector<vector<int>> g(n + 1);

    for (int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    auto dfs = [&](auto &&dfs, int u, int fa) -> int
    {
        int re{};

        for (auto &v : g[u])
        {
            if (v == fa)
                continue;
            re ^= dfs(dfs, v, u) + 1;
        }

        return re;
    };

    if (dfs(dfs, 1, 0) != 0)
    {
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }
}

H.Zuma's Revenge

分析：

题目大意是$k$个球挨在一起就会消除这$k$个球，并且是环形轨道即第一个球和最后一个球挨在一起。要求把所有球消除完后还剩多少球。

参考做法：

先假设不是环形轨道，使用栈模拟一遍，将能消除的球先消除。再用双端队列判断首尾的球可不可以被消除掉（即是否满足首尾元素相等并且连续的个数大于等于$k$），如果可以继续模拟消除过程，不可以则直接退出循环。

参考代码

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

int main() {
    int n,k;
    cin >> n >> k;
    stack<pair<int,int>> st;
    for(int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if(st.empty()){
            st.push({x,1});
            continue;
        }

        if(st.top().first == x){
            st.push({x,st.top().second + 1});
        }else{
            st.push({x,1});
        }

        if(st.top().second == k){
            for(int j = 0; j < k; ++j) st.pop();
        }

    }

    deque<int> v;
    int ans = st.size();
    while(!st.empty()) {
        v.push_front(st.top().first);
        st.pop();
    }

    while(v.size() >= k && v.front() == v.back()) {
        int x = v.front();
        int cnt = 0;

        int i = 0;
        while(i < v.size() && v[i] == x) {
            cnt++;
            i++;
        }
        int j = v.size() - 1;
        while(j >= 0 && v[j] == x) {
            cnt++;
            j--;
        }

        if(cnt > v.size()) cnt = v.size();

        if(cnt >= k) {
            int res = 0;
            while(v.front() == x && res < k){
                v.pop_front();
                res++;
            }
            while(v.back() == x && res < k){
                v.pop_back();
                res++;
            }
            ans -= k;
        }else{
            break;
        }
    }

    cout << ans << endl;
    return 0;
}