C 游游的二进制树
题目描述
游游拿到了一棵树,共有nnn个节点,每个节点都有一个权值:0或者1。这样,每条路径就代表了一个二进制数。
游游想知道,有多少条路径代表的二进制数在[l,r][l,r][l,r]区间范围内?
(请注意:路径长度至少为1,例如,节点3到节点3虽然有一个权值,但并不是合法路径!)
输入描述:
第一行输入三个正整数n,l,r用空格隔开。 第二行输入一个长度为n的01串,第i个字符代表i号节点的权值。 接下来的n−1行,每行输入两个正整数u和v,代表u号节点和v号节点有一条边连接。 1≤n≤103 1≤u,v≤n 1≤l≤r≤1014
输出描述:
一个整数,代表合法的路径条数。
示例1
输入
4 4 5 1010 1 2 2 3 3 4
输出
3
说明
路径1-2-3代表的二进制数为5。
路径3-2-1代表的二进制数为5。
路径4-3-2-1代表的二进制数为5。
示例2
输入
3 1 2 100 1 2 1 3
输出
6
说明
任意合法路径均在区间[l,r]内。
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<long long>h[N];
string s;
long long n,l,r,ans;void dfs(int u,int fa,long long mid){mid=mid*2+s[u-1]-'0'; //每次加上该点位的权值 if(mid>r)return; //如果大于r则该路径不合法,退出递归 if(fa&&mid>=l)ans++; //fa代表节点数 fa大于1代表最少2个节点 for(int v:h[u]){ //if(fa==v)continue;//不合法了,节点不会回头 dfs(v,u,mid); //遍历以这一个节点的第一个值为节点的路径 }
}int main(){cin>>n>>l>>r>>s;for(int i=1;i<n;i++){int x,y;cin>>x>>y;h[x].push_back(y); //可以存储以一个数为起点,能达到的所有点 h[y].push_back(x);}for(int i=1;i<=n;i++)dfs(i,0,0); //从第一个点开始查询,搜索所有以该点为起点的路径 cout<<ans<<endl;return 0;
}
相关文章:
C 游游的二进制树
题目描述 游游拿到了一棵树,共有nnn个节点,每个节点都有一个权值:0或者1。这样,每条路径就代表了一个二进制数。 游游想知道,有多少条路径代表的二进制数在[l,r][l,r][l,r]区间范围内? (请注意…...
收发存和进销存有什么区别?
一、什么是收发存和进销存 1、收发存 收发存是供应链管理中的关键概念,用于描述企业在供应链中的物流和库存管理过程。 收发存代表了企业在采购、生产和销售过程中的物流活动和库存水平。 收(Receiving) 企业接收供应商送达的物料或产品…...
小程序 账号的体验版正式版的账号信息及相关配置
siteinfo.js // 正式环境 const releaseConfig {appID: "",apiUrl: "",imgUrl: "" }; // 测试环境(包含开发环境和体验环境) const developConfig {appID: "",apiUrl: "",imgUrl: "" }…...
AIGC(Artificial Intelligence Generated Content)和 Web3对比,未来发展
一、AIGC(Artificial Intelligence Generated Content)行业 历史背景 AIGC(Artificial Intelligence Generated Content)是指利用人工智能技术生成的内容。随着人工智能技术的不断发展,AIGC 行业逐渐兴起。早期的 AIG…...
机器学习之Boosting和AdaBoost
1 Boosting和AdaBoost介绍 1.1 集成学习 集成学习 (Ensemble Learning) 算法的基本思想就是将多个分类器组合,从而实现一个预测效果更好的集成分类器。 集成学习通过建立几个模型来解决单一预测问题。它的工作原理是生成多个分类器/模型,各自独立地学…...
汇编语言预定义寄存器和协处理器
ARM汇编器对ARM的寄存器和协处理器进行了预定义(包括APCS对r0~r15寄存器的定义),所有的寄存器和协处理器名都是大小写敏感的。 (1)预定义寄存器名 下面列出了被ARM汇编器预定义的寄存器名。 r0ÿ…...
【前缀和】974. 和可被 K 整除的子数组
Halo,这里是Ppeua。平时主要更新C,数据结构算法,Linux与ROS…感兴趣就关注我bua! 974. 和可被 K 整除的子数组 题目:示例:题解: 题目: 示例: 题解: 本题与560.和为K的子数组高度相似 同样的,本题利用了前缀和的定理.当(pre[i]-…...
linux页框回收之shrink_node函数源码剖析
概述 《Linux内存回收入口_nginux的博客-CSDN博客》前文我们概略的描述了几种内存回收入口,我们知道几种回收入口最终都会调用进入shrink_node函数,本文将以Linux 5.9源码来描述shrink_node函数的源码实现。 函数调用流程图 scan_control数据结构 str…...
网络运维基础问题及解答
前言 本篇文章是对于网络运维基础技能的一些常见问题的解答,希望能够为进行期末复习或者对网络运维感兴趣的同学或专业人员提供一定的帮助。 问题及解答 1. 列举 3 种常用字符编码,简述怎样在 str 和 bytes 之间进行编码和解码。 答:常用的…...
【RabbitMQ】之保证数据不丢失方案
目录 一、数据丢失场景二、数据可靠性方案 1、生产者丢失消息解决方案2、MQ 队列丢失消息解决方案3、消费者丢失消息解决方案 一、数据丢失场景 MQ 消息数据完整的链路为:从 Producer 发送消息到 RabbitMQ 服务器中,再由 Broker 服务的 Exchange 根据…...
插入排序算法
插入排序 算法说明与代码实现: 以下是使用Go语言实现的插入排序算法示例代码: package mainimport "fmt"func insertionSort(arr []int) {n : len(arr)for i : 1; i < n; i {key : arr[i]j : i - 1for j > 0 && arr[j] > …...
Linux标准库API
目录 1.字符串函数 2.数据转换函数 3.格式化输入输出函数 4.权限控制函数 5.IO函数 6.进程控制函数 7.文件和目录函数 1.字符串函数 2.数据转换函数 3.格式化输入输出函数 #include<stdarg.h>void test(const char * format , ...){va_list ap;va_start(ap,format…...
腾讯云—自动挂载云盘
腾讯云,稍微麻烦了点。 腾讯云服务器,镜像为opencloudos 8。 ### 1、挂载云盘bash #首先通过以下命令,能够看到新的数据盘,如果不能需要通过腾讯云控制台卸载后,重新挂载,并重启服务器。 fdisk -l#为 /dev…...
为Win12做准备?微软Win11 23H2将集成AI助手:GPT4免费用
微软日前确认今年4季度推出Win11 23H2,这是Win11第二个年度更新。 Win11 23H2具体有哪些功能升级,现在还不好说,但它会集成微软的Copilot,它很容易让人想到多年前的“曲别针”助手,但这次是AI技术加持的,Co…...
Opencv Win10+Qt+Cmake 开发环境搭建
文章目录 一.Opencv安装二.Qt搭建opencv开发环境 一.Opencv安装 官网下载Opencv安装包 双击下载的软件进行解压 3. 系统环境变量添加 二.Qt搭建opencv开发环境 创建一个新的Qt项目(Non-Qt Project) 打开创建好的项目中的CMakeLists.txt,添加如下代码 # openc…...
Matlab实现光伏仿真(附上30个完整仿真源码)
光伏发电电池模型是描述光伏电池在不同条件下产生电能的数学模型。该模型可以用于预测光伏电池的输出功率,并为优化光伏电池系统设计和控制提供基础。本文将介绍如何使用Matlab实现光伏发电电池模型。 文章目录 1、光伏发电电池模型2、使用Matlab实现光伏发电电池模…...
JSON.stringify()与JSON.parse()
JSON.parse() 方法用来解析 JSON 字符串 onst json {"result":true, "count":42}; const obj JSON.parse(json); console.log(typeof(json)) //string console.log(typeof(obj)) //objJSON.stringify() 方法将一个 JavaScript 对象或值转换为 JSON 字…...
neo4j教程-安装部署
neo4j教程-安装部署 Neo4j的关键概念和特点 •Neo4j是一个开源的NoSQL图形存储数据库,可为应用程序提供支持ACID的后端。Neo4j的开发始于2003年,自2007年转变为开源图形数据库模型。程序员使用的是路由器和关系的灵活网络结构,而不是静态表…...
网络面试合集
传输层的数据结构是什么? 就是在问他的协议格式:UDP&TCP 2.1.1三次握手 通信前,要先建立连接,确保双方都是在线,具有数据收发的能力。 2.1.2四次挥手 通信结束后,会有一个断开连接的过程࿰…...
java+springboot+mysql智慧办公OA管理系统
项目介绍: 使用javaspringbootmysql开发的智慧办公OA管理系统,系统包含超级管理员,系统管理员、员工角色,功能如下: 超级管理员:管理员管理;部门管理;职位管理;员工管理…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...
论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing
Muffin 论文 现有方法 CRADLE 和 LEMON,依赖模型推理阶段输出进行差分测试,但在训练阶段是不可行的,因为训练阶段直到最后才有固定输出,中间过程是不断变化的。API 库覆盖低,因为各个 API 都是在各种具体场景下使用。…...
【实施指南】Android客户端HTTPS双向认证实施指南
🔐 一、所需准备材料 证书文件(6类核心文件) 类型 格式 作用 Android端要求 CA根证书 .crt/.pem 验证服务器/客户端证书合法性 需预置到Android信任库 服务器证书 .crt 服务器身份证明 客户端需持有以验证服务器 客户端证书 .crt 客户端身份…...
