25年秋-期末考核-25
25年秋-期末考核-25 题解
mayoi_Akira ✌️🦌➗ LV 5 @ 2025-12-30 10:58:51

前言

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

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

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

题解目录

A.夕凪、某处、烟火
B.雨和卡布奇诺
- 分析
- 具体做法
  - 代码实现
C.鹦鹉螺号
D.Eimy
- 分析
- 具体做法
  - 代码实现
E.小憨的矩阵
- 分析
- 具体做法
  - 代码实现
F.帮我给这道题起一个帅气的名字
- 分析
- 具体做法
  - 代码实现
G.?
- 分析
- 具体做法
  - 代码实现
H. Zuma's Revenge
- 分析
- 具体做法
  - 代码实现

题解

A.夕凪、某处、烟火

分析

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

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

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

比如

111000110000100

我们可以把它视作

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

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

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

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

方法一：暴力枚举

这个问题用数学方法表示的话，就是解以下不定方程：

ax + by = len \quad (x,y \geq 0)

同时要求让 $x + y$ 最小。

我们可以枚举所有可能的 $x$ 的值，然后计算出对应的 $y$ ，同时维护 $x + y$ 的最小值。

每一段的时间复杂度为 $O(\frac{len}{a})$ ，但由于 $\sum{len}\leq n$ ，所以总时间复杂度为 $O(\frac{n}{a})$ ，完全可以接受。

代码实现

#include<stdio.h>

const int inf = 1e9;

// 处理每一段连续的0，判断最小操作次数
int seg(int len, int a, int b)
{
    // 由于要维护最小值，所以答案初始化为无穷大
    int res = inf;
    // x表示使用长度为 a 的块的数量
    // x的最大可能值为 len / a
    for (int x = 0; x * a <= len; ++x)
    {
        // 检查剩余长度是否能被 b 整除
        if ((len - a * x) % b == 0)
        {
            // 计算使用长度为 b 的块的数量
            int y = (len - a * x) / b;
            // 使用 x 块 a 和 y 块 b
            // 更新最小值
            if(x + y < res)
                res = x + y;
        }
    }
    // 如果res从未更新过，说明没有找到可行解，返回 -1
    if (res == inf)
        return -1;
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    int a, b;
    scanf("%d %d", &a, &b);
    char s[n + 1];
    scanf("%s", s);
    // res是最终答案
    int res = 0;
    // cnt记录当前连续0的数量
    int cnt = 0;
    for (int i = 0; i <= n; ++i)
    {
        // 如果当前字符是'0'，增加计数
        if (s[i] == '0')
            cnt++;
        // 遇到'1'或者字符串末尾('\0')，处理之前的连续0段
        else
        {
            // cnt大于0时才处理
            if (cnt > 0)
            {
                // 处理当前连续0段
                int seg_res = seg(cnt, a, b);
                // 如果该段无法被分割，输出-1并结束程序
                if (seg_res == -1)
                {
                    printf("-1\n");
                    return 0;
                }
                // 累加当前段的结果到总结果中
                res += seg_res;
                // 重置计数器
                cnt = 0;
            }
        }
    }
    printf("%d", res);
    return 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$ 。具体来说：
- 如果 $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)$。
最终， $\text{dp}[len]$ 就是长度为 $len$ 的连续 0 最少需要的操作次数。如果 $\text{dp}[len]$ 仍为无穷大，则表示无法将其全部变成 1。

代码实现

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

const int inf = 1e9;

int main()
{
    int n;
    cin >> n;
    int a, b;
    cin >> a >> b;
    string s;
    cin >> s;
    // 在字符串末尾添加一个'1'，方便处理结尾的连续0段
    s += '1';
    // 预处理dp数组，dp[i]表示长度为i的连续0段的最小操作次数
    vector<int> dp(n + 1, inf);
    dp[0] = 0;

    // 动态规划计算dp数组
    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);
    }

    // 这里dp数组已经预准备好了，开始处理字符串
    // 对于每一段连续的0，直接使用预处理好的dp数组查询最小操作次数

    // res是最终答案
    int res = 0;
    // cnt记录当前连续0的数量
    int cnt = 0;
    for (int i = 0; i <= n; ++i)
    {
        // 如果当前字符是'0'，增加计数
        if (s[i] == '0')
            cnt++;
        // 遇到'1'时处理之前的连续0段
        else
        {
            // cnt大于0时才处理
            if (cnt > 0)
            {
                // 处理当前连续0段
                int seg_res = dp[cnt];
                // 如果该段无法被分割，输出-1并结束程序
                if (seg_res == inf)
                {
                    printf("-1\n");
                    return 0;
                }
                // 累加当前段的结果到总结果中
                res += seg_res;
                // 重置计数器
                cnt = 0;
            }
        }
    }

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

B.雨和卡布奇诺

分析

题目大意：

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

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

具体做法

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

代码完全按照这个思路走一遍即可， $n、m、k$ 的规模都比较小，直接模拟即可。时间复杂度为 $O(nmk)$ 。

代码实现

#include<stdio.h>
int main(){
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    int B[n][m];
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            scanf("%d", &B[i][j]);
    while(k--)
    {
        int a, b, x;
        scanf("%d%d%d", &a, &b, &x);
        a--,b--;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                if(i == a || j == b)
                    B[i][j] -= x;
    }
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < m; ++j)
            printf("%d ", B[i][j]);
        printf("\n");
    }
}

C.鹦鹉螺号

分析

题目大意：

给出 $n$ 个互不相交的矩形，找出一个平行于 $y$ 轴的直线把坐标系分成左右两部分，使得左边所有矩形的面积和与右边所有矩形的面积和相等。题目保证了一定有解

方法一：差分、前缀和

把整个坐标系分成一个个 $1\times 1$ 的小方格来考虑。

然后考虑在 $x$ 轴上每个 $\left[a,a+1\right)$ 区间内矩形部分覆盖了多少个小方格。

不难发现，对于每个矩形 $\left(x_1,y_1,x_2,y_2\right)$ ，它会对 $x$ 轴上 $\left[x_1,x_2\right)$ 范围内的每个单位区间都贡献 $(y_1 - y_2)$ 个小方格。注意到， $x$ 的范围很大，但变化点很少，所以我们可以使用差分数组 $\text{diff}$ 来高效地记录这些变化。

diff[x1] += (y1 - y2);
diff[x2] -= (y1 - y2);

差分完成后，我们可以通过对 $\rm diff$ 数组进行前缀和计算出每个单位区间内被覆盖的小方格数量。

for (int i = 1; i <= max_x; ++i)
    diff[i] += diff[i - 1];

现在 $\rm diff$ 数组的含义是：对于每个 $i$ ， $\rm diff[i]$ 表示 $x$ 轴上 $\left[i,i+1\right)$ 区间内被覆盖的小方格数量。

接下来，我们计算前缀和数组 $\rm pre$ ，其中 $\rm pre[i]$ 表示从 $0$ 到 $i-1$ 的所有单位区间内被覆盖的小方格总数。

for (int i = 1; i <= max_x; ++i)
    pre[i] = pre[i - 1] + diff[i - 1];

$\rm pre$ 数组的含义是：对于每个 $i$ ， $\rm pre[i]$ 表示从 $0$ 到 $i-1$ 的所有单位区间内被覆盖的小方格总数。显然，设总面积为 $S$ ，若 $\rm pre[i] = S/2$ ，则 $i$ 就是我们要找的分割线位置。

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

代码实现

#include <stdio.h>
int diff[1000005];
int pre[1000005];
int main()
{
    int n;
    scanf("%d", &n);

    // 记录所有矩形的总面积
    int total = 0;

    for (int i = 0; i < n; i++)
    {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

        int h = y1 - y2; // 矩形高度
        // 差分数组记录区间覆盖情况
        diff[x1] += h;
        diff[x2] -= h;

        total += h * (x2 - x1); // 总面积
    }

    // 计算前缀和，得到每个单位区间的覆盖数量
    for (int i = 1; i <= 1000000; ++i)
        diff[i] += diff[i - 1];

    // 计算前缀和，得到从0到i-1的覆盖总数
    for (int i = 1; i <= 1000000; ++i)
    {
        pre[i] = pre[i - 1] + diff[i - 1];
        // 检查是否达到了总面积的一半
        if (pre[i] * 2 == total)
        {
            printf("%d\n", i);
            return 0;
        }
    }

    return 0;
}

方法二：二分答案

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

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

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

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

代码实现

#include <stdio.h>
struct rect{
    int x1, y1, x2, y2;
};
int main()
{
    int n;
    scanf("%d", &n);

    // 记录所有矩形的总面积
    int total = 0;
    struct rect rects[n];
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d %d %d", &rects[i].x1, &rects[i].y1, &rects[i].x2, &rects[i].y2);

        int h = rects[i].y1 - rects[i].y2; // 矩形高度
        total += h * (rects[i].x2 - rects[i].x1); // 总面积
    }

    // 二分答案
    int left = 0, right = 1000000;

    // 开区间写法
    while(left + 1 < right)
    {
        int mid = (left + right) / 2;
        int area = 0; // 左侧累计面积

        for (int i = 0; i < n; i++)
        {
            int h = rects[i].y1 - rects[i].y2; // 矩形高度

            // 如果整个矩形在 mid 右侧
            if (rects[i].x1 >= mid)
                continue;

            // 如果整个矩形在 mid 左侧
            else if (rects[i].x2 <= mid)
                area += h * (rects[i].x2 - rects[i].x1);

            // 如果矩形横跨 mid
            else
                area += h * (mid - rects[i].x1);
        }

        // 更新二分区间
        if (area * 2 >= total)
            right = mid;
        else
            left = mid;
    }
    printf("%d", right);
    return 0;
}

D.Eimy

分析

题目大意：

给出一个无限循环的长度为 $n$ 的循环节，输出 $l$ 到 $r$ 范围内的子串。

由于循环节是无限循环的，所以 $n + 1$ 的位置和 $1$ 位置是相同的， $n + 2$ 的位置和 $2$ 位置是相同的，以此类推。

具体做法

我们可以通过取模运算来实现对循环节的访问。具体来说，对于位置 $i$ ，我们可以计算出它在循环节中的对应位置为 $(i - 1) \mod n + 1$ 。这样，我们就可以直接访问循环节中的字符。由于输入字符串是 0-based 的，我们需要将计算结果减 1 来访问字符串。

特别注意：int 是存不下的，必须全程使用 long long 类型

代码实现

#include <stdio.h>
int main() {
    long long n, l, r;
    scanf("%lld", &n);
    char s[n + 1];
    scanf("%s", s);
    scanf("%lld %lld", &l, &r);
    for (long long i = l; i <= r; ++i) {
        // 计算当前位置在循环节中的对应位置并输出
        printf("%c", s[(i - 1) % n]);
    }
    printf("\n");
    return 0;
}

E.小憨的矩阵

分析

题目大意：

给出一个矩阵，求从左上角到右下角的最短时间，矩阵中有一些传送门，到达这些传送门可以花 $t$ 时间直接到达右下角。

不难发现，不使用传送门的话，从左上角到矩阵中的任意一个位置 $(x,y)$ 所花费的时间均为 $(x - 1) + (y - 1) = x + y - 2$ 。所以，不使用传送门的情况下，直接到达右下角所需时间为 $n + m - 2$ 。

如果使用传送门的话，假设传送门的位置为 $(x_i,y_i)$ ，那么从左上角到达该传送门所需时间为 $x_i + y_i - 2$ ，然后再花费 $t$ 时间直接到达右下角。因此，使用传送门的总时间为 $x_i + y_i - 2 + t$ 。

综上所述，我们只需要计算所有传送门的时间，并与不使用传送门的时间进行比较，取最小值即可。

具体做法

初始化答案为不使用传送门的时间 $n + m - 2$ ，然后遍历所有传送门，计算到达每个传送门的时间并加上 $t$ ，维护答案最小值。

特别注意：可能不存在传送门（k 等于 0）

代码实现

#include<stdio.h>

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    int k, t;
    scanf("%d %d", &k, &t);

    // 不用传送门的花费
    int ans = n + m - 2;
    for (int i = 0; i < k; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        // 使用传送门的花费
        int cost = x + y - 2 + t;
        // 如果比当前答案更小，更新答案
        if (cost < ans)
            ans = cost;
    }

    printf("%d\n", ans);
    return 0;
}

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

分析

题目大意：

射 $n$ 次靶子，命中得一分，第一次命中率是百分百，之后每次下降 $\frac{1}{n}$ 。求最终得分的数学期望。

由于每次射击之间相互独立，所以我们直接对每次射击单独计算期望，然后把它们加起来就是最终期望。

具体做法

第 $i$ 次射击的命中概率为 $\frac{n - (i - 1)}{n}$ ，所以第 $i$ 次射击的期望得分为 $\frac{n - (i - 1)}{n} \times 1 + \frac{i - 1}{n} \times 0 = \frac{n - (i - 1)}{n}$。

所以，最终的期望得分，即答案为：

$$\begin{aligned} & \frac{n}{n} + \frac{n-1}{n} + \frac{n-2}{n} + \cdots + \frac{1}{n} \\ \\ = & \frac{n+(n-1)+(n-2)+\cdots+1}{n} \\ \\ = & \frac{\frac{n(n+1)}{2}}{n} \\ \\ = & \frac{n+1}{2} \end{aligned}$$

即答案直接输出 $\frac{n+1}{2}$ 即可。

特别注意：float 类型精度不够，必须使用 double 类型。建议在以后的代码中都使用 double 类型，完全不要考虑使用 float。

代码实现

#include <stdio.h>
int main() {
    double n;
    scanf("%lf", &n);
    printf("%.2f", (n + 1) / 2.0);
    return 0;
}

G.?

分析

题目大意：

纸上有 $n$ 个数，每次 Alice 会选择并擦掉一个 $a$ ，然后 Bob 会选择并擦掉一个数 $b$ ，如果 $a + b = k$ 则得 1 分。Alice 会尽力最小化得分，而 Bob 会尽力最大化得分。求最终得分。

不难发现，由于 Alice 先手，所以实际上她就是个小丑，是否得分完全取决于 Bob 能否找到合适的 $b$ 来配合 Alice 擦掉的 $a$ 。

游戏结束的条件是纸上没有数，而 Bob 又不傻，所以所有符合 $a + b = k$ 的 $(a,b)$ 一定都会得一分。所以最终得分一定会是所有符合 $a + b = k$ 的 $(a,b)$ 对数。

具体做法

我们可以使用一个哈希表 $\rm hash$ 来记录纸上剩余的数的频率。对于每个数 $a$ ，我们计算出 $b = k - a$ ，然后检查哈希表中是否存在 $b$ 。如果存在，那得分一定会增加 $\min(\text{hash}[a], \text{hash}[b])$ ，因为 Bob 都会尽力擦掉这些匹配的数。

需要注意的是，遍历整个哈希表后，每个 $(a,b)$ 对会被计算两次（一次是 $a$ ，一次是 $b$ ），所以最后的答案需要除以 2。

代码实现

#include <stdio.h>

int hash[200005];
int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        hash[x]++;
    }

    int ans = 0;
    for (int a = 0; a <= 200000; a++)
    {
        int b = k - a;
        if (b < 0 || b > 200000)
            continue;

        if(hash[a] < hash[b])
            ans += hash[a];
        else
            ans += hash[b];
    }

    // 每对 (a,b) 被计算了两次
    printf("%d\n", ans / 2);
    return 0;
}

H.Zuma's Revenge

分析

题目大意：

给出一个正整数序列，只要某个连续子序列中的值全部相等且长度等于 $k$ ，就可以把它们全部删除，问最后剩下的最短长度是多少。

可以看作是经典括号匹配问题的变种。需要用到数据结构栈。这里就不展开讲了。

具体做法

与括号匹配不同的是，每次入栈的时候需要检查栈顶元素是否和当前元素相等且数量达到了 $k$ ，如果是的话就把它们全部弹出。所以我们需要在栈中存储一个二元组，分别表示当前元素的值和数量。如果栈顶元素和当前元素相等，就把数量加一，若这时数量达到了 $k$ ，就把它们全部弹出；否则就把当前元素和数量 1 一起入栈。

代码实现

#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();
        }

    }
    cout << st.size() << endl;
    return 0;
}

Evonnezl LV 7 SU @ 2025-12-30 11:15:45

%%%

👍 1

❤️ 1

🕊️ 1

25年秋-期末考核-25 题解

前言

题解目录

题解

A.夕凪、某处、烟火

分析

方法一：暴力枚举

代码实现

方法二：动态规划（完全背包问题）

代码实现

B.雨和卡布奇诺

分析

具体做法

代码实现

C.鹦鹉螺号

分析

方法一：差分、前缀和

代码实现

方法二：二分答案

代码实现

D.Eimy

分析

具体做法

代码实现

E.小憨的矩阵

分析

具体做法

代码实现

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

分析

具体做法

代码实现

G.?

分析

具体做法

代码实现

H.Zuma's Revenge

分析

具体做法

代码实现

1 条评论

状态

开发

支持

关于

还没有账户？

登录