专题五 搜索

2025ACM寒假集训

专题五 搜索

102400226 石华波

Vjudge账号:DustLi

问题一 自然数的拆分问题

问题陈述

任何一个大于 1 的自然数 n，总可以拆分成若干个小于 n 的自然数之和。现在给你一个自然数 n，要求你求出 n 的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。

解题思路

DFS。

AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include<iostream>

using namespace std;

using ll = long long;

int Pr[11]={1};
int N;

void Print(int M) {
    for(int i=1;i<M;i++) cout<<Pr[i]<<'+';
    if(M!=1) cout<<Pr[M]<<endl;
}

void DFS(int T) {
    for(int i=Pr[T-1];i<=N;i++) {
        Pr[T]=i;
        N-=i;
        if(N==0) Print(T);
        else DFS(T+1);
        N+=i;
    }
}

int main() {
    cin>>N;
    DFS(1);
    return 0;
}

问题二 填涂颜色

问题陈述

由数字 0 组成的方阵中，有一任意形状的由数字 1 构成的闭合圈。现要求把闭合圈内的所有空间都填写成 2。例如：6×6 的方阵（n=6），涂色前和涂色后的方阵如下：

如果从某个 0 出发，只向上下左右 4 个方向移动且仅经过其他 0 的情况下，无法到达方阵的边界，就认为这个 0 在闭合圈内。闭合圈不一定是环形的，可以是任意形状，但保证闭合圈内的 0 是连通的（两两之间可以相互到达）。

解题思路

”寻找闭合圈中的0“是一个比较难的操作，不妨转化为”寻找与边界联通的0并标记“。

另外，可以先将所有的0染为2，然后将与边界联通的2染回0。

以Dir数组存储转向数对,BFS。

AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include<iostream>
#include <queue>

using namespace std;

using ll = long long;

int Mar[31][31];
int Dir[5][5]={{0,0},{0,1},{0,-1},{-1,0},{1,0}};
queue<pair<int,int>> Pos;

int main() {
    int N;
    cin>>N;
    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) cin>>Mar[i][j];
    for(int i=0;i<=N+1;i++) for(int j=0;j<=N+1;j++) if(Mar[i][j]==0) Mar[i][j]=2;
    Pos.push(make_pair(0,0));
    while(!Pos.empty()) {
        int x=Pos.front().first;
        int y=Pos.front().second;
        Pos.pop();
        Mar[x][y]=0;
        for(int i=1;i<=4;i++) if(Mar[x+Dir[i][0]][y+Dir[i][1]]==2) Pos.push(make_pair(x+Dir[i][0],y+Dir[i][1]));
    }
    for(int i=1;i<=N;i++) {
        for(int j=1;j<=N;j++) {
            cout<<Mar[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

问题三 素数密度

问题陈述

古老的显示屏是由 N×M 个像素（Pixel）点组成的。一个像素点的位置是根据所在行数和列数决定的。例如 P(2,1) 表示第 2 行第 1 列的像素点。那时候，屏幕只能显示黑与白两种颜色，人们用二进制 0 和 1 来表示。0 表示黑色，1 表示白色。当计算机发出一个指令：P(x,y)=1，则屏幕上的第 x 行第 y 列的阴极射线管就开始工作，使该像素点显示白色，若 P(x,y)=0，则对应位置的阴极射线管不工作，像素点保持黑色。在某一单位时刻，计算机以 N×M 二维 01 矩阵的方式发出显示整个屏幕图像的命令。

例如，屏幕是由 3×4 的像素点组成，在某单位时刻，计算机发出如下命令：

000001011110

对应屏幕显示应为：

img

假设放大后，一个格子表示一个像素点。

由于未知的原因，显示黑色的像素点总是受显示白色的像素点的影响——可能是阴极射线管工作的作用。并且，距离越近，影响越大。这里的距离定义如下：

设有像素点 P1(x1,y1) 和像素点 P2(x2,y2)，则它们之间的距离 D(P1,P2)=∣x1−x2∣+∣y1−y2∣。

在某一时刻，计算机发出显示命令后，科学家们期望知道，每个像素点和其最近的显示白色的像素点之间的最短距离是多少——科学家们保证屏幕上至少有一个显示白色的像素点。

上面的例子中，像素 P(1,1) 与最近的白色像素点之间的距离为 3，而像素 P(3,2) 本身显示白色，所以最短距离为 0。

解题思路

BFS，对每个黑块处理来找到距离最近的白块操作次数太多，易TLE，不妨从白块出发，依次找到距离最近的白块的距离为1、2…的黑块。注意检查坐标是否合法。

AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include<iostream>
#include <queue>
#include <string.h>

using namespace std;

using ll = long long;

int N,M;
int Mar[190][190];
int Dis[190][190];
bool Vis[190][190];
int Dir[5][5]={{0,0},{0,1},{0,-1},{-1,0},{1,0}};
queue<pair<int,int> > Pos;

bool Ava(int x,int y) {
    return x>=1&&x<=N&&y>=1&&y<=M;
}

int main() {

    cin>>N>>M;
    char c;
    for(int i=1;i<=N;i++) {
        for(int j=1;j<=M;j++) {
            cin>>c;
            Mar[i][j]=c-'0';
            if(Mar[i][j]==1) {
                Dis[i][j]=0;
                Vis[i][j]=true;
                Pos.push(make_pair(i,j));
            }
        }
    }
    while(!Pos.empty()) {
        int x=Pos.front().first;
        int y=Pos.front().second;
        Pos.pop();
        for(int i=1;i<=4;i++) {
            int xi=x+Dir[i][0];
            int yi=y+Dir[i][1];
            if(Ava(xi,yi)&&!Vis[xi][yi]) {
                Pos.push(make_pair(xi,yi));
                Vis[xi][yi]=true;
                Dis[xi][yi]=Dis[x][y]+1;
            }
        }
    }
    for(int i=1;i<=N;i++) {
        for(int j=1;j<=M;j++) cout<<Dis[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

问题4 健康的荷斯坦奶牛

问题陈述

农民 John 以拥有世界上最健康的奶牛为傲。他知道每种饲料中所包含的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛，以保持它们的健康，使喂给牛的饲料的种数最少。

给出牛所需的最低的维他命量，输出喂给牛需要哪些种类的饲料，且所需的饲料剂量最少。

维他命量以整数表示，每种饲料最多只能对牛使用一次，数据保证存在解。

解题思路

DFS，数目未知选用Vector容器。

其中：

if (!Ans.empty() && Cho.size() >= Ans.size()) return;

用于剪枝，防止数据量过大超时。

AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include<iostream>
#include <queue>

using namespace std;

using ll = long long;

int V,G;
int VatN[26];
int VatS[16][26];
vector<int> Cho;
vector<int> Ans;

bool Check() {
    for(int i=1;i<=V;i++) {
        int Sum=0;
        for(auto j:Cho) Sum+=VatS[j][i];
        if(Sum<VatN[i]) return false;
    }
    return true;
}

void DFS(int x) {
    if (!Ans.empty() && Cho.size() >= Ans.size()) return;
    if(x>G) {
        if(Check()&&(Ans.empty()||Cho.size()<Ans.size())) Ans=Cho;
        return;
    }
    Cho.push_back(x);
    DFS(x+1);
    Cho.pop_back();
    DFS(x+1);
}


int main() {
    cin>>V;
    for(int i=1;i<=V;i++) cin>>VatN[i];
    cin>>G;
    for(int i=1;i<=G;i++) for(int j=1;j<=V;j++) cin>>VatS[i][j];
    DFS(1);
    cout<<Ans.size()<<' ';
    for(auto i:Ans) cout<<i<<' ';
    return 0;
}

问题五 GRZ-Ridges and Valleys

问题陈述

给定一个 n×n 的网格状地图，每个方格 (i,j) 有一个高度 w**ij。如果两个方格有公共顶点，则它们是相邻的。

定义山峰和山谷如下：

  • 均由地图上的一个连通块组成；
  • 所有方格高度都相同；
  • 周围的方格（即不属于山峰或山谷但与山峰或山谷相邻的格子）高度均大于山谷的高度，或小于山峰的高度。

求地图内山峰和山谷的数量。特别地，如果整个地图方格的高度均相同，则整个地图既是一个山谷，也是一个山峰。

解题思路

BFS，八联通，注意Dir中应有八个方向。

处理BFS时，将与目前元素高度相等的元素加入队列，并标记已访问，对于与当前元素高度不同的元素，若当前元素较大，则当前联通块不可能为山谷，反之，则当前联通块不可能为山峰。最后计数输出。

AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include<iostream>
#include <queue>

using namespace std;

using ll = long long;

int N;
int CntP,CntV;
int Dir[9][9]={{0,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0}};
int Mar[1001][1001];
bool Vis[1001][1001];
queue<pair<int, int>> Pos;

bool Ava(int i,int j) {
    return i>=1&&j>=1&&i<=N&&j<=N;
}
void BFS() {
    bool isPeak=true;
    bool isValley=true;
    while(!Pos.empty()) {
        int x=Pos.front().first;
        int y=Pos.front().second;
        Pos.pop();
        for(int i=1;i<=8;i++) {
            int xi=x+Dir[i][0];
            int yi=y+Dir[i][1];
            if(Ava(xi,yi)) {
                if(Mar[xi][yi]==Mar[x][y]&&!Vis[xi][yi]) {
                    Pos.push(make_pair(xi,yi));
                    Vis[xi][yi]=true;
                }
                if(Mar[xi][yi]>Mar[x][y]) isPeak=false;
                if(Mar[xi][yi]<Mar[x][y]) isValley=false;
            }
        }
    }
    if(isPeak) CntP++;
    if(isValley) CntV++;
}

int main() {
    cin>>N;
    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) cin>>Mar[i][j];
    for(int i=1;i<=N;i++) {
        for(int j=1;j<=N;j++) {
            if(!Vis[i][j]) {
                Pos.push(make_pair(i,j));
                BFS();
            }
        }
    }
    cout<<CntP<<" "<<CntV<<endl;
    return 0;
}

问题六 DFS

问题陈述

  • 一个如下的 6×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

    img

    上面的布局可以用序列 2 4 6 1 3 5 来描述，第 i 个数字表示在第 i 行的相应位置有一个棋子，如下：

    行号 1 2 3 4 5 6

    列号 2 4 6 1 3 5

    这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。 并把它们以上面的序列方法输出，解按字典顺序排列。 请输出前 3 个解。最后一行是解的总个数。

解题思路

DFS，同一条主对角线上的元素横纵坐标之和相等，同一条副对角线上的元素横纵坐标之差相等，故两个一维数组即可存储对角线的占用状态，再开两个一维数组用于存储列的占用状态和当前方案。

Cnt<=3时输出本次方案，最后输出总方案数。

AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include<iostream>
#include <queue>

using namespace std;

using ll = long long;

int N;
int Cnt;
bool MDia[27];
bool SDia[27];
bool Col[27];
int Ans[14];

void DFS(int x) {
    if(x>N) {
        Cnt++;
        if(Cnt<=3) {
            for(int i=1;i<=N;i++) cout<<Ans[i]<<" ";
            cout<<endl;
        }
        return;
    }
    for(int i=1;i<=N;i++) {
        if(!(Col[i]||MDia[x+i]||SDia[x-i+N])) {
            Ans[x]=i;
            Col[i]=true;
            MDia[x+i]=true;
            SDia[x-i+N]=true;
            DFS(x+1);
            Col[i]=false;
            MDia[x+i]=false;
            SDia[x-i+N]=false;
        }
    }
}

int main() {
    cin>>N;
    DFS(1);
    cout<<Cnt<<endl;
    return 0;
}

学习总结

本专题内容主要为搜索，通过学习，提高了自己的能力。

Licensed under CC BY-NC-SA 4.0
© 2025 - 2026 Dust_Li
2025寒假ACM新生线上集训
使用 Hugo 构建
主题 Stack 由 Jimmy 设计