当前位置: 首页 > news >正文

Acwing 蓝桥杯 第一章 递归与递推

我上周在干什么,感觉我上周啥也没训,本来两天一次的vp也没v

很寄啊,再这样下去真不行了

先总结一下如何爆搜:

先去确定好枚举的对象

枚举的对象很重要!!这直接影响了复杂度

然后就是去想递归树就好了

一、确定状态:

状态分为全局变量和局部变量

考虑状态时去考虑三样东西:

  1. 阶段(即深度),阶段作为出口

  1. 影响决策的因素(全局or局部)

  1. 要维护的答案

二、枚举决策+加限定条件

三、确定出口(根据阶段)

那么我们怎么去考虑复杂度:考虑每一层树的结点个数*每个结点的复杂度

92. 递归实现指数型枚举 - AcWing题库

思路:

一、先去确定状态:

  1. 阶段就是深度,即选了几个数了

  1. 决策就是选与不选,没东西影响决策

  1. 开个全局数组记录答案即可

因此状态就是dfs(x)

二、枚举决策:选or不选

三、确定出口:深度>n

Code:

#include <bits/stdc++.h>
#define int long long
const int mxn=3e6+10;
const int mxe=2e5+10;
using namespace std;
vector<int> v;
int n;
int vis[mxn];
void print(){for(int i=0;i<v.size();i++) cout<<v[i]<<" \n"[i==v.size()-1];
}
void dfs(int u){if(u>n){print();return;}v.push_back(u);dfs(u+1);v.pop_back();dfs(u+1);
}
void solve(){cin>>n;dfs(1);cout<<'\n';
}
void init(){}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;init();while(__--)solve();return 0;
}

AcWing 94. 递归实现排列型枚举 - AcWing

一、设状态:

  1. 阶段:深度,即选了几个数

  1. 影响决策的因素:只能选没选过的数:开个全局vis

  1. 记录答案:开个全局数组记录答案

二、枚举决策:

1~n,然后不选vis[i]=1的就行

三、出口:

深度>n

Code:

#include <bits/stdc++.h>
#define int long long
const int mxn=3e6+10;
const int mxe=2e5+10;
using namespace std;
vector<int> v;
int n;
int vis[mxn];
void print(){for(int i=0;i<v.size();i++) cout<<v[i]<<" \n"[i==v.size()-1];
}
void dfs(int u){if(u>n){print();return;}for(int i=1;i<=n;i++){if(!vis[i]){v.push_back(i);vis[i]=1;dfs(u+1);vis[i]=0;v.pop_back();}}
}
void solve(){cin>>n;dfs(1);
}
void init(){}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;init();while(__--)solve();return 0;
}

93. 递归实现组合型枚举 - AcWing题库

一、确定状态:

  1. 阶段:即深度,选不超过m个数

  1. 影响决策的因素:每次选比上次选的数大的,因此要记录上次选的数

  1. 记录结果:开个全局数组就行了

因此状态就是dfs(u,last),第二维是上次选的数

二、枚举决策:

从last+1开始枚举即可,不用开vis数组,不会重复

三、出口:

选了>m个数

Code:

#include <bits/stdc++.h>
#define int long long
const int mxn=3e6+10;
const int mxe=2e5+10;
using namespace std;int n,m,len=0;
int vis[mxn],a[mxn];
void print(){for(int i=1;i<=len;i++) cout<<a[i]<<" \n"[i==len];
}
void dfs(int u,int last){if(u>m){print();return;}for(int i=last+1;i<=n;i++){if(!vis[i]){vis[i]=1;a[++len]=i;dfs(u+1,i);len--;vis[i]=0;}}
}
void solve(){cin>>n>>m;dfs(1,0);
}
void init(){}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;init();while(__--)solve();return 0;
}

AcWing 1209. 带分数 - AcWing

枚举对象:先去枚举全排列,然后枚举两个指针隔起来,验证正确性就好了,不需要dfs爆搜

有个细节就是:不要用substr,写个函数更清晰

Code:

#include <bits/stdc++.h>
//#define int long long
const int mxn=3e6+10;
const int mxe=2e5+10;
using namespace std;int n;
string s="123456789";
bool check(int x1,int x2,int x3){if(x2%x3==0&&x1+x2/x3==n) return true;return false;
}
int trans(int l,int r){int res=0;for(int i=l;i<=r;i++){res=res*10+(s[i]-'0');}return res;
}
void solve(){int ans=0;cin>>n;do{for(int i=0;i<9;i++){for(int j=i+1;j<9;j++){int a1=trans(0,i);int a2=trans(i+1,j);int a3=trans(j+1,8);if(a1==0||a2==0||a3==0) continue;if(check(a1,a2,a3)) ans++;}}}while(next_permutation(s.begin(),s.end()));cout<<ans<<'\n';
}
void init(){}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;init();while(__--)solve();return 0;
}

AcWing 1208. 翻硬币 - AcWing

思路:

这是典中典,第一个是确定的,因此只需递推过去就好了

Code:

#include <bits/stdc++.h>
#define int long long
const int mxn=3e6+10;
const int mxe=2e5+10;
using namespace std;string s,t;
void solve(){cin>>s>>t;int cnt=0;for(int i=0;i<s.size();i++){if(s[i]!=t[i]){cnt++;if(s[i]=='*') s[i]='o';else s[i]='*';if(s[i+1]=='o') s[i+1]='*';else s[i+1]='o';}}cout<<cnt<<'\n';
}
void init(){}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;init();while(__--)solve();return 0;
}

相关文章:

Acwing 蓝桥杯 第一章 递归与递推

我上周在干什么&#xff0c;感觉我上周啥也没训&#xff0c;本来两天一次的vp也没v很寄啊&#xff0c;再这样下去真不行了先总结一下如何爆搜&#xff1a;先去确定好枚举的对象枚举的对象很重要&#xff01;&#xff01;这直接影响了复杂度然后就是去想递归树就好了一、确定状态…...

模型部署笔记

目录模型部署工作ONNX存在的意义ONNX&#xff08;Open Neural Network Exchange&#xff09;ONNX示例模型推理示例Batch调整量化量化方式常见问题模型部署工作 训练好的模型在特定软硬件平台下推理针对硬件优化和加速的推理代码 训练设备平台&#xff1a; CPU、GPU、DSP ONN…...

多线程之wait和notify

目录 1.wait()方法 2. notify方法 因为线程之间是抢占式执行的&#xff0c;所以线程之间执行的先后顺序难以预知。但是实际开发中&#xff0c;我们希望线程之间的执行顺序是能被掌控的&#xff0c;比如线程2开始之前&#xff0c;需要线程1的某个任务先被执行。也就是说,很多时…...

MVCC 当前读 快照读 RC read view RR下事务更新不会丢失

MVCC(multi-version-concurrent-control) MVCC是行锁的一个变种&#xff0c;但MVCC在很多情况下它避免了加锁。不是buffer块&#xff0c;而是buffer中的记录行。 MVCC (Multi-Version Concurrency Control) (注&#xff1a;与MVCC相对的&#xff0c;是基于锁的并发控制&#x…...

NCRE计算机等级考试Python真题(二)

第二套试题1、关于算法的描述&#xff0c;以下选项中错误的是A.算法具有可行性、确定性、有穷性的基本特征B.算法的复杂度主要包括时间复杂度和数据复杂度C.算法的基本要素包括数据对象的运算和操作及算法的控制结构D.算法是指解题方案的准确而完整的描述正确答案&#xff1a; …...

借助IBM Spectrum LSF为芯片行业大幅提升算力,预测未来

IBM Spectrum LSF 客户案例——上海开赟软件服务有限公司借助IBM Spectrum LSF为芯片行业大幅提升算力&#xff0c;预测未来 业务影响 中国芯片市场作为全球消费芯片市场重要组成部分&#xff0c;近年来发展迅猛。据国家统计局统计&#xff0c;2019年中国集成电路产量突破200…...

力扣-换座位

大家好&#xff0c;我是空空star&#xff0c;本篇带大家了解一道简单的力扣sql练习题。 文章目录前言一、题目&#xff1a;626. 换座位二、解题1.正确示范①提交SQL运行结果2.正确示范②提交SQL运行结果3.正确示范③提交SQL运行结果4.正确示范④提交SQL运行结果5.其他总结前言 …...

DFT基本入门介绍

1.什么是DFT&#xff1f;2.为什么要做DFT&#xff1f;3.“测试”与“验证”的区别4.DFT的核心技术1)扫描路径设计&#xff08;Scan Design&#xff09;2)内建自测试&#xff08;Bist&#xff09;3)JTAG4)ATPG5.DFT工程师的岗位职责随着芯片的制程越来小(5nm), 芯片的规模越来越…...

做「增长」必须懂的6大关键指标

无论你所从事的是哪个行业&#xff0c;增长都不是一件易事&#xff0c;SaaS公司想要维持长期的增长更是难上加难。这是因为SaaS公司对未来回报的依赖程度更大&#xff0c;反观那些传统商业模式的公司&#xff0c;主要的收入来源都集中在产品购买交付的时点上&#xff0c;而客户…...

Linux:soft lockup 检测机制

1. 前言 限于作者能力水平&#xff0c;本文可能存在谬误&#xff0c;因此而给读者带来的损失&#xff0c;作者不做任何承诺。 2. 分析背景 本文分析基于 linux-4.14.132 内核代码分析&#xff0c;运行环境 Ubuntu 16.04.4 LTS QEMU ARM vexpress-a9 &#xff0c;rootfs 基…...

天线理论知识4——非频变天线

目录 简介自补结构巴比涅原理天线的描述常见的非频变天线简介 所谓的非频变天线指的是天线的参数几乎不随着频率的改变而发生变化。 自补结构 天线的自补结构指的是:由无限大且无厚度的理想导电区域的自由空间中的非导电区域放置一起的结构称为自补结构。包含金属部分和非金…...

基础架构组件选型及服务化

常见的分布式基础架构组件 分布式服务化框架&#xff0c;业界开源产品比如 Dubbo、Spring Cloud 这样的框架&#xff1b;分布式缓存及框架&#xff0c;业界如 Redis、Memcached&#xff0c;框架如 Codis 和 Redis Cluster&#xff1b;数据库及分布式数据库框架&#xff0c;这两…...

leetcode-每日一题-1247(中等,数学逻辑)

这道题当理解清了意思之后&#xff0c;只要是s1和s2的某位置的字母一样时我们就可以忽视比如s1"xxxxxxyyyy"; 就可以看成s1"xxxyyyy";s2"xxxyyyxxxx"; s2"yyyxxxx";其次就是只有当x和y位置差异产生的数量同奇偶的时候才可以构成相等字…...

前端面试题 —— 计算机网络(一)

目录 一、常见的HTTP请求头和响应头 二、HTTP状态码304是多好还是少好&#xff1f; 三、OPTIONS请求方法及使用场景 四、对keep-alive的理解 五、HTTP协议的优点和缺点 六、URL有哪些组成部分&#xff1f; 七、HTTPS通信&#xff08;握手&#xff09;过程 八、HTTPS的特…...

分布式-分布式缓存笔记

分布式系统缓存 缓存分类 前端缓存 前端缓存包括页面和浏览器缓存&#xff0c;如果是 App&#xff0c;那么在 App 端也会有缓存。当你打开商品详情页&#xff0c;除了首次打开以外&#xff0c;后面重复刷新时&#xff0c;页面上加载的信息来自多种缓存。 页面缓存属于客户端…...

【反序列化漏洞-01】为什么要序列化

为什么要序列化百度百科上关于序列化的定义是&#xff0c;将对象的状态信息转换为可以存储或传输的形式(字符串)的过程。在序列化期间&#xff0c;对象将其当前状态写入到临时或持久性存储区(非关系型键值对形式的数据库Redis&#xff0c;与数组类似)。以后&#xff0c;可以通过…...

用c语言模拟实现常用字符串函数

目录 一.常用字符串函数介绍 1.strlen 2. strcpy 3.strcmp 4.strcat 5.strstr 二.模拟实现常用字符串函数 1.strlen 2.strcpy 3.strcmp 4.strcat 5.strstr 一.常用字符串函数介绍 1.strlen 字符串strlen是用来求字符串长度的&#xff0c;我们可以打开cpp网站查看有关…...

在 Flutter 中使用 webview_flutter 4.0 | 基础用法与事件处理

大家好&#xff0c;我是 17。 Flutter WebView 一共写了四篇文章 在 Flutter 中使用 webview_flutter 4.0 | 基础用法与事件处理在 Flutter 中使用 webview_flutter 4.0 | js 交互Flutter WebView 性能优化&#xff0c;让 h5 像原生页面一样优秀&#xff0c;已入选 掘金一周 …...

JavaWeb--Servlet

Servlet1 简介2 快速入门3 执行流程4 生命周期5 方法介绍6 体系结构7 urlPattern配置8 XML配置目标&#xff1a; 理解Servlet的执行流程和生命周期掌握Servlet的使用和相关配置 1 简介 Servlet是JavaWeb最为核心的内容&#xff0c;它是Java提供的一门动态web资源开发技术。 使…...

Linux启动过程

theme: channing-cyan 两种启动方式 传统启动方式&#xff08;LEGACYMBR&#xff09; 指传统BIOS启动方式&#xff0c;存在一些不足&#xff1a;比如最大只支持2TB磁盘&#xff0c;磁盘最多四个分区&#xff0c;且不支持图形操作 UEFIGPT方式 是新式的启动方式&#xff0c…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...