Codeforces Round 303 (Div. 2)C. Kefa and Park(DFS、实现)
文章目录
- 题面
- 链接
- 题意
- 题解
- 代码
- 总结
题面
链接
C. Kefa and Park
题意
求叶节点数量,叶节点满足,从根节点到叶节点的路径上最长连续1的长度小于m
题解
这道题目主要是实现,当不满足条件时直接返回。
到达叶节点后统计答案,用vector存图的话,无向图时,叶节点的边只有一条,也就是 g [ i ] . s i z e ( ) = = 1 g[i].size()==1 g[i].size()==1而不是0
需要特判是一条链的情况,一条链的话根节点的 g [ i ] . s i z e ( ) = = 1 g[i].size()==1 g[i].size()==1也成立
代码
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_backusing namespace std;
const int N=1e5+10;
vector<int>g[N];
int a[N],ans,n,m;void dfs(int u,int fa,int sum,int maxx){if(maxx>m){ return;}//统计答案if(g[u].size()==1&&max(maxx,sum+a[u])<=m&&u!=1){
// cout<<"----------"<<u<<endl;ans++;return;}for(auto y:g[u]){if(y==fa) continue;if(a[u]==1){if(a[fa]==1){dfs(y,u,sum+1,max(maxx,sum+1));}else{dfs(y,u,1,max(maxx,1*1ll));}}else{dfs(y,u,0,maxx);}}
}void solve()
{cin>>n>>m;rep(i,1,n){cin>>a[i];}rep(i,1,n-1){int u,v;cin>>v>>u;g[u].pb(v);g[v].pb(u);}//当前结点、根节点,目前连续猫数。dfs(1,0,0,0);cout<<ans<<endl;
}signed main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);int _;
// cin>>_;
// while(_--)solve();return 0;
}
总结
这道题目主要是dfs的实现,树的遍历,以及在遍历过程中维护相关信息。同时需要考虑一些细节,特殊情况比如树是一条链。
相关文章:
Codeforces Round 303 (Div. 2)C. Kefa and Park(DFS、实现)
文章目录 题面链接题意题解代码总结 题面 链接 C. Kefa and Park 题意 求叶节点数量,叶节点满足,从根节点到叶节点的路径上最长连续1的长度小于m 题解 这道题目主要是实现,当不满足条件时直接返回。 到达叶节点后统计答案,用…...
797. 差分
Problem: 797. 差分 文章目录 思路解题方法复杂度Code 思路 这是一个差分数组的问题。差分数组的主要适用场景是频繁对原始数组的某一个区间进行增减操作。这种操作是区间修改操作,在这种操作下,差分数组只需要对区间的两个端点进行操作,时间…...
2024.2.5 vscode连不上虚拟机,始终waiting for server log
昨天还好好的,吃着火锅,做着毕设,突然就被vscode给劫了。 起初,哥们跟着网上教程有模有样地删除了安装包缓存,还删除了.vscode-server,发现没卵用,之前都是搜那个弹窗报错。 后来发现原来是vsco…...
CSS基础---新手入门级详解
CSS:层叠样式表 CSS(Cascading Style Sheets,层叠样式表),是一种用来为结构化文档添加样式(字体、间距和颜色)的计算机语言,css扩展名为.css。 实例: <!DOCTYPE html><html> <head><…...
Python中Pymysql库的常见用法和代码示例
关注B站可以观看更多实战教学视频:肆十二-的个人空间-肆十二-个人主页-哔哩哔哩视频 (bilibili.com) pymysql是一个用于连接MySQL数据库的Python库,它允许你执行SQL查询并处理返回的结果。以下是pymysql库的一些常见用法和代码示例: 1. 安装…...
使用 WPF + Chrome 内核实现高稳定性的在线客服系统复合应用程序
对于在线客服与营销系统,客服端指的是后台提供服务的客服或营销人员,他们使用客服程序在后台观察网站的被访情况,开展营销活动或提供客户服务。在本篇文章中,我将详细介绍如何通过 WPF Chrome 内核的方式实现复合客服端应用程序。…...
fastapi mysql 开发restful 3
pip install mysql-connector-python pymysql 数据库链接 创建src目录,里面创建db.py 代码如下: # 导入mysql.connector模块,该模块提供了与MySQL数据库进行连接和交互的功能。 import mysql.connector # 定义一个函数get_db_connectio…...
【Uniapp uni-app学习与快速上手——详细讲解】
Uniapp uni-app学习与快速上手——详细讲解 1. 介绍2. Uni-app 学习资源3. 快速上手4. 开始第一个项目5. 调试和发布 1. 介绍 Uni-app 是一个使用 Vue.js 编写多端应用的前端框架。开发者可以编写一份代码,然后发布到iOS、Android、网页(响应式…...
剑指offer——旋转数组的最小数字
目录 1. 题目描述2. 分析思路2.1 示例分析 3. 更完美的做法 1. 题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3.4,5,1.2}为{1.2,3,4,5}的一个旋转&a…...
盘点数据可视化大屏焦点图十种样式
所谓焦点图就是大屏中居于中心位置的图,是视觉的中心,本位列举了十种焦点图样式供大家参考。 地球作为焦点图 图片来自网络 地图作为焦点图 图片来自网络 城市作为焦点图 图片来自网络 园区做焦点图 图片来自网络 建筑做焦点图 图片来自网络 生产线…...
问题 G: 老鼠和猫的交易
题目描述 小老鼠准备了M磅的猫粮,准备去和看守仓库的猫做交易,因为仓库里有小老鼠喜欢吃的五香豆。 仓库有N个房间; 第i个房间有J[i] 磅的五香豆,并且需要用F[i]磅的猫粮去交换; 老鼠不必交换该房间所有的五香豆&…...
HiveSQL——借助聚合函数与case when行转列
一、条件函数 if 条件函数 if函数是最常用到的条件函数,其写法是if(xn,a,b), xn代表判断条件,如果xn时,那么结果返回a ,否则返回b。 selectif(age < 25 or age is null, 25岁以下, 25岁以上) as age_cnt,count(1) as number from table…...
冒泡排序,判断回文,以及12-24小时制
6-7 定义函数,完成冒泡排序算法。 本题定义一个冒泡排序算法的函数,调用函数后实现数组的升序排序,其数组长度为任意长度。 函数接口定义: 在这里描述函数接口。例如: void sort(int arr[],int n); 在这里解释接口…...
【Vue】computed与watch
📝个人主页:五敷有你 🔥系列专栏:Vue⛺️稳重求进,晒太阳 计算属性 概念:基于现有的数据,计算出来新的属性,依赖的数据变化,自动重新计算 语法: 声明…...
探索设计模式的魅力:捕捉变化的风-用观察者模式提升用户体验
设计模式专栏:http://t.csdnimg.cn/U54zu 目录 一、引言 核心概念 应用场景 可以解决的问题 二、场景案例 2.1 不用设计模式实现 2.2 存在问题 2.3 使用设计模式实现 2.4 成功克服 三、工作原理 3.1 结构图和说明 3.2 工作原理详解 3.3 实现步骤 四、 优…...
SpringCloud-高级篇(十九)
我们已经学过使用 SpringAMQP去收和发消息,但是发和收消息是只是MQ最基本的功能了,在收发消息的过程中,会有很多的问题需要去解决,下面需要学习rabbitMQ的高级特性去解决 死信交换机:这个可以帮助我们实现消息的延迟的…...
Junit常用断言
0.断言简介 断言:assert Q:断言的作用 更方便的对结果进行判定 "有针对性"的if判断 针对两个变量值是否相同 使用assertEquals针对两个对象是否相同 使用assertSame针对返回值是否为True 使用assertTrue 1.断言的参数 assertXXX(”断言失败时提升的信息“&#x…...
docker 实现 mysql:8.3.0 主从复制(2024年2月13日最新版本)
环境为 CentOS 7.6, 具体操作请看MySQL主从复制01-主从复制概述及原理_哔哩哔哩_bilibili 1、配置主服务器 # 启动主服务器 docker run -p 3306:3306 --name mysql_master -e MYSQL_ROOT_PASSWORDnmnmnm67890890 -v /docker/mysql_master/conf:/etc/mysql/conf.d…...
STM32 + ESP8266,连接阿里云 上报/订阅数据
(文章正在编辑中,一点点地截图操作过程,估计要拖拉两三天) 一、烧录MQTT固件 ESP8266出厂时,默认是AT固件。连接阿里云,需要使用MQTT固件。 1、独立EPS8266模块的烧录方法 2、魔女开发板,板载…...
如何利用chatgpt提升工作效率?
在数字化和信息化的时代,人工智能技术已经深入到了我们生活的方方面面。其中,ChatGPT作为当前热门的人工智能技术,以其强大的自然语言处理能力和广泛的应用场景,正逐渐改变着我们的工作方式,为我们提高工作效率提供了全…...
MongoDB聚合:$geoNear
$geoNear根据指定的点按照距离以由近到远的顺序输出文档。 从4.2版本开始,MongoDB移除了limit和num选项以及100个文档的限制,如果要限制结果文档的数量可以使用$limit阶段。 语法 { $geoNear: { <geoNear options> } }$geoNear操作接受一个包含…...
Docker-CE 国内源国内镜像
Docker-CE 就是 Docker Community Edition 的意思 docker-ce由docker官方维护 , docker.io由Debian维护 Docker官文 – Install Docker Engine on CentOS Docker官文 – Install Docker Engine on Fedora Docker官文 – Install Docker Engine on Debian Docker官文 – In…...
【Tauri】(3):使用Tauri1.5版本,进行桌面应用开发,在windows上搭建环境,安装node,rust环境,可以打包成功,使用vite创建应用
1,视频地址: https://www.bilibili.com/video/BV1Ny421a7nA/ 【Tauri】(3):使用Tauri1.5版本,进行桌面应用开发,在windows上搭建环境,安装node,rust环境,可以…...
C++ 堆排序
C 堆排序 堆排序是一种基于二叉堆数据结构的排序算法,其原理如下: 构建最大堆:将待排序的数组看作一个完全二叉树,并通过调整节点的位置构建一个最大堆。最大堆满足每个父节点的值都大于或等于其子节点的值。构建最大堆的过程可以…...
U3D记录之FBX纹理丢失问题
今天费老大劲从blender建了个模型,然后导出进去unity 发现贴图丢失 上网查了一下 首先blender导出要改设置 这个path mode要copy 然后unity加载纹理也要改设置 这里这个模型的纹理load要改成external那个模式 然后就有了,另外这个导出还有好多选项可…...
监测Nginx访问日志502情况后并做相应动作
今天带大家写一个比较实用的脚本哈 原理: 假设服务器环境为lnmp,近期访问经常出现502现象,且502错误在重启php-fpm服务后消失,因此需要编写监控脚本,一旦出现502,则自动重启php-fpm服务 场景: 1…...
【数据分享】1929-2023年全球站点的逐年平均风速(Shp\Excel\免费获取)
气象数据是在各项研究中都经常使用的数据,气象指标包括气温、风速、降水、能见度等指标,说到气象数据,最详细的气象数据是具体到气象监测站点的数据! 有关气象指标的监测站点数据,之前我们分享过1929-2023年全球气象站…...
Android性能调优 - 应用安全问题
Android应用安全 1.组件暴露: 像比如ContentProvider,BroadcastReceiver,Activity等组件有android:exported属性; 如果是私有组件 android:exported “false”; 如果是公有组件 android:exported “true” 且进行权限控制&…...
C#的Char 结构的像IsLetterOrDigit(Char)等常见的方法
目录 一、Char 结构的方法 二、Char.IsLetterOrDigit 方法 1.Char.IsLetterOrDigit(Char)用法 2.IsLetterOrDigit(String, Int32)方法 三、Char.IsLetter 方法 1.IsLetter(Char) 2.IsLetter(String, Int32) 四、Char.IsDigit 方法 1. IsDigit(String, Int32) 2.IsDig…...
部分意图分类【LLM+RAG】
在生成人工智能领域工作最有价值的事情之一就是发现新兴技术如何融入新的解决方案。 举个例子:在为北美顶级金融服务公司之一设计对话式人工智能助手时,WillowTree 的数据和人工智能研究团队 (DART) 发现,将意图分类与大型语言模型 (LLM) 结合…...
1277. 统计全为 1 的正方形子矩阵
1277. 统计全为 1 的正方形子矩阵 题目链接:1277. 统计全为 1 的正方形子矩阵 代码如下: class Solution { public:int countSquares(vector<vector<int>>& matrix) {if(matrix.size()0||matrix[0].size()0) return 0;//dp[i][j]代表…...
Python 3 时间序列可视化指南
简介 时间序列分析属于统计学的一个分支,涉及对有序的、通常是时间性的数据进行研究。当适当应用时,时间序列分析可以揭示意想不到的趋势,提取有用的统计数据,甚至预测未来的趋势。因此,它被应用于许多领域࿰…...
[算法前沿]--059-大语言模型Fine-tuning踩坑经验之谈
前言 由于 ChatGPT 和 GPT4 兴起,如何让人人都用上这种大模型,是目前 AI 领域最活跃的事情。当下开源的 LLM(Large language model)非常多,可谓是百模大战。面对诸多开源本地模型,根据自己的需求,选择适合自己的基座模型和参数量很重要。选择完后需要对训练数据进行预处…...
【Docker】01 Docker安装与配置
文章目录 一、Docker二、离线安装Docker三、联网安装Docker3.1 下载YUM软件库文件3.2 安装epel-release3.3 安装yum-utils3.4 设置镜像仓库3.5 查看docker-ce所有版本3.6 安装Docker3.7 启动Docker3.8 查看Docker信息3.9 启动第一个容器 四、一些配置4.1 登录DockerHub4.2 镜像…...
Unity3d Shader篇(六)— BlinnPhong高光反射着色器
文章目录 前言一、BlinnPhong高光反射着色器是什么?1. BlinnPhong高光反射着色器的工作原理2. BlinnPhong高光反射着色器的优缺点优点缺点 3. 公式 二、使用步骤1. Shader 属性定义2. SubShader 设置3. 渲染 Pass4. 定义结构体和顶点着色器函数5. 片元着色器函数 三…...
Go-zero微服务个人探究之路(十二)定时任务的选择调研
前言 很多时候后台需要做定时任务的需求,笔者的项目采用go-zero框架微服务框架,需要做定时任务,于是做了如下方法调研,共有大概三种主要选择 方案 难度总体由容易到复杂 go的timer库 通过Go的标准库time中的Ticker和Tick功能…...
Java中,List、Map和Set的区别是什么?
在Java中,List、Map和Set是三种常用的集合类型,它们之间的主要区别如下: 1、List List是有序集合,它可以包含重复元素。 List中的元素是按照插入顺序排列的,可以通过索引访问每个元素。 Java中常见的List实现类有A…...
Google刚刚推出了图神经网络Tensorflow-GNN
每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗?订阅我们的简报,深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同,从行业内部的深度分析和实用指南中受益。不要错过这个机会,成为AI领…...
链表基础知识汇总
链表 链表是一种基本的数据结构,是由一系列节点组成的集合。每个节点包含两个部分:值和指向下一个节点的指针。链表中的节点可以动态地添加、删除,其大小可以根据需要进行扩展或缩小。 链表通常用于处理不固定长度的数据结构,具有…...
Educational Codeforces Round 2(远古edu计划)
A. 恶心模拟。。 模拟一下分类即可 数字类,数字0,或者都是数字 字母类,字母空的也是字母,有字母就是字母 #include<bits/stdc.h> #define INF 1e9 using namespace std; typedef long long ll; const int N2e59; strin…...
【Tauri】(1):使用Tauri1.5版本,进行桌面应用开发,在windows,linux进行桌面GUI应用程序开发,可以打包成功,使用 vite 最方便
1,视频地址: https://www.bilibili.com/video/BV1Pz421d7s4/ 【Tauri】(1):使用Tauri1.5版本,进行桌面应用开发,在windows,linux进行桌面GUI应用程序开发,可以打包成功&…...
「Linux」软件安装
MySQL5.7在CentOS安装 安装 配置yum仓库 更新密钥:rpm --import https://repo.mysql.com/RPM-GPG-KEY-mysql-2022安装MySQL yum库:rpm -Uvh http://repo.mysql.com//mysql57-community-release-el7-7.noarch.rpm使用yum安装MySQL:yum -y in…...
Ubuntu Desktop - Terminal 输出全部选中 + 复制
Ubuntu Desktop - Terminal 输出全部选中 复制 1. Terminal2. Terminal 最大化3. Edit -> Select All4. Copy & PasteReferences 1. Terminal 2. Terminal 最大化 3. Edit -> Select All 4. Copy & Paste Edit -> Copy or Shift Ctrl C Edit -> Paste…...
Java 三大并大特性-可见性介绍(结合代码、分析源码)
目录 编辑 一、可见性概念 1.1 概念 二、可见性问题由来 2.1 由来分析 三、可见性代码例子 3.1 代码 3.2 执行结果 四、Java 中保证可见性的手段 4.1 volatile 4.1.1 优化代码 4.1.2 测试结果 4.1.3 volatile原理分析 4.1.3.1 查看字节码 4.1.3.2 hotspot 层面…...
【漏洞复现】狮子鱼CMS某SQL注入漏洞01
Nx01 产品简介 狮子鱼CMS(Content Management System)是一种网站管理系统,它旨在帮助用户更轻松地创建和管理网站。该系统拥有用户友好的界面和丰富的功能,包括页面管理、博客、新闻、产品展示等。通过简单直观的管理界面…...
《Java 简易速速上手小册》第6章:Java 并发编程(2024 最新版)
文章目录 6.1 线程的创建和管理 - 召唤你的士兵6.1.1 基础知识6.1.2 重点案例:实现一个简单的计数器6.1.3 拓展案例 1:定时器线程6.1.4 拓展案例 2:使用 Executor 框架管理线程 6.2 同步机制 - 维持军队的秩序6.2.1 基础知识6.2.2 重点案例&a…...
C++初阶:容器(Containers)list常用接口详解
介绍完了vector类的相关内容后,接下来进入新的篇章,容器list介绍: 文章目录 1.list的初步介绍2.list的定义(constructor)3.list迭代器( iterator )4.string的三种遍历4.1迭代器4.2范围for循环 5…...
HARRYPOTTER: FAWKES
攻击机 192.168.223.128 目标机192.168.223.143 主机发现 nmap -sP 192.168.223.0/24 端口扫描 nmap -sV -p- -A 192.168.223.143 开启了21 22 80 2222 9898 五个端口,其中21端口可以匿名FTP登录,好像有点说法,百度搜索一下发现可以用anonymous登录…...
嵌入式Qt 第一个Qt项目
一.创建Qt项目 打开Qt Creator 界面选择 New Project或者选择菜单栏 【文件】-【新建文件或项目】菜单项 弹出New Project对话框,选择Qt Widgets Application 选择【Choose】按钮,弹出如下对话框 设置项目名称和路径,按照向导进行下一步 选…...
【OpenHarmony硬件操作】风扇与温湿度模块
文章目录 前言一、串行通信是什么二、IC2.1 IC是什么2.2 IC涉及到的线2.3 IC的时序三、风扇的操作3.1 关于 pcf85743.2 风扇的接口函数IO拓展芯片的定义初始化PCF8574初始化 IO拓展版的引脚属性开启和关闭风扇读状态四、温湿度传感器的使用4.1 初始化温湿度传感器</...