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

三道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题

一&#xff1a;1114. 棋盘问题 - AcWing题库 分别枚举行和列&#xff0c;能填的地方就填&#xff0c;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 # 加载示例数据&#xff08;例如&#xff0c;使用seaborn自带的数据集&#xff09; 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&#xff1a;不足之处&#xff0c;欢迎指正&#xff01; HashMap&#xff1a;put数据是无序的&#xff1b; TreeMap&#xff1a;key值按一定的顺序排序&#xff1b;数字做key&#xff0c;put数据是有序&#xff0c;非数字字符串做key&#xff0c;put数据…...

TiDB Serverless Branching:通过数据库分支简化应用开发流程

2023 年 7 月 10 日&#xff0c;TiDB Serverless 正式商用。这是一个完全托管的数据库服务平台&#xff08;DBaaS&#xff09;&#xff0c;提供灵活的集群配置和基于用量的付费模式。紧随其后&#xff0c;TiDB Serverless Branching 的测试版也发布了。 TiDB Serverless Branc…...

运用亚马逊云科技Amazon Kendra,快速部署企业智能搜索应用

亚马逊云科技Amazon Kendra是一项由机器学习&#xff08;ML&#xff09;提供支持的企业搜索服务。Kendra内置数据源连接器&#xff0c;支持快速访问Amazon S3、AmazonRDS、AmazonFSX以及其他外部数据源&#xff0c;帮助用户自动提取文档并建立索引。Kendra支持超过30多种多国语…...

C# 使用 OleDbConnection 连接读取Excel的方法

Connection类有四种:SqlConnection&#xff0c;OleDbConnection&#xff0c;OdbcConnection和OracleConnection。 &#xff08;1&#xff09;Sqlconnetcion类的对象连接是SQL Server数据库&#xff1b; &#xff08;2&#xff09;OracleConnection类的对象连接Oracle数据库&…...

【LeetCode-中等题】98. 验证二叉搜索树

文章目录 题目方法一&#xff1a;BFS 层序遍历方法二&#xff1a; 递归方法三&#xff1a; 中序遍历&#xff08;栈&#xff09;方法四&#xff1a; 中序遍历&#xff08;递归&#xff09; 题目 思路就是首先得知道什么是二叉搜索树 左孩子在&#xff08;父节点的最小值&#x…...

Leetcode-每日一题【剑指 Offer 37. 序列化二叉树】

题目 请实现两个函数&#xff0c;分别用来序列化和反序列化二叉树。 你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑&#xff0c;你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。 …...

删除无点击数据offer数据分析使用

梳理思路&#xff1a; 1、 获取 7month 和 8month fullreport 报表中 所有offer&#xff1b;输出结果&#xff1a;offerid&#xff0c; totalClickCount&#xff1b; 2、 分析数据7month totalClickCount0 and 8month totalClickCount0 的offer去除&#xff1b; 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

刚才尝试各种方法&#xff0c;在物理机上就是ping不能wmware中的windows server 2012 . 折腾了几个小时&#xff0c;原来是icmp 被windows server 2012 禁用了 现在使用使用以下协议就能启用Icmp协议。 netsh firewall set icmpsetting 8然后&#xff0c;就能正常ping 通虚…...

誉天HCIE-Datacom丨为什么选择誉天数通HCIE课程学习

大家好&#xff0c;我是誉天HCIE-Datacom的一名学员&#xff0c;在2022年觉得自己技术水平不够&#xff0c;想要提升自己&#xff0c;经朋友介绍在誉天报的名。 听朋友说誉天的阮Sir的课讲的非常好&#xff0c;我在B站上看了几节阮老师的课确实比之前在听得其他机构的课程讲的要…...

Python文本终端GUI框架详解

今天笔者带大家&#xff0c;梳理几个常见的基于文本终端的 UI 框架&#xff0c;一睹为快&#xff01; Curses 首先出场的是 Curses。 Curses 是一个能提供基于文本终端窗口功能的动态库&#xff0c;它可以: 使用整个屏幕 创建和管理一个窗口 使用 8 种不同的彩色 为程序提供…...

01_lwip_raw_udp_test

1.打开UDP的调试功能 &#xff08;1&#xff09;设置宏定义 &#xff08;2&#xff09;打开UDP的调试功能 &#xff08;3&#xff09;修改内容&#xff0c;串口助手打印的日志信息自动换行 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值处理

在使用数据库时&#xff0c;有时需要表示未知值&#xff0c;这时可以使用NULL值表示。引入NULL值后&#xff0c;会对原有的使用产生影响&#xff0c;这里记录下常见的场景&#xff0c;以做记录。 NULL含义 在MySQL中&#xff0c;NULL值表示一个未知值&#xff0c;表示不可知、…...

Vector 动态数组(迭代器)

C数据结构与算法 目录 本文前驱课程 1 C自学精简教程 目录(必读) 2 Vector<T> 动态数组&#xff08;模板语法&#xff09; 本文目标 1 熟悉迭代器设计模式&#xff1b; 2 实现数组的迭代器&#xff1b; 3 基于迭代器的容器遍历&#xff1b; 迭代器语法介绍 对迭…...

多组背包恰好装满方案数

链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源&#xff1a;牛客网 现在有一个大小n*1的收纳盒&#xff0c;我们手里有无数个大小为1*1和2*1的小方块&#xff0c;我们需要用这些方块填满收纳盒&#xff0c;请问我们有多少种不同的方法填满这个收纳盒 分析&…...

Oracle查询语句中做日期加减运算

在Oracle中&#xff0c;可以使用日期函数来实现日期的加减。 若想在日期上加上一定的天数&#xff0c;可以使用"INTERVAL"关键字。例如&#xff0c;如果要将一个日期加上3天&#xff0c;可以使用以下代码&#xff1a; SELECT SYSDATE INTERVAL 3 DAY FROM DUAL; …...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...

在Spring Boot中集成RabbitMQ的完整指南

前言 在现代微服务架构中&#xff0c;消息队列&#xff08;Message Queue&#xff09;是实现异步通信、解耦系统组件的重要工具。RabbitMQ 是一个流行的消息中间件&#xff0c;支持多种消息协议&#xff0c;具有高可靠性和可扩展性。 本博客将详细介绍如何在 Spring Boot 项目…...

Linux入门(十五)安装java安装tomcat安装dotnet安装mysql

安装java yum install java-17-openjdk-devel查找安装地址 update-alternatives --config java设置环境变量 vi /etc/profile #在文档后面追加 JAVA_HOME"通过查找安装地址命令显示的路径" #注意一定要加$PATH不然路径就只剩下新加的路径了&#xff0c;系统很多命…...

中科院1区顶刊|IF14+:多组学MR联合单细胞时空分析,锁定心血管代谢疾病的免疫治疗新靶点

中科院1区顶刊|IF14&#xff1a;多组学MR联合单细胞时空分析&#xff0c;锁定心血管代谢疾病的免疫治疗新靶点 当下&#xff0c;免疫与代谢性疾病的关联研究已成为生命科学领域的前沿热点。随着研究的深入&#xff0c;我们愈发清晰地认识到免疫系统与代谢系统之间存在着极为复…...