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

[蓝桥杯 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){ // 月份是2
        if((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); // 输入n
    if(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 long

int main()
{
    ll n;
    cin >> n;
    ll a[n];//原始数组 a
    bool 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调整startIndex
    sum -= 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到9
    for (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;
}

 

 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/537455.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C#基础--之数据类型

C#基础–之数据类型 在第一章我们了解了C#的输入、输出语句后&#xff0c;我这一节主要是介绍C#的基础知识&#xff0c;本节的内容也是后续章节的基础&#xff0c;好的开端等于成功的一半。在你阅读完本章后&#xff0c;你就有足够的C#知识编写简单的程序了。但还不能使用封装、…

基于PyAutoGUI图片定位的自动化截图工具--jmeter部分(2)

1、计划 压测完成后需要编写性能测试报告&#xff0c;报告中所需数据截图较多&#xff0c;使用自动化操作方便快捷&#xff0c;就编写一个界面工具以便后续复用。 基于PyAutoGUI图片定位的自动化截图工具–jmeter部分   使用pyautogui 库操作鼠标键盘&#xff0c;按钮根据截取…

汇舟问卷:做调查问卷需要准备什么?

大家好&#xff0c;我是汇舟问卷。海外问卷调查分为很多个种类&#xff0c;接触最多的有站点查、口子查和渠道查&#xff0c;每种调查的方式都是不一样的。 几年前口子查的操作门槛还是很低的&#xff0c;我们只需要在国外的社交网站上搜索调查问卷、调查这些类似的文字就能获…

MongoDB爬虫:(某扑)实战

https://bbs.hupu.com/bxj网页地址: https://bbs.hupu.com/bxj 然后我们在网页上定义帖子名称、帖子链接、创建时间、回复数、最后回复用户...... 除此之外,我们发现虎扑步行街最多显示的页数(20): 、 当我们打开第3页的时候,网页的URL的地址变为了:https://bbs.hupu.…

基于java+springboot+vue实现的西安旅游系统(文末源码+Lw)23-265

摘 要 如今社会上各行各业&#xff0c;都喜欢用自己行业的专属软件工作&#xff0c;互联网发展到这个时候&#xff0c;人们已经发现离不开了互联网。新技术的产生&#xff0c;往往能解决一些老技术的弊端问题。因为传统西安旅游系统信息管理难度大&#xff0c;容错率低&#…

一文看尽西周275年12王历史

周朝是中国历史上继商朝之后的第三个王朝。周王朝一共传国君 32 代 37 王&#xff0c;享国共计 790 年。周朝分为“西周”&#xff08;前 1046&#xff0d;前 771 年&#xff09;与“东周”&#xff08;前 770 年&#xff0d;前 256 年&#xff09;两个时期。 西周由周武王姬发…

Bug及异常:unity场景角色移动卡墙壁的问题

场景是一个小的杠铃形状封闭空间&#xff0c;美术没有给包围盒&#xff0c;我自己用blender做了一个&#xff08;属于兴趣爱好&#xff09;&#xff0c;如下&#xff1a; 导入场景中使用meshcollider做成空气墙&#xff0c;发现角色移动到角落继续行走会卡角落处&#x…

TSINGSEE青犀AI智能分析网关V4人员睡岗检测算法介绍及应用

人员睡岗AI算法是一种通过人工智能技术来检测和预警人员是否处于睡眠状态的算法。它主要通过分析人员的行为、姿势和身体特征等信息来判断人员是否已经进入睡眠状态。该算法通过对监控摄像头捕捉的画面进行实时分析&#xff0c;利用卷积神经网络&#xff08;CNN&#xff09;对图…

LongVLM:让大模型解读长视频 SOTA 的方法

LongVLM&#xff1a;让大模型解读长视频 SOTA 的方法 使用LongVLM处理长视频的步骤LongVLM 方法3.1 总体架构3.2 局部特征聚合3.3 全局语义整合 效果4.1 实验设置4.2 主要结果4.3 消融研究4.4 定性结果 论文&#xff1a;https://arxiv.org/pdf/2404.03384.pdf 代码&#xff1a…

适配器模式类图与代码

某软件系统中&#xff0c;已设计并实现了用于显示地址信息的类Address,现要求提供基于Dutch语言的地址信息显示接口。为了实现该要求并考虑到以后可能还会出现新的语言的接口&#xff0c;决定采用适配器(Adapter)模式实现该要求&#xff0c;得到如图7.9所示的类图。 【Java代码…

硬件学习件Cadence day16 做个笔记,BOM 位号这个参数输出的两种情况。

1. BOM 中位号有3种情况 1. 一种是位号生成时多行&#xff0c;每行是固定的位数。&#xff08;如下图所示&#xff09; 2. 一种是位号生成时只有一行&#xff0c;但是可以使用表格中自动换行功能&#xff0c;给他换行&#xff0c;但是这个位号本质上只有一行&#xff0c;只是因…

可视化后台管理系统-空框架

1.下载element-plus npm install element-plus --save 注意&#xff1a;element-ui不适配vue3&#xff0c;官方已将vue3版本的更新为element-plus 2.main.js配置 // 全局样式 import ./assets/main.cssimport { createApp } from vue import { createPinia } from piniaimpo…

【教学类-52-02】20240412动物数独02(四宫格)黏贴卡片

作品展示 背景需求 制作了动物数独4宫格后&#xff0c;需要再做一些黏贴上去的图片 【教学类-52-01】20240411动物数独&#xff08;4宫格&#xff09;-CSDN博客文章浏览阅读53次。【教学类-52-01】20240411动物数独01&#xff08;4宫格&#xff09;https://blog.csdn.net/rea…

中科方德服务器操作系统安装zabbix5.0

原文链接&#xff1a;中科方德服务器操作系统安装zabbix5.0 Hello&#xff0c;大家好啊&#xff01;接着我们上一次的讨论&#xff0c;今天我要为大家介绍如何在已经安装好的中科方德服务器操作系统基础上&#xff0c;安装和配置Zabbix 5.0。Zabbix是一个开源的监控软件工具&am…

C语言 | Leetcode C语言题解之第24题两两交换链表中的节点

题目&#xff1a; 题解&#xff1a; struct ListNode* swapPairs(struct ListNode* head) {struct ListNode dummyHead;dummyHead.next head;struct ListNode* temp &dummyHead;while (temp->next ! NULL && temp->next->next ! NULL) {struct ListNod…

[Python图像识别] 五十二.水书图像识别 (2)基于机器学习的濒危水书古文字识别研究

该系列文章是讲解Python OpenCV图像处理知识,前期主要讲解图像入门、OpenCV基础用法,中期讲解图像处理的各种算法,包括图像锐化算子、图像增强技术、图像分割等,后期结合深度学习研究图像识别、图像分类应用。目前我进入第二阶段Python图像识别,该部分主要以目标检测、图像…

go语言学习--3.常用语句

目录 1.条件语句 1.1 if语句 1.2 if-else语句 1.3 switch语句 1.4 select语句 2.循环语句 2.1循环处理语句 2.2循环控制语句 3.go语言关键字 1.条件语句 和c语言类似&#xff0c;相关的条件语句如下表所示&#xff1a; 1.1 if语句 if 布尔表达式 {/* 在布尔表达式为 t…

前端常见面试题-CSS盒模型

前言&#xff1a; 什么是CSS盒模型&#xff1f;盒模型的构造&#xff1f; 在前端开发中&#xff0c;CSS 盒模型是一种非常基础且核心的概念&#xff0c;它描述了文档中的每个元素被框架处理的方式。 ---- 打开浏览器开发者工具&#xff0c;查看Elements右侧下的Styles底部。 …

C++ | Leetcode C++题解之第21题合并两个有序链表

题解&#xff1a; 题解&#xff1a; class Solution { public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* preHead new ListNode(-1);ListNode* prev preHead;while (l1 ! nullptr && l2 ! nullptr) {if (l1->val < l2->val) {prev-…

Python用于模拟量子系统库之qutip使用详解

概要 QuTiP(Quantum Toolbox in Python)是一个用于模拟量子系统的开源Python库,它提供了丰富的工具来研究量子力学和量子信息学。 安装 通过pip可以轻松安装QuTiP: pip install qutip特性 多种量子对象表示:支持量子态、算符和超算符的表示和操作。 动力学模拟:提供了…