蓝桥杯真题Day48 倒计时7天 练了几道真题小程序+回溯剪枝应用一个小程序

2024-04-09 03:28

本文主要是介绍蓝桥杯真题Day48 倒计时7天 练了几道真题小程序+回溯剪枝应用一个小程序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

[蓝桥杯 2023 省 A] 更小的数

题目描述

59d62eeb159e48f189b63a772dc05b28.png

小蓝有一个长度均为 n 且仅由数字字符 0∼9 组成的字符串,下标从0到 n−1,你可以将其视作是一个具有n位的十进制数字num,小蓝可以从num 中选出一段连续的子串并将子串进行反转,最多反转一次

小蓝想要将选出的子串进行反转后再放入原位置处得到的新的数字num(new)​ 满足条件num(new)​<num,请你帮他计算下一共有多少种不同的子串选择方案,只要两个子串在 num 中的位置不完全相同我们就视作是不同的方案。

注意,我们允许前导零的存在,即数字的最高位可以是0,这是合法的。

输入格式

输入一行包含一个长度为n 的字符串表示num(仅包含数字字符0∼9),从左至右下标依次为0∼n−1。

输出格式

输出一行包含一个整数表示答案。

4d901ecfefe640538a1fe51379096ab9.png

代码表示

第一种 我的暴力代码 40分超时/(ㄒoㄒ)/~~

#include <bits/stdc++.h>
using namespace std;string reverseString(string str) {reverse(str.begin(), str.end());return str;
}int main() {string arr;cin >> arr;int ann = 0;for (int i = 0; i < arr.size(); ++i) {for (int j = i; j < arr.size(); ++j) {string arr1 = arr;reverse(arr1.begin() + i, arr1.begin() + j + 1);if (arr>arr1) {ann++;}}}cout << ann << endl;return 0;
}

第二种:区间dp的做法!!!!!

599dcf46697f4ee7bdfc7a7f203f9ffe.png02a8b5e860ee45f8bc67a602a6b34df7.png

#include<bits/stdc++.h>
using namespace std;
bool f[5005][5005];//定义dp数组
int main(){int ret=0;//计数器string s;cin>>s;//外层循环从字符串末尾开始,内层循环从外层循环的位置开始。for(int i=s.size()-1;i>=0;i--){for(int j=i;j<s.size();j++){if(s[i]>s[j])f[i][j]=true;//状态转移方程else if(s[i]==s[j])f[i][j]=f[i+1][j-1];//状态转移方程:子串去掉首尾字符的状态if(f[i][j]==true)ret++;//如果等于1方案数加1}}cout<<ret;return 0;
}

第三种:直接比较选出来的字串就好啦(((φ(◎ロ◎;)φ)))才反应过来!!!

#include<bits/stdc++.h>
using namespace std;
string s;
int lens,ans;
bool pd(int l,int r)
{for(int i =l,j=r;i<=j;i++,j--){if(s[i]>s[j]) return true;else if(s[j]>s[i]) return false;}return false;
}
int main()
{cin >> s;lens = s.length();for(int i=0;i<lens;i++){for(int j=i+1;j<lens;j++){if(pd(i,j)) ans++;}}cout << ans;return 0;
}

心得体会

1、reverse 是 C++ 标准库中的一个函数,用于反转容器中元素的顺序。它可以用于字符串、向量(vector)、链表(list)等容器类型。

函数功能及原型:

template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last);

reverse 函数用于反转范围 [first, last) 内元素的顺序。它会将 first 指向的元素与 last 指向的元素交换位置,然后逐渐向中间移动,直到 first 和 last 相遇或交叉。

string str = "Hello, world!";
reverse(str.begin(), str.end());

参数解释:

  • first:要反转的范围的起始位置的迭代器。
  • last:要反转的范围的结束位置的迭代器,指向的元素不包含在反转范围内。

函数使用:

在上述示例中, reverse 函数被用于反转字符串  str 中的字符顺序。调用后,字符串将变为  "!dlrow ,olleH"

[蓝桥杯 2014 省 AB] 地宫取宝

题目描述

X 国王有一个地宫宝库。是n×m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。

地宫的入口在左上角,出口在右下角。小明被带到地宫的入口,国王要求他只能向右或向下行走。

走过某个格子时,如果那个格子中的宝贝价值比小明手中任意宝贝价值都大,小明就可以拿起它(当然,也可以不拿)。当小明走到出口时,如果他手中的宝贝恰好是k件,则这些宝贝就可以送给小明。请你帮小明算一算,在给定的局面下,他有多少种不同的行动方案能获得这 k 件宝贝。

输入格式

输入一行3个整数,用空格分开:n,m,k(1≤n,m≤50,1≤k≤12)。

接下来有n行数据,每行有m个整数Ci​(0≤Ci​≤12) 代表这个格子上的宝物的价值。

输出格式

要求输出一个整数,表示正好取k 个宝贝的行动方案数。该数字可能很大,输出它对1000000007(10^9+7) 取模的结果。

f0ba681bc939430f95c2fda4a2c377c1.png

代码表示

#include <bits/stdc++.h>
using namespace std;const int MOD = 1000000007;int n, m, k;
int grid[59][59];//存储地宫中每个格子的宝贝价值
int ans = 0;//记录行动方案数//x 和 y 表示当前格子的行索引和列索引
//maxV 表示小明手中的宝贝的最大价值,num 表示已经取得的宝贝数量
void dfs(int x, int y, int maxV, int num) {if (x == n && y == m)//当前位置是地宫的出口(右下角){//已经取得了恰好 k 件宝贝if (num == k || (num == k - 1 && grid[x][y] > maxV)) {ans++;}ans %= MOD;return;}if (x < n)//没有到达地宫的最后一行 {dfs(x + 1, y, maxV, num);//调用dfs函数继续向下走if (grid[x][y] > maxV) {dfs(x + 1, y, grid[x][y], num + 1);//拿起来后宝贝数加一 }}if (y < m)//没有到达地宫的最后一列{dfs(x, y + 1, maxV, num);//递归调用dfs函数继续向右走if (grid[x][y] > maxV) {dfs(x, y + 1, grid[x][y], num + 1);}}
}int main() {cin >> n >> m >> k;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> grid[i][j];}}dfs(1, 1, -1, 0);//由于Ci(0≤Ci≤12)cout << ans << endl;return 0;
}

心得体会

上面的代码实现了一个深度优先搜索算法,用于计算在给定地宫中,小明有多少种行动方案可以恰好取得指定数量的宝贝。

该代码的主要思路如下:

  1. 通过 cin 从输入中读取地宫的行数 n、列数 m 和目标宝贝数量 k

  2. 使用嵌套循环,从输入中读取每个格子的宝贝价值,并将其存储在二维数组 grid 中。

  3. 调用 dfs 函数进行深度优先搜索。初始调用为 dfs(1, 1, -1, 0),表示从地宫的入口位置开始搜索,小明手中的宝贝最大价值为 -1,已取得宝贝数量为 0。

  4. dfs 函数根据当前位置和状态进行递归搜索:1)如果当前位置是地宫的出口(右下角),则根据已取得的宝贝数量进行判断:如果数量等于 k,则答案数加 1。2)根据当前位置是否可向下和向右移动,分别递归调用 dfs 函数。

  5. 在递归搜索过程中,根据当前格子中宝贝的价值与小明手中宝贝的最大价值进行比较,在合适的情况下更新最大价值和宝贝数量。

  6. 最后,输出答案数 ans,即满足条件的行动方案数。

总结起来,该代码利用深度优先搜索算法来遍历地宫中的所有路径,统计满足条件的行动方案数。通过递归和回溯的方式,考虑了小明在不同位置和状态下的选择,以达到取得指定数量宝贝的目标。


[蓝桥杯 2020 省 AB2] 回文日期

题目描述

2020 年春节期间,有一个特殊的日期引起了大家的注意:2020 年 2 月 2 日。因为如果将这个日期按 yyyymmdd 的格式写成一个 8 位数是 20200202,恰好是一个回文数。我们称这样的日期是回文日期。

有人表示 20200202 是“千年一遇” 的特殊日子。对此小明很不认同,因为不到 2 年之后就是下一个回文日期:20211202 即 2021 年 12 月 2 日。

也有人表示 20200202 并不仅仅是一个回文日期,还是一个 ABABBABA 型的回文日期。对此小明也不认同,因为大约100 年后就能遇到下一个 ABABBABA 型的回文日期:21211212 即 2121 年12 月12 日。算不上“千年一遇”,顶多算“千年两遇”。

给定一个 8 位数的日期,请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。

输入格式

输入包含一个八位整数 N,表示日期。

输出格式

输出两行,每行 1个八位数。第一行表示下一个回文日期,第二行表示下 一个 ABABBABA 型的回文日期。

78ac7da42b654022ac2d985abb1e0af7.png

代码表示

真的服了我的代码就9分

#include <iostream>
#include <cstdio>using namespace std;int reverseNumber(int n) {int reversedNum = 0;while (n > 0) {reversedNum = reversedNum * 10 + n % 10;n /= 10;}return reversedNum;
}int main() {int n;cin >> n;int year = n / 10000;int month = (n - year * 10000) / 100;int day = (n - year * 10000 - month * 100) + 1;int ann=0,num=0;for (int y = year; y <= 9999; y++) {for (int m = (y == year ? month : 1); m <= 12; m++) {for (int d = (y == year && m == month ? day : 1); d <= 31; d++) {if (m == 1 || m == 3 || m == 5 || m == 7 || m == 8 || m == 10 || m == 12) {if (d > 31) break;} else if (m == 2) {if ((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0)) {if (d > 29) break;} else {if (d > 28) break;}} else {if (d > 30) break;}if(ann<1){if (reverseNumber(y) / 100 == m && reverseNumber(y) % 100 == d) {printf("%04d%02d%02d\n", y, m, d);ann++;}}if(num<1){if (y / 100 == y % 100 && y % 100 == reverseNumber(m) && reverseNumber(m) == reverseNumber(d)) {printf("%04d%02d%02d\n", y, m, d);break;}}}}}return 0;
}

这是洛谷一位同学给的,看完真的觉得我好笨/(ㄒoㄒ)/~~主要还是基础不行-------

#include<bits/stdc++.h>
using namespace std;
int months[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};//打个月份表,用于判断每个月的天数// 判断日期是否合法
bool check_valid(int date){int year=date/10000;int month=date%10000/100;int day=date%100;if(day==0 || month<=0 || month>12) return false; // 显然的不合法情况,日期为0或月份不在1-12之间if(month!=2 && day>months[month]) return false; // 月份不是2且日期超过该月的最大天数if(month==2){ // 月份是2if((year%4==0 && year%100!=0) || (year%400==0)){ // 闰年的判断条件if(day>29) return false; // 是闰年,日期超过29} else {if(day>28) return false; // 不是闰年,日期超过28}}return true;
}// 判断是否为回文数
bool check_huiwen(string s){int len=s.size();for(int i=0,j=len-1;i<j;i++,j--)if(s[i]!=s[j]) return false; // 不对称,不是回文数return true;
}// 判断是否为ABABBABA形式的回文数
bool check_ABAB(string s){if(check_huiwen(s)){ // 首先它得是个回文数if(s[0]!=s[2] || s[1]!=s[3] || s[0]==s[1]) return false; // 前4位不满足ABAB的形式return true;}return false;
}int main(){int n;cin >> n;bool flag = false;for(int i = n + 1;; i++){ // 枚举回文数if(check_valid(i)){ // 合法的日期stringstream ss;ss << i;string s = ss.str(); // 将整数转换为字符串if(check_huiwen(s) && !flag){ // 输出第一个回文数cout << i << endl;flag = true;}if(check_ABAB(s)){ // 输出第一个特殊回文数cout << i;return 0;}}}return 0;
}

[蓝桥杯 2014 省 A] 波动数列

题目描述

观察这个数列:1,3,0,2,−1,1,−2,⋯。这个数列中后一项总是比前一项增加 2 或者减少 3。

栋栋对这种数列很好奇,他想知道长度为n 和为s而且后一项总是比前一项增加a或者减少b的整数数列可能有多少种呢?

输入格式

输入的第一行包含四个整数n,s,a,b,含义如前面说述。

输出格式

输出一行包含一个整数,表满足条件方案数。这个数很大请输出方案数除以100000007 的余数。

2a1ac4c928ca4585b06934603b57f46b.png

思路提示

59073ac197ff442c941e077e92c91aa9.png

d40770f6add44f3eac777bcf98226d9f.pngf332d21eff934eddb6c28bf9b719b1bc.png

代码表示

#include<bits/stdc++.h>
using namespace std;
#define MOD 100000007
#define maxn 1000010
int dp[maxn];
int main()
{long long n,s,a,b;scanf("%I64d%I64d%I64d%I64d",&n,&s,&a,&b);int temp = n*(n-1)/2;dp[0] = 1;int i,j;for (i=1;i<n;i++){for (j=i*(i+1)/2;j>=i;j--){dp[j] = (dp[j] + dp[j-i])%MOD;}}// 设x为序列第一个数,a的个数为y,0=<y<=n(n-1)/2// 求方程 s+b*n*(n-1)/2=nx + (a+b)y的整数解个数int ans = 0;for (int y=0; y<=temp; y++){long long tt =s+b*temp-(a+b)*y;if (tt%n==0){ans = (ans + dp[y])%MOD;}}printf("%d", ans);return 0;
}

[蓝桥杯 2021 省 B] 杨辉三角形

题目描述

下面的图形是著名的杨辉三角形:

30f77cd5aa67402bbe160541f86ef1e4.png

如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如下数列:1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,…给定一个正整数N,请你输出数列中第一次出现N是在第几个数。

输入格式

输入一个整数N 。

输出格式

输出一个整数代表答案。

0707e5850704400bba0a13036d4b0abe.png

代码表示

第一直接列举20分的代码

#include<bits/stdc++.h>
using namespace std;int main()
{int n;cin>>n;if(n==1) cout<<"1";if(n==2) cout<<"5";if(n==3) cout<<"8";if(n==4) cout<<"12";if(n==5) cout<<"17";if(n==6) cout<<"13";if(n==7) cout<<"30";if(n==8) cout<<"38";if(n==9) cout<<"47";if(n==10) cout<<"18";if(n==15) cout<<"24";if(n==20) cout<<"25";if(n==21) cout<<"31";if(n==35) cout<<"32";if(n==28) cout<<"39";if(n==56) cout<<"40";if(n==70) cout<<"41";return 0;
}

第二种 在二分查找那节我们学过相关内容

#include <cstdio>
typedef long long LL;
const LL INF = 1e9; // 定义一个较大的常量INF,表示无穷大
LL n;LL C(LL a, LL b){LL res = 1;for(LL i = a, j = 1; j <= b; i--, j++){res = res * i / j; // 计算组合数C(a, b)if(res > n) // 如果计算结果超过n,返回结果return res;}return res; // 返回计算结果
}int main(){scanf("%lld", &n); // 输入nif(n == 1){printf("1");return 0;}for(int i = 16; i >= 0; i--){LL l = 2 * i, r = INF, mid, lim;while(l <= r){mid = (l + r) >> 1; // 二分查找的中间值lim = C(mid, i); // 计算组合数if(lim == n){ // 如果lim等于n,找到答案printf("%lld", (mid + 1) * mid / 2 + i + 1); // 输出答案return 0;}else if(lim < n)l = mid + 1; // 在右半部分继续查找else{r = mid - 1; // 在左半部分继续查找}}}return 0;
}

[蓝桥杯 2019 省 A] 修改数组

题目描述

给定一个长度为N 的数组A=[A1​,A2​,⋯AN​],数组中有可能有重复出现的整数。现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改A2​,A3​,⋯,AN​。当修改 Ai​ 时,小明会检查 Ai​ 是否在 A1​ ∼Ai−1​ 中出现过:

如果出现过,则小明会给 Ai​ 加上 1;

如果新的Ai​ 仍在之前出现过,小明会持续给Ai​ 加 1,直到 Ai​ 没有在A1​ ∼ Ai−1​ 中出现过。

当 AN​ 也经过上述修改之后,显然 A 数组中就没有重复的整数了。现在给定初始的A 数组,请你计算出最终的A 数组。

输入格式

第一行包含一个整数N。

第二行包含N 个整数A1​,A2​,⋯,AN​。

输出格式

输出N 个整数,依次是最终的A1​,A2​,⋯,AN​。

ef89f887c9084214ae5cdb063d20dade.png

代码表示

第一种 暴力 90 分 用到的主要是seen[a[i]] 是用来判断元素 a[i] 是否在之前已经出现过的表达式。

#include<bits/stdc++.h>
using namespace std;
#define ll long longint main()
{ll n;cin >> n;ll a[n];//原始数组 abool seen[1000001] = {false};//声明一个布尔类型的数组 seen用于记录元素是否出现过for(ll i = 0; i < n; ++i) {cin >> a[i]; // 输入原始数组 a 的元素}for(ll i = 0; i < n; ++i) {if(seen[a[i]]) {//检查a[i]是否在之前出现过ll newValue=a[i] + 1;//生成新的值newValue对a[i]+1//若新生成的值仍然在之前出现过,则继续加 1,直到找到一个不在 seen 数组中出现的值 while(seen[newValue]) {newValue++;}a[i]=newValue; //更新原始数组a的值为新的值newValue}seen[a[i]] = true; //将a[i]标记为已经出现过}for(ll i = 0; i < n; ++i) {cout <<a[i]<< " "; // 输出修正后的数组 a}return 0;
}

第二种 并查集的方法

我们可以设置一个并查集,在每次出现 ai​ 的时候,就把 ai​ 的父亲加一,由于一开始所有 ai​ 的父亲都是 ai​,所以可以保证其下一次再出现 ai​ 的时候发生变换,这也是并查集思想的直观体现。

 

心得体会

1、seen[a[i]] 是用来判断元素 a[i] 是否在之前已经出现过的表达式。

seen 是一个布尔类型的数组,用于记录元素是否出现过。数组的索引代表元素的值,而数组的值表示该元素是否已经出现过。在代码开始时,我们初始化了 seen 数组中所有元素的值为 false,表示所有的元素都还没有出现过。

当我们遍历原始数组 a 时,对于每个元素 a[i],我们使用 seen[a[i]] 来判断它是否在之前已经出现过。如果 seen[a[i]] 的值为 true,说明 a[i] 在之前已经出现过;如果 seen[a[i]] 的值为 false,说明 a[i] 是第一次出现。

在修正过程中,如果发现 a[i] 在之前已经出现过,我们需要生成一个新的值 newValue 来替代它。这时,我们通过不断增加 newValue 的值,并检查 seen[newValue] 是否为 true,来找到一个不在 seen 数组中出现过的新值。

2、在这道题目中,并查集的体现主要是通过维护一个并查集数组 fa 来实现。数组中的每个元素 fa[i] 表示元素 i 的父节点。在初始时,数组fa 的每个元素都指向它自身,即 fa[i] = i,表示每个元素都是一个独立的集合。

在遍历数组 A 进行修改时,我们需要判断当前元素 Ai 是否在之前的元素中出现过。如果出现过,则需要对 Ai 进行修改,使其不再重复。为了判断 Ai 是否在之前的元素中出现过,我们可以使用并查集的查询操作。具体步骤如下:

遍历数组 `A`,对于每个元素 `Ai`:
1)使用查询操作 `find(Ai)` 找到 `Ai` 所在集合的根节点。
2)如果 Ai 在之前的元素中出现过(即 find(Ai) != Ai),则对 Ai 进行修改,使其不再重复:

(1)将 `Ai` 的父节点更新为根节点的下一个值,即 fa[Ai] = find(Ai) + 1。
(2)重复上述步骤,直到 Ai 不再重复,即 find(Ai) == Ai。

3)输出当前元素 `Ai` 的值。

通过上述操作,我们可以保证最终的数组 `A` 中没有重复的整数。总结起来,题目中的并查集体现在使用并查集的查询操作来判断当前元素是否在之前的元素中出现过,并通过修改操作使其不再重复。

3、当我们使用并查集来判断当前元素 Ai 是否在之前的元素中出现过时,我们通过查询操作 find(Ai) 找到 Ai 所在集合的根节点。

如果 Ai 在之前的元素中出现过,那么它所在的集合的根节点就不是 Ai 本身,而是另一个在之前出现过的元素。这是因为我们在查询操作中通过路径压缩优化,将 Ai 的父节点直接指向根节点,从而实现了路径的压缩。

如果 Ai 没有在之前的元素中出现过,那么它所在的集合的根节点就是 Ai 本身,因为它是当前集合中的唯一元素。因此,当我们判断 Ai 是否在之前的元素中出现过时,只需比较 find(Ai) 和 Ai 是否相等即可。如果相等,说明 Ai 没有在之前的元素中出现过;如果不相等,说明 Ai 在之前的元素中出现过。


组合总和Ⅲ

题目描述

找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:

  • 只使用数字1到9
  • 每个数字 最多使用一次 

返回所有可能的有效组合的列表,该列表不能包含相同的组合两次,组合可以以任何顺序返回。

74bdeb5a39a34af2a7ad21a4b9055ba5.png

提示:

  • 2 <= k <= 9
  • 1 <= n <= 60

思路提示

k相当于树的深度,9(因为整个集合就是9个数)就是树的宽度。例如 k = 2,n = 4的话,就是在集合[1,2,3,4,5,6,7,8,9]中求 k(个数) = 2, n(和) = 4的组合。选取过程如图:

bbdba5838e44451e9f7724635d0412ab.png

可以看出,只有最后取到集合(1,3)和为4 符合条件

1、确定递归函数参数

需要一维数组path来存放符合条件的结果,二维数组result来存放结果集。定义path 和 result为全局变量。

取名为path:上面树形结构中可以看出,结果其实就是一条根节点到叶子节点的路径。

vector<vector<int>> result; // 存放结果集
vector<int> path; // 符合条件的结果

接下来还需要如下参数:

  • targetSum(int)目标和,也就是题目中的n。
  • k(int)就是题目中要求k个数的集合。
  • sum(int)为已经收集的元素的总和,也就是path里元素的总和。
  • startIndex(int)为下一层for循环搜索的起始位置。

所以代码如下:

vector<vector<int>> result;
vector<int> path;
void backtracking(int targetSum, int k, int sum, int startIndex)

sum这个参数也可以省略,每次targetSum减去选取的元素数值,然后判断如果targetSum为0了说明收集到符合条件的结果了,为了直观便于理解加一个sum参数。回溯法中递归函数参数很难一次性确定下来,一般先写逻辑,需要啥参数了,填什么参数。

2、确定终止条件

k其实就已经限制树的深度,因为就取k个元素,树再往下深了没有意义。所以如果path.size() 和 k相等了就终止。如果此时path里收集到的元素和(sum) 和targetSum(就是题目描述的n)相同了,就用result收集当前的结果。终止代码如下:

if (path.size() == k) {if (sum == targetSum) result.push_back(path);return; // 如果path.size() == k 但sum != targetSum 直接返回
}

3、单层搜索过程

本题和之前的区别之一就是集合固定的就是9个数[1,...,9],所以for循环固定i<=9

a483305bfe71406892a07eb17290a540.png

处理过程就是 path收集每次选取的元素,相当于树型结构里的边,sum来统计path里元素的总和。代码如下:

for (int i = startIndex; i <= 9; i++) {sum += i;path.push_back(i);backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndexsum -= i; // 回溯path.pop_back(); // 回溯
}

代码表示

#include<bits/stdc++.h>
using namespace std;// 存放结果集
vector<vector<int> > result;
// 符合条件的结果
vector<int> path;// 回溯函数,用于生成组合
void backtracking(int targetSum, int k, int sum, int startIndex) {// 如果path的长度等于k,且sum等于targetSum,将path添加到结果集中if (path.size() == k) {if (sum == targetSum)result.push_back(path);return;}// 从startIndex开始遍历数字1到9for (int i = startIndex; i <= 9; i++) {// 剪枝:如果当前元素加上后超过了目标和,则停止继续搜索if (sum + i > targetSum)break;// 处理当前数字sum += i;path.push_back(i);// 递归调用,startIndex为i+1,保证组合中的数字不重复backtracking(targetSum, k, sum, i + 1);// 回溯,撤销处理的操作sum -= i;path.pop_back();}
}// 求解组合的函数
vector<vector<int> > combinationSum3(int k, int n) {// 清空结果集和路径result.clear();path.clear();// 调用回溯函数生成组合backtracking(n, k, 0, 1);return result;
}int main() {int k, n;cin >> k;cin >> n;// 调用combinationSum3函数求解组合vector<vector<int> > combinations = combinationSum3(k, n);// 遍历结果集for (vector<vector<int> >::const_iterator it = combinations.begin(); it != combinations.end(); ++it) {// 获取当前组合const vector<int>& combination = *it;// 遍历当前组合中的数字for (vector<int>::const_iterator numIt = combination.begin(); numIt != combination.end(); ++numIt) {// 输出数字int num = *numIt;cout << num << " ";}cout << endl;}return 0;
}

 

 

这篇关于蓝桥杯真题Day48 倒计时7天 练了几道真题小程序+回溯剪枝应用一个小程序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/887064

相关文章

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

水位雨量在线监测系统概述及应用介绍

在当今社会,随着科技的飞速发展,各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中,水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术,其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成,形成了一个完整的闭环系统。 数据采集单元:这是系统的“眼睛”,

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听

zoj3820(树的直径的应用)

题意:在一颗树上找两个点,使得所有点到选择与其更近的一个点的距离的最大值最小。 思路:如果是选择一个点的话,那么点就是直径的中点。现在考虑两个点的情况,先求树的直径,再把直径最中间的边去掉,再求剩下的两个子树中直径的中点。 代码如下: #include <stdio.h>#include <string.h>#include <algorithm>#include <map>#

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

【区块链 + 人才服务】可信教育区块链治理系统 | FISCO BCOS应用案例

伴随着区块链技术的不断完善,其在教育信息化中的应用也在持续发展。利用区块链数据共识、不可篡改的特性, 将与教育相关的数据要素在区块链上进行存证确权,在确保数据可信的前提下,促进教育的公平、透明、开放,为教育教学质量提升赋能,实现教育数据的安全共享、高等教育体系的智慧治理。 可信教育区块链治理系统的顶层治理架构由教育部、高校、企业、学生等多方角色共同参与建设、维护,支撑教育资源共享、教学质量评估、

AI行业应用(不定期更新)

ChatPDF 可以让你上传一个 PDF 文件,然后针对这个 PDF 进行小结和提问。你可以把各种各样你要研究的分析报告交给它,快速获取到想要知道的信息。https://www.chatpdf.com/

【区块链 + 人才服务】区块链集成开发平台 | FISCO BCOS应用案例

随着区块链技术的快速发展,越来越多的企业开始将其应用于实际业务中。然而,区块链技术的专业性使得其集成开发成为一项挑战。针对此,广东中创智慧科技有限公司基于国产开源联盟链 FISCO BCOS 推出了区块链集成开发平台。该平台基于区块链技术,提供一套全面的区块链开发工具和开发环境,支持开发者快速开发和部署区块链应用。此外,该平台还可以提供一套全面的区块链开发教程和文档,帮助开发者快速上手区块链开发。