2022——蓝桥杯十三届2022国赛大学B组真题

在这里插入图片描述

问题分析

看到这个问题的同学很容易想到用十层循环暴力计算,反正是道填空题,一直算总能算得出来的,还有些同学可能觉得十层循环太恐怖了,写成回溯更简洁一点。像下面这样

#include <bits/stdc++.h>
using namespace std;
int cnt=0;
vector<bool> used(2023,false);
void dfs(int now,int len,int start) {if(len==10){if(now==2022){cnt++;}return;}for(int i=start;i<=2022-now;i++){if(!used[i]){used[i]=true;dfs(now+i,len+1,i+1);used[i]=false;}}
}
int main() {dfs(0,0,1);cout<<cnt<<endl;return 0;
}

但是我们分析一下,这个时间复杂度大概是 O ( C 2022 10 ) O(C_{2022}^{10}) O(C202210)级别的,这个数字太恐怖了,要高于 1 0 30 10^{30} 1030的数量级,而c++代码在平台上运行的速度大概是 1 0 9 10^{9} 109次每秒。所以,根本不可能暴力求出答案。而回溯不可以,我们可以动态规划嘛。这实际上就是典型的限量背包问题(如果不知道什么是限量背包问题,可以看我的这篇博客)。从物品(1~2022)中挑选10个物品,要求每种物品只能选一次,然后装满该背包(容量2022)有多少种组合?将该问题转化为背包问题就很容易解决了。(不过要记得用long long,这个数字很大)

具体代码如下

#include<iostream>
using namespace std;
long long int f[11][2023]= {0}; //f[j][k]:选择了j个物品满载容积k的背包的组合数 
int i, j, k;
int main() {f[0][0]=1;for(i=1; i<=2022; i++) {//遍历每个物品 for(k=2022; k>=i; k--) {//遍历背包容量,从后往前遍历 for(j=1; j<=10; j++) {//遍历每个选择数量 f[j][k]+=f[j-1][k-i];}}}cout << f[10][2022];return 0;
}

结果

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

用 Supabase CLI 进行本地开发环境搭建

文章目录 &#xff08;零&#xff09;前言&#xff08;一&#xff09;Supabase CLI&#xff08;1.1&#xff09;安装 Scoop&#xff08;1.2&#xff09;用 Scoop 安装 Supabase CLI &#xff08;二&#xff09;本地项目环境&#xff08;2.1&#xff09;初始化项目&#xff08;2…

C++ | Leetcode C++题解之第86题分隔链表

题目&#xff1a; 题解&#xff1a; class Solution { public:ListNode* partition(ListNode* head, int x) {ListNode* small new ListNode(0);ListNode* smallHead small;ListNode* large new ListNode(0);ListNode* largeHead large;while (head ! nullptr) {if (head-…

Spring STOMP-消息处理流程

一旦STOMP的接口被公布&#xff0c;Spring应用程序就成为连接客户端的STOMP代理。本节描述服务端消息处理的流程。 spring-messaging模块包含消息类应用的基础功能&#xff0c;这些功能起源于Spring Integration项目。并且&#xff0c;后来被提取整合到Spring框架&#xff0c;…

Zookeeper 注册中心:单机部署

序言 本文给大家介绍 Zookeeper 单机部署流程、 如何与 Spring 整合使用。除此之外&#xff0c;还有 Zookeeper 作为注册中心与 SpringCloud 的整合流程。 一、部署流程 官网下载 Zookeeper 安装包 解压安装包到指定目录 进入 apache-zookeeper-3.8.4-bin/conf 目录&…

目标检测——印度车辆数据集

引言 亲爱的读者们&#xff0c;您是否在寻找某个特定的数据集&#xff0c;用于研究或项目实践&#xff1f;欢迎您在评论区留言&#xff0c;或者通过公众号私信告诉我&#xff0c;您想要的数据集的类型主题。小编会竭尽全力为您寻找&#xff0c;并在找到后第一时间与您分享。 …

《C++学习笔记---初阶篇6》---string类 上

目录 1. 为什么要学习string类 1.1 C语言中的字符串 2. 标准库中的string类 2.1 string类(了解) 2.2 string类的常用接口说明 2.2.1. string类对象的常见构造 2.2.2. string类对象的容量操作 2.2.3.再次探讨reserve与resize 2.2.4.string类对象的访问及遍历操作 2.2.5…

【Spring】验证 @ServerEndpoint 的类成员变量线程安全

文章目录 前言猜想来源验证方法Controller 的情况ServerEndpoint 的情况 后记 前言 最近有 websocket 的需求。探索 ServerEndpoint 的类成员变量特点。 这里类比 Controller 讨论 ServerEndpoint 类成员变量是否线程安全。 猜想来源 网上的教程大多数都这么展示程序&#…

OBS插件--音频采集

音频采集 音频采集是一款 源 插件,类似于OBS的win-capture/game-capture&#xff0c;允许从特定应用程序捕获音频&#xff0c;而不是捕获整个系统的音频。避免了因为特定音频的采集而需要引入第三方软件&#xff0c;而且时延也非常低。 下面截图演示下操作步骤&#xff1a; 首…

简单的Python HTML 输出

1、问题背景 一名初学者在尝试将 Python 脚本输出到网页上时遇到了一些问题。他当前使用 Python 和 HTML 进行开发&#xff0c;并且遇到了以下问题&#xff1a; 担心自己的代码过于复杂&#xff0c;尤其是 WebOutput() 函数。希望通过 JavaScript 使用 HTML 模板文件更新数据。…

几个字符串函数的使用和模拟实现(2)

strcop的使用和模拟实现 strcpy函数的使用事项&#xff1a; 源字符串时不需要修改的&#xff0c;在定义前加上const 源字符串被拷贝到目标字符串上时终止字符\0也被拷贝进去 目标数组的大小要相对于源数组的大小足够大&#xff0c;并且不应该在内存中重叠 函数的返回值是一个字…

网络无线网卡无法配置正确的 dns 服务器

网络无线网卡无法配置正确的 dns 服务器--解决办法 网络无线网卡无法配置正确的 dns 服务器--解决办法 网络无线网卡无法配置正确的 dns 服务器–解决办法 建议先使用疑难反馈&#xff08;自带的&#xff09; 打开网络适配中心 之后更改适配器设置&#xff0c;在点击 wlan 属…

绿盟之旅——一段安全实习结束

去年&#xff0c;因为着急找实习&#xff0c;拿着简历就开始海投&#xff0c;当时想的是有人让我去就谢天谢地了&#xff0c;第一个约我面试的就是绿盟&#xff0c;也很顺利的通过了面试&#xff0c;当时让我选择在上海还是北京&#xff0c;我选择的是上海&#xff0c;因为学校…

【C++】set 和 map 学习及使用

&#x1f525;博客主页&#xff1a; 小羊失眠啦. &#x1f3a5;系列专栏&#xff1a;《C语言》 《数据结构》 《C》 《Linux》 ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 前言 set 和 map 是 STL 中的容器之一&#xff0c;不同于普通容器&#xff0c;它俩的查找速度极快…

开发一款相亲交友小程序

uni-app框架&#xff1a;使用Vue.js开发跨平台应用的前端框架&#xff0c;编写一套代码&#xff0c;可编译到Android、小程序等平台。 框架支持:springboot/Ssm/thinkphp/django/flask/express均支持 前端开发:vue.js 可选语言&#xff1a;pythonjavanode.jsphp均支持 运行软件…

第四届上海理工大学程序设计全国挑战赛 J.上学 题解 DFS 容斥

上学 题目描述 usst 小学里有 n 名学生&#xff0c;他们分别居住在 n 个地点&#xff0c;第 i 名学生居住在第 i 个地点&#xff0c;这些地点由 n−1 条双向道路连接&#xff0c;保证任意两个地点之间可以通过若干条双向道路抵达。学校则位于另外的第 0 个地点&#xff0c;第…

【JAVA进阶篇教学】第十三篇:Java中volatile关键字讲解

博主打算从0-1讲解下java进阶篇教学&#xff0c;今天教学第十三篇&#xff1a;volatile关键字讲解。 在 Java 中&#xff0c;volatile关键字是一种轻量级的同步机制&#xff0c;用于确保变量的可见性和禁止指令重排序。本文将详细解释volatile关键字的工作原理、可见性保证以及…

Web安全:SQL注入之布尔盲注原理+步骤+实战操作

「作者简介」&#xff1a;2022年北京冬奥会网络安全中国代表队&#xff0c;CSDN Top100&#xff0c;就职奇安信多年&#xff0c;以实战工作为基础对安全知识体系进行总结与归纳&#xff0c;著作适用于快速入门的 《网络安全自学教程》&#xff0c;内容涵盖系统安全、信息收集等…

ansible------inventory 主机清单

目录 inventory 中的变量 2&#xff09;组变量[webservers:vars] #表示为 webservers 组内所有主机定义变量&#xff0c;所有组内成 员都有效 ansible_userrootansible_passwordabc1234 3&#xff09; [all:vars…

实现字符串复制(C语言)

一、N-S流程图&#xff1b; 二、运行结果&#xff1b; 三、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>int main() {//初始化变量值&#xff1b;int i 0;char a[100], b[100];//获取字符串&#xff1b;printf("请为数组a输入字符串…

回溯算法精讲

原理 回溯&#xff0c;就和深度优先遍历&#xff08;DFS&#xff09;类似&#xff0c;属于先一层到底直至到终点&#xff0c;如果这条路径不对&#xff0c;则回退一下&#xff0c;再继续往下搜索。 抽象地说&#xff0c;解决一个回溯问题&#xff0c;实际上就是遍历一棵决策树…