搜索
简帛阁>技术文章>AcWing 蓝桥杯专题训练 :(一)递归与递推 习题

AcWing 蓝桥杯专题训练 :(一)递归与递推 习题

AcWing 蓝桥杯专题训练 :(一)递归与递推习题

AcWing账号ID:田所浩二

注:可能会和y总的代码有不一样的地方

  1. 递归实现组合型枚举(掌握)
    这道题实际上是94题的升级版,其不同之处在于是从n个数中抽取m个并且需要不重复(答案组中任意两组数的组成情况都不一样,例如 1 2 3 和 2 1 3就是重复的)
    解决第一个不同在于u枚举到m的时候就返回(从n中抽取m个),枚举的时的范围为1-n 和94题一样我们选了这个数就标记并注意递归还原。但是我们如何解决 2 1 3 和 1 2 3相同?这时我们新增一个参数start 表示下一层递归开始的数均在上一层后面即dfs(u+1,i+1);其中的i+1,这同样也说明我们最后得到的答案中数组都只能是递增的。
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
vector<int> path;
bool st[N];
int n,m;

void dfs(int u,int start)
{<!-- -->
    if(u == m)
    {<!-- -->
        for(int i=0;i<path.size();i++)
        {<!-- -->
            cout<<path[i]<<" ";
        }
        cout<<endl;
        return ;
    }
    for(int i=start;i<=n;i++)
    {<!-- -->
        if(!st[i])
        {<!-- -->
            path.push_back(i);
            st[i]=true;
            dfs(u+1,i+1);
            st[i]=false;
            path.pop_back();
        }
    }
}
int main()
{<!-- -->
    cin>>n>>m;
    dfs(0,1);
    return 0;
}
  1. 带分数(掌握)
    首先我们将这个带分数分为 n=a+b/c
    这道题我们可以利用之前的第94道题,先将1-9 进行不同的排列(题目要求1-9都得用上)将结果储存在st数组中。之后我们开始对st数组进行划分:
    这三层循环分别代表了a,b,c这三个数。
    第一层循环范围为数组下标第0位到第7位,我们枚举第一个数a的长度(注意这里i最多到7也就是总共8位,最后一位留给第二层循环)那么第一个数a在数组里的范围为[0,i];
    第二层循环我们从第一层循环的下一位开始,同样的第二个数b在数组里的范围我们枚举j得到[i+1,j];(i是上一个数的结尾)
    剪枝的地方:我们已经有了前两段数了,第三个数c不用循环在st里的范围自然就是[j+1,8];(总共8个数)
    那么我们在开一个函数去将数组里的数按位相加分别得出a,b,c。最后通过a+b/c算出结果与我们最后的答案比较是否相等即可。
#include<bits/stdc++.h>
using namespace std;
const int N=10;
int used[N];
int st[N];
int n;
int cnt=0;
bool check(int a,int b,int c)
{<!-- -->
    return (a+(b/c)==n)&&(b%c==0);
}
int cal(int l,int r)
{<!-- -->
    int res=0;
    for(int i=l;i<=r;i++)
    {<!-- -->
        res=res*10+st[i];//这就相当于数位每乘以一个10就会往后加一个
    }
    return res;
}
void dfs(int u)
{<!-- -->
    if(u>8)
    {<!-- -->
        for(int i=0;i<8;i++)
        {<!-- -->
            for(int j=i+1;j<8;j++)//这里如果i=7那么下面自动到i=8最后一个数位
            {<!-- -->
                int a=cal(0,i);//通过改变端点值来控制位数的不同
                int b=cal(i+1,j);//及控制前面的整数和分数不同
                int c=cal(j+1,8);
                if(check(a,b,c))
                {<!-- -->
                    cnt++;
                }
            }
        }
        return ;
    }
    for(int i=1;i<=9;i++)//将1-9以不同的顺序存入数组当中
    {<!-- -->
        if(!used[i])
        {<!-- -->
            used[i]=1;
            st[u]=i;
            dfs(u+1);
            used[i]=0;
            st[u]=0;
        }
    }
}
int main()
{<!-- -->
    cin>>n;
    dfs(0);
    cout<<cnt<<endl;
    return 0;
}


  1. 飞行员兄弟(了解)
    题中如果存在多种打开冰箱的方式,则按照优先级整体从上到下,同行从左到右打开。
    我们只需要枚举这个16位的二进制数,就可以确定我们的方案,因为题目只需要最优解方案,所以我们通过每次递归改变把手的状态最后判断是否全亮即可,然后在比较全量的方案中谁是最优解即可。
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 5;
char g[N][N], backup[N][N];
int get(int x, int y)
{<!-- -->
    return x * 4 + y;
}
void turn_one(int x, int y)
{<!-- -->
    if (g[x][y] == '+') g[x][y] = '-';
    else g[x][y] = '+';
}
void turn_all(int x, int y)
{<!-- -->
    for (int i = 0; i < 4; i ++ )
    {<!-- -->
        turn_one(x, i);
        turn_one(i, y);
    }
    turn_one(x, y);
}
int main()
{<!-- -->
    for (int i = 0; i < 4; i ++ ) cin >> g[i];

    vector<PII> res;
    for (int op = 0; op < 1 << 16; op ++ )
    {<!-- -->
        vector<PII> temp;
        memcpy(backup, g, sizeof g);        // 备份

        // 进行操作
        for (int i = 0; i < 4; i ++ )
            for (int j = 0; j < 4; j ++ )
                if (op >> get(i, j) & 1)
                {<!-- -->
                    temp.push_back({<!-- -->i, j});
                    turn_all(i, j);
                }

        // 判断所有灯泡是否全亮
        bool has_closed = false;
        for (int i = 0; i < 4; i ++ )
            for (int j = 0; j < 4; j ++ )
                if (g[i][j] == '+')
                    has_closed = true;

        if (has_closed == false)
        {<!-- -->
            if (res.empty() || res.size() > temp.size()) res = temp;
        }

        memcpy(g, backup, sizeof g);        // 还原
    }

    cout << res.size() << endl;
    for(int i=0;i<res.size();i++)
	{<!-- -->
    	cout<<res[i].x+1<<" "<<res[i].y+1<<endl;
	}	

    return 0;
}

  1. 翻硬币 (掌握)
    将s1和s2进行比较,这里我们统一选择s2进行反转,通过对这两个字符串每一位进行比较,如果出现了不同的情况就将s2反转成和s1相同的图案即可。
#include<bits/stdc++.h>
using namespace std;
char s1[1100],s2[1100];
int cnt;
int main()
{<!-- -->
    cin>>s1>>s2;
    int n1=strlen(s1);
    int n2=strlen(s2);
    for(int i=0;i<=n1-1;i++)
    {<!-- -->
        if(s1[i]!=s2[i])
        {<!-- -->
            if(s2[i]=='o')
            {<!-- -->
                s2[i]='*';
            }
            else if(s2[i]=='*')
            {<!-- -->
                s2[i]='o';
            }
            if(s2[i+1]=='o')
            {<!-- -->
                s2[i+1]='*';
            }
            else if(s2[i+1]=='*')
            {<!-- -->
                s2[i+1]='o';
            }
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}


AcWing蓝桥杯专题训练:(递归习题AcWing账号ID:田所浩二注:可能会和y总的代码有不一样的地方递归实现组合型枚举(掌握这道题实际上是94题的升级版,其不同之处在于是从n个数中抽取
AcWing蓝桥杯专题训练:(递归例题AcWing账号ID:田所浩二注:可能会和y总的代码有不一样的地方递归实现指数型枚举(掌握从1~n这n个整数中随机选取任意多个,而且题目最后要求我们以
AcWing蓝桥杯专题训练:(二分前缀和例题AcWing账号ID:田所浩二注:可能会和y总的代码有不一样的地方写在前面:y总的二分模板分为两类:其一是类似于“分巧克力”中的求最大值,其二类似于
费解的开关你玩过“拉灯”游戏吗?25盏灯排成一个5x5的方形。每一个灯都有一个开关,游戏者可以改变它的状态。每一步,游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应:和这个灯上下左右
带分数题意简单dfs枚举全19的全排列,for循环出a,b,c,判断结果,是的话res++pragmacomment(linker,/STACK:1024000000,1024000000)inclu
目录AcWing92递归实现指数型枚举AcWing93递归实现组合型枚举AcWing94递归实现排列型枚举AcWing1209带分数AcWing1208翻硬币AcWing92递归实现指数型枚举从1~
AcWing92递归实现指数型枚举从1~n这n个整数中随机选取任意多个,输出所有可能的选择方案。输入格式输入一个整数n。输出格式每行输出一种方案。同一行内的数必须升序排列,相邻两个数用恰好1个空格隔开
蓝桥杯C++AB组辅导课例题92递归实现指数型枚举AC代码:include<iostream>include<cstring>include<cstdio>incl
例题AcWing92递归实现指数型枚举从1∼n这n个整数中随机选取任意多个,输出所有可能的选择方案。输入格式输入一个整数n。输出格式每行输出一种方案。同一行内的数必须升序排列,相邻两个数用恰好1个空格
乘积数量题目链接标题字数完全不够用啊!!!给定一个长度为n且不包含0的整数序列a1,a2,…,an。请你计算以下两值:使得al×al+1×…×ar为负的索引对(l,r)(l≤r)的数量。使得al×al