前言

先放一些题目上来，有时间再来一起解决它们。

1.融合各种算法知识点的题目

1.1.二进制加减

题目

题目描述

小 Z 最近学会了二进制数，他觉得太小的二进制数太没意思，于是他想对一个巨大二进制数做以下 $4$ 种基础运算：

运算 $1$：将整个二进制数加 $1$。

运算 $2$：将整个二进制数减 $1$。

运算 $3$：将整个二进制数乘 $2$。

运算 $4$：将整个二进制数整除 $2$。

小 Z 很想知道运算后的结果，他只好向你求助。

（Ps：为了简化问题，数据保证 +，- 操作不会导致最高位的进位与退位）

输入格式

第一行两个正整数 $n,m$，表示原二进制数的长度以及运算数。

接下来一行 $n$ 个字符，分别为 0 或 1 表示这个二进制数。

第三行 $m$ 个字符，分别为 +，-，*，/，对应运算 $1,2,3,4$。

输出格式

一行若干个字符，表示经过运算后的二进制数。

输入输出样例 #1

输入 #1

4 10
1101
*/-*-*-/*/

输出 #1

10110

说明/提示

对于 $30\%$ 的数据，$1 \leq n,m \leq 1000$。

对于 $60\%$ 的数据，$1 \leq n,m \leq 10^5$。

对于 $100\%$ 的数据，$1 \leq n,m \leq 5 \times 10^6$。

我的代码

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

#define int long long
#define all(x) (x).begin(), (x).end()

int32_t main(){
    int n,m;
    cin >> n >> m;
    string snum,op;
    cin >> snum >> op;
    int nums[n*2];
    for (int i=0;i<n;i++){
        nums[i]=snum[i]-'0';
    }
    for (int j=0;j<m;j++){
        if (op[j]=='+'){//加一
            for (int k=n-1;k>=0;k--){
                if (nums[k]==0){
                    nums[k]++;
                    break;
                }else{
                    nums[k]=0;
                }
            }
        }else if (op[j]=='-'){//减一
            for (int k=n-1;k>=0;k--){
                if (nums[k]==1){
                    nums[k]--;
                    break;
                }else{
                    nums[k]=1;
                }
            }
        }else if (op[j]=='*'){//乘2
            nums[n]=0;
            n++;
        }else{//整除2
            n--;
        }
    }
    for (int l=0;l<n;l++){
        printf("%d",nums[l]);
    }
    return 0;
}

答案是错误的，原因如下：

  1. 不能开int a[n*2]，会在编译时溢出。
  2. 对于加减1的模拟策略不对，只需要从最后一位向前扫描，例如加一时，只需要往前扫描直到找到第一个是0的位然后加一就行了。
  3. 在除二时有可能全都删完了，出现空向量，此时输出0就行了。
  4. 最后要去掉高位的多余的前导0，保留一个就行了。

o4-mini修正后的代码(我自己修正的代码后续更新，先挖坑)

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

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

    int n, m;
    cin >> n >> m;
    string snum, ops;
    cin >> snum >> ops;

    // 用 char 存 0/1，避免大数组占用过多内存
    vector<char> bits;
    bits.reserve(n + m + 1);
    for (char c : snum) {
        bits.push_back(c - '0');
    }

    for (char op : ops) {
        if (op == '+') {
            // 二进制加 1
            int k = bits.size() - 1;
            // 将末尾的 1 都翻成 0
            while (k >= 0 && bits[k] == 1) {
                bits[k] = 0;
                --k;
            }
            // 找到第一个 0 翻成 1（题目保证不会溢出到最高位外）
            if (k >= 0) {
                bits[k] = 1;
            }
        }
        else if (op == '-') {
            // 二进制减 1
            int k = bits.size() - 1;
            // 将末尾的 0 都翻成 1
            while (k >= 0 && bits[k] == 0) {
                bits[k] = 1;
                --k;
            }
            // 找到第一个 1 翻成 0（题目保证不会借位到最高位外）
            if (k >= 0) {
                bits[k] = 0;
            }
        }
        else if (op == '*') {
            // 乘 2 等同于在末尾添 0
            bits.push_back(0);
        }
        else {
            // 整除 2 等同于删掉最低位
            if (!bits.empty()) bits.pop_back();
            // 如果删光了，输出 0
            if (bits.empty()) bits.push_back(0);
        }
    }

    // 去掉高位多余的前导 0，但至少留一个
    int start = 0;
    while (start + 1 < (int)bits.size() && bits[start] == 0) {
        ++start;
    }
    for (int i = start; i < (int)bits.size(); ++i) {
        cout << char(bits[i] + '0');
    }
    cout << "\n";
    return 0;
}

也是成功ac了。

2.二分、前缀和

2.1.地毯(挖坑，待填)

题目

题目描述

在 $n\times n$ 的格子上有 $m$ 个地毯。

给出这些地毯的信息，问每个点被多少个地毯覆盖。

输入格式

第一行，两个正整数 $n,m$。意义如题所述。

接下来 $m$ 行，每行两个坐标 $(x_1,y_1)$ 和 $(x_2,y_2)$，代表一块地毯，左上角是 $(x_1,y_1)$，右下角是 $(x_2,y_2)$。

输出格式

输出 $n$ 行，每行 $n$ 个正整数。

第 $i$ 行第 $j$ 列的正整数表示 $(i,j)$ 这个格子被多少个地毯覆盖。

输入输出样例 #1

输入 #1

5 3
2 2 3 3
3 3 5 5
1 2 1 4

输出 #1

0 1 1 1 0
0 1 1 0 0
0 1 2 1 1
0 0 1 1 1
0 0 1 1 1

说明/提示

样例解释

覆盖第一个地毯后：

$0$$0$$0$$0$$0$
$0$$1$$1$$0$$0$
$0$$1$$1$$0$$0$
$0$$0$$0$$0$$0$
$0$$0$$0$$0$$0$

覆盖第一、二个地毯后：

$0$$0$$0$$0$$0$
$0$$1$$1$$0$$0$
$0$$1$$2$$1$$1$
$0$$0$$1$$1$$1$
$0$$0$$1$$1$$1$

覆盖所有地毯后：

$0$$1$$1$$1$$0$
$0$$1$$1$$0$$0$
$0$$1$$2$$1$$1$
$0$$0$$1$$1$$1$
$0$$0$$1$$1$$1$

数据范围

对于 $20\%$ 的数据，有 $n\le 50$，$m\le 100$。

对于 $100\%$ 的数据，有 $n,m\le 1000$。

我的代码(超时)

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

#define int long long
#define all(x) (x).begin(), (x).end()

int32_t main(){
    int n,m,x1,y1,x2,y2;
    cin >> n >> m;
    vector<vector<int>> matr (n,vector<int>(n,0));
    for (int i=0;i<m;i++){
        cin >> x1 >> y1 >> x2 >> y2;
        for (int y=y1-1;y<y2;y++){
            for (int x=x1-1;x<x2;x++){
                matr[x][y]+=1;
            }
        }
    }
    for (int j=0;j<n;j++){
        for (int k=0;k<n;k++){
            printf("%d ",matr[j][k]);
        }
        printf("\n");  
    }
    return 0;
}

题解代码

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

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

    int n, m;
    cin >> n >> m;
    vector<vector<long long>> diff(n+1, vector<long long>(n+1, 0LL));

    for(int i = 0; i < m; i++){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        diff[x1][y1] += 1;
        if(y2 + 1 <= n) diff[x1][y2 + 1] -= 1;
        if(x2 + 1 <= n) diff[x2 + 1][y1] -= 1;
        if(x2 + 1 <= n && y2 + 1 <= n) diff[x2 + 1][y2 + 1] += 1;
    }

    for(int x = 1; x <= n; x++){
        for(int y = 1; y <= n; y++){
            if(y > 1) diff[x][y] += diff[x][y - 1];
        }
    }

    for(int y = 1; y <= n; y++){
        for(int x = 1; x <= n; x++){
            if(x > 1) diff[x][y] += diff[x - 1][y];
        }
    }

    for(int x = 1; x <= n; x++){
        for(int y = 1; y <= n; y++){
            cout << diff[x][y];
            if(y < n) cout << " ";
        }
        cout << "\n";
    }

    return 0;
}

涉及到的知识(o4-mini)

这道题主要考察以下算法/技巧：

  1. 2D 差分（Imos）

    • 对每个矩形［x1,y1］–［x2,y2］，在差分矩阵 d 做四次标记：
      d[x1][y1] += 1
      d[x1][y2+1] –= 1
      d[x2+1][y1] –= 1
      d[x2+1][y2+1] += 1
    • 最后对差分矩阵做二维前缀和，得到每个格子的覆盖次数。

  2. 二维前缀和

    • 差分累加后，先对行方向做前缀和，再对列方向做前缀和（或反过来），即可恢复原始每点的累加值。

  3. 边界处理

    • 要注意 y2+1 或 x2+1 可能越界，应在矩阵尺寸上预留多 1 行／列，或在做差分时做边界判断。

  4. 时间复杂度分析

    • 差分标记花 O(m)，二维前缀和花 O(n²)，总体 O(n² + m)，当 n,m≤1000 时完全可接受。

3.纯纯的模拟

3.1.扫雷(挖坑，待填)

题目

题目背景
NOIP2015 普及组 T2
题目描述
扫雷游戏是一款十分经典的单机小游戏。在 $n$ 行 $m$ 列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。
现在给出 $n$ 行 $m$ 列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。
注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。
输入格式
第一行是用一个空格隔开的两个整数 $n$ 和 $m$，分别表示雷区的行数和列数。
接下来 $n$ 行，每行 $m$ 个字符，描述了雷区中的地雷分布情况。字符 $\texttt{*}$ 表示相应格子是地雷格，字符 $\texttt{?}$ 表示相应格子是非地雷格。相邻字符之间无分隔符。
输出格式
输出文件包含 $n$ 行，每行 $m$ 个字符，描述整个雷区。用 $\texttt{*}$ 表示地雷格，用周围的地雷个数表示非地雷格。相邻字符之间无分隔符。
输入输出样例 #1
输入 #1

3 3
*??
???
?*?

输出 #1

*10
221
1*1

输入输出样例 #2
输入 #2

2 3
?*?
*??

输出 #2

2*1
*21

说明/提示
对于 $100\%$的数据，$1≤n≤100, 1≤m≤100$。

我的代码(错误)

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

#define int long long
#define all(x) (x).begin(), (x).end()

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin >> n >> m;
    vector<vector<char>> mat (n,vector<char>(m,'?'));
    vector<vector<int>> nums (n,vector<int>(m,-1));
    for (int i=0;i<n;i++){
        string str;
        cin >> str;
        for (int j=0;j<m;j++){
            mat[i][j]=str[j];
        }
    }

    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            if (mat[i][j]=='*'){
                if (i-1>0 && mat[i-1][j]!='*'){
                    if (nums[i-1][j]<0){ nums[i-1][j]=1;}
                    else{ nums[i-1][j]++;}
                }if (i+1<n && mat[i+1][j]!='*'){
                    if (nums[i+1][j]<0){ nums[i+1][j]=1;}
                    else{ nums[i+1][j]++;}
                }if (j-1>0 && mat[i][j-1]!='*'){
                    if (nums[i][j-1]<0){ nums[i][j-1]=1;}
                    else{ nums[i][j-1]++;}
                }if (j+1<m && mat[i][j+1]!='*'){
                    if (nums[i][j+1]<0){ nums[i][j+1]=1;}
                    else{ nums[i][j+1]++;}
                }if (i-1>0 && j-1>0  && mat[i-1][j-1]!='*'){//左上角
                    if (nums[i-1][j-1]<0){ nums[i-1][j-1]=1;}
                    else{ nums[i-1][j-1]++;}
                }if (i+1<n && j+1<m && mat[i+1][j+1]!='*'){//右下角
                    if (nums[i+1][j+1]<0){ nums[i+1][j+1]=1;}
                    else{ nums[i+1][j+1]++;}
                }if (i+1<n && j-1<m && mat[i+1][j-1]!='*'){//左下角
                    if (nums[i+1][j-1]<0){ nums[i+1][j-1]=1;}
                    else{ nums[i+1][j-1]++;}
                }if (i-1<n && j+1<m && mat[i-1][j+1]!='*'){//右上角
                    if (nums[i-1][j+1]<0){ nums[i-1][j+1]=1;}
                    else {nums[i-1][j+1]++;}
                }
            }
        }
    }

    for (int i=0;i<n;i++){
        string temp="";
        for (int j=0;j<m;j++){
            if (nums[i][j]<0){
                temp+='*';
            }else{
                temp+=nums[i][j]+'0';
            }
        }
        cout << temp << "\n";
    }
    return 0;
}

题解代码

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

#define int long long
#define all(x) (x).begin(), (x).end()

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<char>> mat(n, vector<char>(m, '?'));
    vector<vector<int>> nums(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++){
        string str;
        cin >> str;
        for (int j = 0; j < m; j++){
            mat[i][j] = str[j];
        }
    }
  
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            if (mat[i][j] == '*'){
                // 上
                if (i - 1 >= 0 && mat[i-1][j] != '*'){
                    if (nums[i-1][j] < 0) { nums[i-1][j] = 1; }
                    else { nums[i-1][j]++; }
                }
                // 下
                if (i + 1 < n && mat[i+1][j] != '*'){
                    if (nums[i+1][j] < 0) { nums[i+1][j] = 1; }
                    else { nums[i+1][j]++; }
                }
                // 左
                if (j - 1 >= 0 && mat[i][j-1] != '*'){
                    if (nums[i][j-1] < 0) { nums[i][j-1] = 1; }
                    else { nums[i][j-1]++; }
                }
                // 右
                if (j + 1 < m && mat[i][j+1] != '*'){
                    if (nums[i][j+1] < 0) { nums[i][j+1] = 1; }
                    else { nums[i][j+1]++; }
                }
                // 左上角
                if (i - 1 >= 0 && j - 1 >= 0 && mat[i-1][j-1] != '*'){
                    if (nums[i-1][j-1] < 0) { nums[i-1][j-1] = 1; }
                    else { nums[i-1][j-1]++; }
                }
                // 右下角
                if (i + 1 < n && j + 1 < m && mat[i+1][j+1] != '*'){
                    if (nums[i+1][j+1] < 0) { nums[i+1][j+1] = 1; }
                    else { nums[i+1][j+1]++; }
                }
                // 左下角
                if (i + 1 < n && j - 1 >= 0 && mat[i+1][j-1] != '*'){
                    if (nums[i+1][j-1] < 0) { nums[i+1][j-1] = 1; }
                    else { nums[i+1][j-1]++; }
                }
                // 右上角
                if (i - 1 >= 0 && j + 1 < m && mat[i-1][j+1] != '*'){
                    if (nums[i-1][j+1] < 0) { nums[i-1][j+1] = 1; }
                    else { nums[i-1][j+1]++; }
                }
            }
        }
    }
  
    // 输出结果，用 m 控制内层循环
    for (int i = 0; i < n; i++){
        string temp = "";
        for (int j = 0; j < m; j++){
            if (mat[i][j]=='*'){
                temp.push_back('*');
            } else {
                temp.push_back(nums[i][j] + '0');
            }
        }
        cout << temp << "\n";
    }
    return 0;
}

涉及到的知识

这道题主要考察以下基础算法/技巧：

  1. 二维数组遍历
    – 将输入的 n×m 格子存为二维数组，依次访问每个格子。
  2. 枚举八个方向
    – 对于每个非雷格子，枚举它周围 8 个邻居（上下左右及四个对角线），统计其中的雷数。
    – 常用 dx、dy 两个长度为 8 的方向数组来简化代码。
  3. 边界检查
    – 在访问邻居时判断下标是否越界，确保 1≤x≤n、1≤y≤m。
  4. 模拟实现
    – 对于雷格（‘’）直接输出‘’，否则输出统计到的数字字符。
    – 时间复杂度 O(n·m·8)=O(nm)，在 n,m≤100 范围内非常轻松。

总体上就是对二维网格做简单的模拟与邻居枚举，边界条件和数组下标处理是实现的重点。

最后修改：2025 年 05 月 08 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏