算法竞赛基础：递推、递归、搜索与高精度 | 极客日志

C++算法

算法竞赛基础：递推、递归、搜索与高精度

本文总结了算法竞赛中的核心知识点，包括递推与递归的思想及代码实现、广度优先搜索（BFS）与深度优先搜索（DFS）的基础模板及应用、迷宫问题的解法以及高精度整数运算。内容涵盖状态转移方程、终止条件寻找、图遍历模板及数组模拟计算等关键技巧，适合初学者入门学习。

虚拟内存发布于 2026/3/30更新于 2026/4/131 浏览

算法竞赛基础：递推、递归、搜索与高精度

递推和递归

递推

先简单介绍一下

递推算法：自底向上，由已知条件推导出位置结果的一种算法。

核心：状态转移（边界 + 关系式）

废话不多说，直接从题目入手理解递推思想。

选用信息学奥赛一本通的题：卒过河问题。

题目意思理解：

从 A 点到 B 点的路径数，并且经过马能到达的点都无效，我们先做好前期的工作准备。

// 马走日，移动的位置（马能到达的点）
int mx[] = {-1,-1,-2,-2,1,1,2,2};
int my[] = {-2,2,-1,1,-2,2,-1,1};
int vis[110][110]={0};//标记数组
int rd[110][110]={0};//记录每个点的路径数

//将马能到达的位置全标记成 1
for(int i=0;i<=7;i++) {
    int nx=cx+mx[i];
    int ny=cy+my[i];
    if(nx<0 || ny<0 || nx>n || ny>m)continue;
    vis[nx][ny]=1;
}
//别忘了把马的初始位置也标记成 1
vis[cx][cy]=1;

然后我们准备初始化边界，满足

//起点置为一
rd[0][]=;

( i=;i<=n;i++) {
    rd[i][]=rd[i][];
    (vis[i][]==)rd[i][]=;
}
( i=;i<=m;i++) {
    rd[][i]=rd[][i];
    (vis[][i]==)rd[][i]=;
}

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown 转 HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。在线工具，Markdown 转 HTML在线工具，online
HTML 转 Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML 转 Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

for(int i=1;i<=n;i++) {
    for(int j=1;j<=m;j++) {
        //注意：马能到达的标记处 卒无法通过
        if(vis[i][j]==1)continue;
        rd[i][j]=rd[i-1][j]+rd[i][j-1];
    }
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
int mx[] = {-1,-1,-2,-2,1,1,2,2};
int my[] = {-2,2,-1,1,-2,2,-1,1};
int vis[110][110]={0};
int rd[110][110]={0};
signed main(){
    int n,m,cx,cy;
    cin>>n>>m>>cx>>cy;
    vis[cx][cy]=1;
    for(int i=0;i<=7;i++){
        int nx=cx+mx[i];
        int ny=cy+my[i];
        if(nx<0 || ny<0 || nx>n || ny>m)continue;
        vis[nx][ny]=1;
    }
    rd[0][0]=1;
    for(int i=1;i<=n;i++){
        rd[i][0]=rd[i-1][0];
        if(vis[i][0]==1)rd[i][0]=0;
    }
    for(int i=1;i<=m;i++){
        rd[0][i]=rd[0][i-1];
        if(vis[0][i]==1)rd[0][i]=0;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(vis[i][j]==1)continue;
            rd[i][j]=rd[i-1][j]+rd[i][j-1];
        }
    }
    cout<<rd[n][m]<<endl;
    return 0;
}

int fb(int x){
    if(x==1 || x==2)return 1;
    return fb(x-1)+fb(x-2);
}

#include<bits/stdc++.h>
using namespace std;
int fb(int x){
    if(x==1 || x==2)return 1;
    return fb(x-1)+fb(x-2);
}
int main(){
    int n;//测试数据的组数
    cin>>n;
    while(n--){
        int num;
        cin>>num;
        cout<<fb(num)<<endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
int i=0;//用于找寻字符串中的每个字符
string s;
int Longest(){
    int m_cnt=0;//当前组字符串最大长度
    int cnt=0;//当前字符串长度
    while(i < s.size()){
        //遇见'( ' ,标志着新的一组的开始
        if(s[i] == '('){
            i++;
            //递归调用，算出新组的最长字符串长度
            int n = Longest();
            cnt += n;
        } else if(s[i] == 'x'){
            //普通字符长度正常 +1
            cnt++;
            i++;
        } else if(s[i] == '|'){
            //遇到分界线，就要比较左边界和右边界的大小了
            //这里属于先记录下左边界的大小
            //再将 cnt 清零记录右边界的大小
            m_cnt = max(m_cnt,cnt);
            cnt=0;
            i++;
        } else {//遇见') ' ,标志着这一组的结束
            i++;
            break;
        }
    }
    return max(cnt,m_cnt);//组外可能存在普通的 x，别忘了加上
}
int main(){
    cin>>s;
    cout<<Longest();
}

#include<bits/stdc++.h>
using namespace std;
int g[105][105];//建立邻接矩阵
int vis[105];
int n,m;
void bfs(int start){
    //建立队列
    queue<int> q;
    q.push(start);
    vis[start] = 1;
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        //选定 cur 作为当前节点
        //我们要找 cur 能够直接抵达哪些点
        //i 本质是在找下一个去哪
        for(int i=1;i<=n;i++){
            if(g[cur][i] == 1 && vis[i] == 0){//点 cur 和点 i 有通路，并且没有被标记过
                vis[i] = 1;
                //把 i 点标记上
                q.push(i);
            }
        }
    }
}
int main(){
    cin >> n >> m;
    //无向图，没有边权
    //若为有向图，就只存 u 点->v 点一个通路就行
    for(int i=1;i<=m;i++){
        int u,v;
        cin >> u >> v;
        //u,v 之间有通路，都给标记成 1
        g[u][v] = 1;
        g[v][u] = 1;
    }
    bfs(1);//遍历从 1 出发能到达的所有节点
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
vector<int> adj[105]; //创建动态数组 adj[i],在 adj[i] 中存储 i 能到达的所有点
int vis[105];
int n,m;
void bfs(int start){
    queue<int> q;
    q.push(start);
    vis[start] = 1;
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        //选定 cur 作为当前节点
        //我们要找 cur 能够直接抵达哪些点
        for(int i=0;i<adj[cur].size();i++){
            int nxt = adj[cur][i];
            if(vis[nxt] == 0){
                vis[nxt] = 1;
                q.push(nxt);
            }
        }
    }
}
int main(){
    cin >> n >> m;
    //无向图，没有边权
    for(int i=1;i<=m;i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    bfs(1);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
vector<int> adj[105];
int vis[105];
int n,m;
int a,b;
struct node{
    int id;
    int step;
};
void bfs(int start){
    queue<node> q;
    node tmp;//表示初始节点
    tmp.id = start;
    tmp.step = 0;
    q.push(tmp);
    vis[start] = 1;
    //开始 BFS
    while(!q.empty()){
        //队首节点的编号
        int curId = q.front().id;
        //起点到队首节点的步数
        int curStep = q.front().step;
        q.pop();
        for(int i=0;i<adj[curId].size();i++){
            //构造下一个节点
            node nxt;
            nxt.id = adj[curId][i];//下一步去哪的编号
            nxt.step = curStep + 1;// 去下个位置的步数 等于 当前步数 +1
            //如果下一个节点就是 b，那么直接输出答案就可以了
            if(nxt.id == b){
                cout << nxt.step << endl;
                return;
            }
            if(vis[nxt.id] == 0){//判断这个点去没去过
                vis[nxt.id] = 1;
                q.push(nxt);
            }
        }
    }
}
int main(){
    cin >> n >> m;//无向图有 n 个点，m 条边
    //无向图，没有边权 (看成是 1)
    for(int i=1;i<=m;i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cin >> a >> b;
    bfs(a);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1000;
int a[N][N];
int vis[N];//标记数组，初始为 0，用来标记这个点是否访问过
void dfs(int cur){
    vis[cur]=1;//标记当前点
    //寻找下一个点去哪
    for(int i=1;i<=n;i++){
        //cur 和 i 之间必须有边，并且 i 点没有访问过
        if(a[cur][i]==1 && vis[i]==0){
            dfs(i);//回溯找下一个点
        }
    }
}
int main(){
    cin >> n >> m;//无向图有 n 个点，m 条边
    //无向图，没有边权 (看成是 1)
    for(int i=1;i<=m;i++){
        int u,v;
        cin >> u >> v;
        a[u][v]=1;
        a[v][u]=1;
    }
    dfs(1);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1000;
vector<int>a[N];
int vis[N];//标记数组，初始为 0，用来标记这个点是否访问过
void dfs(int cur){
    vis[cur]=1;//标记当前点
    //寻找下一个点去哪
    for(int i=0;i<a[cur].size();i++){
        //a[cur]数组里存储的已经是和它有通路的点了
        int nxt=a[cur][i];
        if(vis[nxt]==0){
            dfs(nxt);//回溯找下一个点
        }
    }
}
int main(){
    cin >> n >> m;//无向图有 n 个点，m 条边
    //无向图，没有边权 (看成是 1)
    for(int i=1;i<=m;i++){
        int u,v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    dfs(1);
    return 0;
}

int n;//迷宫规模
char maze[110][110];//记录迷宫
int vis[110][110];//标记数组
int xA,yA,xB,yB; 
//控制上下左右移动的方向数组
int nx[]={-1,0,0,1};
int ny[]={0,-1,1,0};
int k;//测试的组数
cin>>k;
while(k--){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            char c;
            cin>>c;
            maze[i][j]=c;//创建迷宫
            vis[i][j]=0;
        }
    }

bool dfs(int sx,int sy){
    int cur_x=sx;
    int cur_y=sy;
    vis[cur_x][cur_y]=1;//把当前搜索点标记出来
    if(cur_x == xB && cur_y == yB)return true;//返回终点值
    for(int i=0;i<4;i++){
        //记录搜寻的上下左右点的位置
        int nxt_x=cur_x+nx[i];
        int nxt_y=cur_y+ny[i];
        //进行判断
        if(judge(nxt_x,nxt_y) && vis[nxt_x][nxt_y]==0){
            //接收 dfs 的返回值
            if(dfs(nxt_x,nxt_y))return true;
        }
    }
    return false;
}

bool judge(int x,int y){
    if(x<0 || y<0 || x>=n || y>=n)return false;
    if(maze[x][y]=='.')return true;
    else return false;
}

#include<bits/stdc++.h>
using namespace std;
int n;//迷宫规模
char maze[110][110];//记录迷宫
int vis[110][110];//标记数组
int xA,yA,xB,yB;
//控制上下左右移动的方向数组
int nx[]={-1,0,0,1};
int ny[]={0,-1,1,0};
bool judge(int x,int y){
    if(x<0 || y<0 || x>=n || y>=n)return false;
    if(maze[x][y]=='.')return true;
    else return false;
}
bool dfs(int sx,int sy){
    int cur_x=sx;
    int cur_y=sy;
    vis[cur_x][cur_y]=1;//把当前搜索点标记出来
    if(cur_x == xB && cur_y == yB)return true;//返回终点值
    for(int i=0;i<4;i++){
        //记录搜寻的上下左右点的位置
        int nxt_x=cur_x+nx[i];
        int nxt_y=cur_y+ny[i];
        //进行判断
        if(judge(nxt_x,nxt_y) && vis[nxt_x][nxt_y]==0){
            //接收 dfs 的返回值
            if(dfs(nxt_x,nxt_y))return true;
        }
    }
    return false;
}
int main(){
    int k;//测试的组数
    cin>>k;
    while(k--){
        cin>>n;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                char c;
                cin>>c;
                maze[i][j]=c;//创建迷宫
                vis[i][j]=0;
            }
        }
        cin>>xA>>yA>>xB>>yB;
        bool ans=dfs(xA,yA);
        if(ans)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

#include<iostream>
#include<queue>
using namespace std;
int n;//迷宫规模
char maze[110][110];//记录迷宫
int vis[110][110];//标记数组
int xA, yA, xB, yB;
//控制上下左右移动的方向数组
int nx[] = {-1, 0, 0, 1};
int ny[] = {0, -1, 1, 0};
bool judge(int x, int y) {
    if (x < 0 || y < 0 || x >= n || y >= n) return false;
    if (maze[x][y] == '.') return true;
    else return false;
}
void bfs(int sx, int sy) {
    queue<pair<int, int>> q;
    q.push({sx, sy});
    vis[sx][sy] = 1;
    while (!q.empty()) {
        int cur_x = q.front().first;
        int cur_y = q.front().second;
        q.pop();
        if (cur_x == xB && cur_y == yB) {
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nxt_x = cur_x + nx[i];
            int nxt_y = cur_y + ny[i];
            if (judge(nxt_x, nxt_y) && vis[nxt_x][nxt_y] == 0) {
                q.push({nxt_x, nxt_y});
                vis[nxt_x][nxt_y] = 1;
            }
        }
    }
}
int main() {
    int k;//测试的组数
    cin >> k;
    while (k--) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                char c;
                cin >> c;
                maze[i][j] = c;//创建迷宫
                vis[i][j] = 0;
            }
        }
        cin >> xA >> yA >> xB >> yB;
        bfs(xA, yA);
        if (vis[xB][yB]) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

#include<iostream>
#include<string>
using namespace std;
int a[110];
int b[110];
int c[110];
int main() {
    //输入两个大整数（在定义时就直接把他们变成字符串类型）
    string s1, s2;
    cin >> s1 >> s2;
    int k = 1, m = 1;
    for (int i = s1.size() - 1; i >= 0; i--) {
        a[k++] = s1[i] - '0';//将数字倒序存储在数组中
    }
    for (int i = s2.size() - 1; i >= 0; i--) {
        b[m++] = s2[i] - '0';
    }
    int lmax = max(s1.size(), s2.size());//确认相加后的数字长度
    for (int j = 1; j <= lmax; j++) {
        c[j] += a[j] + b[j];
        c[j + 1] += c[j] / 10;//进位
        c[j] %= 10;
    }
    for (int i = lmax + 1; i >= 1; i--) {
        if (i == lmax + 1 && c[i] == 0)continue;//去除前导零
        else cout << c[i];
    }
    return 0;
}