三道dfs题
一:1114. 棋盘问题 - AcWing题库
分别枚举行和列,能填的地方就填,dfs就行
#include <iostream>
using namespace std;const int N = 10;
char g[N][N];
int n, k;
int res;
bool st[N];void dfs(int u, int cnt) // u枚举行
{if(cnt == k ) {res ++;return;}if(u >= n) return;for(int i = 0; i < n; i ++ ) // 这里枚举列{if(g[u][i] == '#' && !st[i]) {st[i] = true;dfs(u + 1, cnt + 1);st[i] = false;}}dfs(u + 1, cnt); // 回溯
}int main()
{while(scanf("%d%d", &n, &k)){if(n == -1 && k == -1) break;res = 0;for(int i = 0; i < n; i ++ ){cin >> g[i];}dfs(0, 0);cout << res << endl;}return 0;
}
二:P1025 [NOIP2001 提高组] 数的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这道题类似于组合型枚举
直接
#include <iostream>
using namespace std;int n, k;
int res;
int last;void dfs(int u, int start, int sum)
{if(sum > n) return ;if(u > k){if(sum == n){res ++;}return ;}for(int i = start; i <= n && sum + i * (k - u + 1) <= n; i ++ ) // 组合型枚举的做法就是用start去规定下一个位置{dfs(u + 1, i, sum + i);}
}int main()
{cin >> n >> k;dfs(1, 1, 0);cout << res;return 0;
}
三:P1019 [NOIP2000 提高组] 单词接龙 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这个题最主要的就是dfs前的预处理
1是将重合部分的长度处理出来,2是怎么记录每个单词最多用两次
#include <iostream>
#include <string>
using namespace std;int n;
string s[20];
int m[20][20], used[20], ans; // m表示i与j重合的长度, used 表示i用过的次数
char start;void dfs(string dragon, int pos)
{ans = max(ans, (int)dragon.size()); // 这里必须类型一致used[pos] ++;for(int i = 0; i < n; i ++ ){if(m[pos][i] && used[i] < 2){dfs(dragon + s[i].substr(m[pos][i]), i); // 接龙}}// 回溯 used[pos] --;
}int main()
{cin >> n;for(int i = 0; i < n; i ++ ){cin >> s[i];}cin >> start;// 预处理一下,填mfor(int i = 0; i < n; i ++ ){for(int j = 0; j < n; j ++ ){string a = s[i], b = s[j];for(int k = 1; k < a.size() && k < b.size(); k ++ ){if(a.substr(a.size() - k, k) == b.substr(0, k)){m[i][j] = k;break; // 重合长度最小时,答案最大}}}}for(int i = 0; i < n; i ++ ){if(s[i][0] == start){dfs(s[i], i);}}cout << ans;return 0;
}
相关文章:
三道dfs题
一:1114. 棋盘问题 - AcWing题库 分别枚举行和列,能填的地方就填,dfs就行 #include <iostream> using namespace std;const int N 10; char g[N][N]; int n, k; int res; bool st[N];void dfs(int u, int cnt) // u枚举行 {if(cnt …...
Seaborn数据可视化(四)
目录 1.绘制箱线图 2.绘制小提琴图 3.绘制多面板图 4.绘制等高线图 5.绘制热力图 1.绘制箱线图 import seaborn as sns import matplotlib.pyplot as plt # 加载示例数据(例如,使用seaborn自带的数据集) tips sns.load_dataset("t…...
kubernetes deploy standalone mysql demo
kubernetes 集群内部署 单节点 mysql ansible all -m shell -a "mkdir -p /mnt/mysql/data"cat mysql-pv-pvc.yaml apiVersion: v1 kind: PersistentVolume metadata:name: mysql-pv-volumelabels:type: local spec:storageClassName: manualcapacity:storage: 5Gi…...
【Map】Map集合有序与无序测试案例:HashMap,TreeMap,LinkedHashMap(121)
简单介绍常用的三种Map:不足之处,欢迎指正! HashMap:put数据是无序的; TreeMap:key值按一定的顺序排序;数字做key,put数据是有序,非数字字符串做key,put数据…...
TiDB Serverless Branching:通过数据库分支简化应用开发流程
2023 年 7 月 10 日,TiDB Serverless 正式商用。这是一个完全托管的数据库服务平台(DBaaS),提供灵活的集群配置和基于用量的付费模式。紧随其后,TiDB Serverless Branching 的测试版也发布了。 TiDB Serverless Branc…...
运用亚马逊云科技Amazon Kendra,快速部署企业智能搜索应用
亚马逊云科技Amazon Kendra是一项由机器学习(ML)提供支持的企业搜索服务。Kendra内置数据源连接器,支持快速访问Amazon S3、AmazonRDS、AmazonFSX以及其他外部数据源,帮助用户自动提取文档并建立索引。Kendra支持超过30多种多国语…...
C# 使用 OleDbConnection 连接读取Excel的方法
Connection类有四种:SqlConnection,OleDbConnection,OdbcConnection和OracleConnection。 (1)Sqlconnetcion类的对象连接是SQL Server数据库; (2)OracleConnection类的对象连接Oracle数据库&…...
【LeetCode-中等题】98. 验证二叉搜索树
文章目录 题目方法一:BFS 层序遍历方法二: 递归方法三: 中序遍历(栈)方法四: 中序遍历(递归) 题目 思路就是首先得知道什么是二叉搜索树 左孩子在(父节点的最小值&#x…...
Leetcode-每日一题【剑指 Offer 37. 序列化二叉树】
题目 请实现两个函数,分别用来序列化和反序列化二叉树。 你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。 …...
删除无点击数据offer数据分析使用
梳理思路: 1、 获取 7month 和 8month fullreport 报表中 所有offer;输出结果:offerid, totalClickCount; 2、 分析数据7month totalClickCount0 and 8month totalClickCount0 的offer去除; result.…...
【Apollo学习笔记】——规划模块TASK之SPEED_BOUNDS_PRIORI_DECIDER
文章目录 前言SPEED_BOUNDS_PRIORI_DECIDER功能简介SPEED_BOUNDS_PRIORI_DECIDER相关配置SPEED_BOUNDS_PRIORI_DECIDER流程将障碍物映射到ST图中ComputeSTBoundary(PathDecision* path_decision)ComputeSTBoundary(Obstacle* obstacle)GetOverlapBoundaryPointsComputeSTBounda…...
物理机ping不通windows server 2012
刚才尝试各种方法,在物理机上就是ping不能wmware中的windows server 2012 . 折腾了几个小时,原来是icmp 被windows server 2012 禁用了 现在使用使用以下协议就能启用Icmp协议。 netsh firewall set icmpsetting 8然后,就能正常ping 通虚…...
誉天HCIE-Datacom丨为什么选择誉天数通HCIE课程学习
大家好,我是誉天HCIE-Datacom的一名学员,在2022年觉得自己技术水平不够,想要提升自己,经朋友介绍在誉天报的名。 听朋友说誉天的阮Sir的课讲的非常好,我在B站上看了几节阮老师的课确实比之前在听得其他机构的课程讲的要…...
Python文本终端GUI框架详解
今天笔者带大家,梳理几个常见的基于文本终端的 UI 框架,一睹为快! Curses 首先出场的是 Curses。 Curses 是一个能提供基于文本终端窗口功能的动态库,它可以: 使用整个屏幕 创建和管理一个窗口 使用 8 种不同的彩色 为程序提供…...
01_lwip_raw_udp_test
1.打开UDP的调试功能 (1)设置宏定义 (2)打开UDP的调试功能 (3)修改内容,串口助手打印的日志信息自动换行 2.电脑端连接 UDP发送一帧数据 3.电路板上发送一帧数据...
学习ts(十一)本地存储与发布订阅模式
localStorage实现过期时间 目录 准备 安装 npm i rollup typescript rollup-plugin-typescript2// tsconfig.json"module": "ESNext","moduleResolution": "node", "strict": false, // rollup.config.js import …...
MySQL对NULL值处理
在使用数据库时,有时需要表示未知值,这时可以使用NULL值表示。引入NULL值后,会对原有的使用产生影响,这里记录下常见的场景,以做记录。 NULL含义 在MySQL中,NULL值表示一个未知值,表示不可知、…...
Vector 动态数组(迭代器)
C数据结构与算法 目录 本文前驱课程 1 C自学精简教程 目录(必读) 2 Vector<T> 动态数组(模板语法) 本文目标 1 熟悉迭代器设计模式; 2 实现数组的迭代器; 3 基于迭代器的容器遍历; 迭代器语法介绍 对迭…...
多组背包恰好装满方案数
链接:登录—专业IT笔试面试备考平台_牛客网 来源:牛客网 现在有一个大小n*1的收纳盒,我们手里有无数个大小为1*1和2*1的小方块,我们需要用这些方块填满收纳盒,请问我们有多少种不同的方法填满这个收纳盒 分析&…...
Oracle查询语句中做日期加减运算
在Oracle中,可以使用日期函数来实现日期的加减。 若想在日期上加上一定的天数,可以使用"INTERVAL"关键字。例如,如果要将一个日期加上3天,可以使用以下代码: SELECT SYSDATE INTERVAL 3 DAY FROM DUAL; …...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
MinIO Docker 部署:仅开放一个端口
MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...
深入理解Optional:处理空指针异常
1. 使用Optional处理可能为空的集合 在Java开发中,集合判空是一个常见但容易出错的场景。传统方式虽然可行,但存在一些潜在问题: // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...
《Docker》架构
文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器,docker,镜像,k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...
FFmpeg avformat_open_input函数分析
函数内部的总体流程如下: avformat_open_input 精简后的代码如下: int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...
【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道
文/法律实务观察组 在债务重组领域,专业机构的核心价值不仅在于减轻债务数字,更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明,合法债务优化需同步实现三重平衡: 法律刚性(债…...
DiscuzX3.5发帖json api
参考文章:PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下,适配我自己的需求 有一个站点存在多个采集站,我想通过主站拿标题,采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...
