牛客周赛30

思路:先把x, y除以最大公约数变成最小值,然后同时乘以倍数cnt,只记录两个数都在[l,r]间的倍数。

代码:

int gcd(int a,int b){
	return b ? gcd(b, a % b) : a;
}

void solve(){
	int x, y, l, r;
	cin >> x >> y >> l >> r;
	int g = gcd(x, y);
	x /= g,y /= g;
	int ans = 0, cnt = 1;
    while(x * cnt < l || y * cnt < l)
        cnt ++;
	while(x * cnt <= r && y * cnt <= r)
		ans ++, cnt++;
	cout << ans << endl;
}

思路:从下往上dfs,树形dp;

代码:

int n;
vector<int>e[200010];
int f[200010][2];//0 1分别代表红,不染红

void dfs(int u,int fa){
	int m1 = 1, m2 = 1;
	for(auto v:e[u]){
		if(v == fa)continue;
		dfs(v, u);
		m1 = (m1 * (f[v][0])) % mod;      //u节点不染红的话,就需要每个子节点都染红
		m2 = (m2 * (f[v][0] + f[v][1]))%mod;  //u节点染红的话,子节点染不染红都可以
	}
	f[u][0] = m2;        //u节点染红的方案数
	f[u][1] = m1;        //u节点不染红的方案数
}

void solve(){
	cin >> n;
	for(int i = 1;i < n;i ++){
		int u, v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1, 0);
	cout <<(f[1][0] + f[1][1])%mod;      //输出根节点的总方案数
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/354670.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

两两交换链表中的结点---链表OJ

https://leetcode.cn/problems/swap-nodes-in-pairs/description/?envType=study-plan-v2&envId=top-100-liked 1、递归 创建newhead = head->next,然后将head->next->next作为递归参数,返回值用head->next接收;递归结束条件是:没有结点或者只有一…

Python代码耗时统计

time模块 在代码执行前后各记录一个时间点&#xff0c;两个时间戳相减即程序运行耗时。这种方式虽然简单&#xff0c;但使用起来比较麻烦。 time.time() 函数返回的时间是相对于1970年1月1日的秒数 import timestart time.time() time.sleep(1) end time.time() print(f&…

洛谷 P2150 [NOI2015] 寿司晚宴

P2150 [NOI2015] 寿司晚宴 约定&#xff1a; n ≤ 500 n \leq 500 n≤500 题意 给定 2 → n 2 \rightarrow n 2→n 共 n − 1 n-1 n−1 个数字&#xff0c;现在两个人想分别取一些数字&#xff08;不一定全取完&#xff09;&#xff0c;如果他们两人取的数字中存在&#xf…

05. java线程基础

05. java线程基础 01. 线程相关概念 1. 程序 ​ 是为完成特定任务、用某种语言编写的一组指令的集合。简单来说&#xff1a;就是我们写的代码 2. 进程 进程是指运行中的程序&#xff0c;比如我们使用微信&#xff0c;就启动了一个进程&#xff0c;操作系统会为该进程分配内…

【代码随想录】LC 242. 有效的字母异位词

文章目录 前言一、题目1、原题链接2、题目描述 二、解题报告1、思路分析2、时间复杂度3、代码详解 前言 本专栏文章为《代码随想录》书籍的刷题题解以及读书笔记&#xff0c;如有侵权&#xff0c;立即删除。 一、题目 1、原题链接 242. 有效的字母异位词 2、题目描述 二、解题…

一文理清楚-Docker 容器如何工作

Docker 容器如何工作 集装箱什么是虚拟机&#xff1f;虚拟化如何运作&#xff1f;什么是容器&#xff1f;什么是 Docker&#xff1f;总结 五星上将麦克阿瑟曾经说过&#xff1a;在docker面前&#xff0c;虚拟机就是个弟弟 集装箱 《盒子&#xff1a;集装箱如何让世界变得更小&…

剑指offer——删除链表的节点

题目描述&#xff1a;给定单向链表的头指针和一个要删除的节点的值&#xff0c;定义一个函数删除该节点。返回删除后的链表的头节点。 数据范围&#xff1a; 0 <链表节点值 < 10000 0 <链表长度 < 10000 示例1&#xff1a; 输入&#xff1a;{2,5,1,9}&#xff…

1.28寒假集训

A: 解题思路&#xff1a; 移项就好v mv / (M - m) 下面是c代码&#xff1a; #include<iostream> using namespace std; int main() {int t;double M,m,v;cin >> t;while(t ! 0){cin >> M >> m >> v;printf("%.2lf\n",(m * v) / (M…

数据库之 基础概念、安装mysql、sql语句基础

数据库之 基础概念、安装mysql、sql语句基础 【一】存储数据的演变过程&#xff1a; 文件存储&#xff1a; 初始阶段随意存放数据到文件&#xff0c;格式任意。目录规范引入&#xff1a; 软件开发使用目录规范&#xff0c;限制数据位置&#xff0c;建立专门文件夹。本地数据存…

Linux报 “no route to host” 异常 ping: sendmsg: No route to host

公司有台服务器迁移机房后跟另一台服务器相互ping不通&#xff0c;但是两台服务器都能上网能ping其他机器&#xff0c;其他机器都能ping通这两台服务器。检查两台服务器没有防火墙规则拦截&#xff0c;交换机上也没检查到acl过滤。 下图是迁移机房的服务器ping截图 下图是nfs服…

分布式空间索引了解与扩展

目录 一、空间索引快速理解 &#xff08;一&#xff09;区域编码 &#xff08;二&#xff09;区域编码检索 &#xff08;三&#xff09;Geohash 编码 &#xff08;四&#xff09;RTree及其变体 二、业内方案选取 三、分布式空间索引架构 &#xff08;一&#xff09;PG数…

腾讯云幻兽帕鲁4核16G14M服务器性能测评和价格

腾讯云幻兽帕鲁服务器4核16G14M配置&#xff0c;14M公网带宽&#xff0c;限制2500GB月流量&#xff0c;系统盘为220GB SSD盘&#xff0c;优惠价格66元1个月&#xff0c;277元3个月&#xff0c;支持4到8个玩家畅玩&#xff0c;地域可选择上海/北京/成都/南京/广州&#xff0c;腾…

通讯录项目(终)

Start And Stick 上一期我们将通讯录的项目的基本功能已经实现&#xff0c;这一篇文章我们将对通讯录进行完善。 目录 Start And Stick 上期回顾&#xff1a; 上期必要代码&#xff1a; 数据打印&#xff1a; 代码讲解&#xff1a; 头部插入数据&#xff1a; 代码讲解&…

27.1K Star,优雅的JSON 数据可视化工具

Hi&#xff0c;骚年&#xff0c;我是大 G&#xff0c;公众号「GitHub指北」会推荐 GitHub 上有趣有用的项目&#xff0c;一分钟 get 一个优秀的开源项目&#xff0c;挖掘开源的价值&#xff0c;欢迎关注。 想自己之前做 APP 开发会访问后端数据&#xff0c;这个数据就是 JSON …

【网络基础】网络协议传输层UDP和TCP

UDP 解包和分用 解包&#xff08;解析数据包&#xff09; 捕获数据包&#xff1a;首先&#xff0c;接收端的网络栈捕获UDP数据包。检查目的端口&#xff1a;接收端检查数据包头部的目的端口&#xff0c;以确定哪个应用程序应该接收该数据包。验证校验和&#xff1a;接收端可能…

【排序5】基数排序:数字的组织与整理艺术

&#x1f3a1;基数排序 &#x1f38a;1、基本思想&#x1f38a;2、基本步骤&#x1f38a;3、代码示例&#x1f38a;4、特性总结 &#x1f38a;1、基本思想 基数排序&#xff08;Radix Sort&#xff09;是一种非比较排序算法&#xff0c;它根据数字的每一位来对元素进行排序。它…

2024年数学建模美赛C题(预测 Wordle)——思路、程序总结分享

1: 问题描述与要求 《纽约时报》要求您对本文件中的结果进行分析&#xff0c;以回答几个问题。 问题1&#xff1a;报告结果的数量每天都在变化。开发一个模型来解释这种变化&#xff0c;并使用您的模型为2023年3月1日报告的结果数量创建一个预测区间。这个词的任何属性是否会…

Java TemporalAdjusters 时间调节器

提供了非常多处理日期相关的函数&#xff1a; 使用示例&#xff1a; /*** JCccc* param args*/public static void main(String[] args) {DateTimeFormatter pattern DateTimeFormatter.ofPattern("yyyy-MM-dd");LocalDateTime now LocalDateTime.now();//获取当月…

web前端项目-实现录音功能【附源码】

录音功能 运行效果&#xff1a;本项目可实现录音软件的录音、存储、播放等功能 HTML源码&#xff1a; &#xff08;1&#xff09;index.html&#xff1a; <!DOCTYPE html> <html><head><meta http-equiv"Content-Type" content"text/h…

java日志框架总结(三 、Log4j日志框架)

一、简介 Log4j ( Logger For Java ) , Java 日志的记录包。 官方网站 。Log4j 是 Apache 的一个开源项目&#xff0c; 为Java提供了日志记录功能。能够让程序员非常方便的记录日志&#xff0c; 并且提供了多种适配方式&#xff0c;能满足各种需求。 使用Log4j 只需要导入一个…