- 2024-08-04【LCA 树上两点的距离 判定点是否在某条边中】洛谷P3398 仓鼠找sugar
题目链接:P3398仓鼠找sugar-洛谷|(luogu.com.cn)题目大意:判定一棵树上的两条边是否相交Tag:[LCA][树上两点间距离的计算][如何判断与点在某条路径上]思路:\[\begin{align}&1.建图\\&2.\text{dfs}然后\计算出每个点的深度和计\text{anc}(i,j)\\&3.根据树上路径
- 2024-05-26无线技术整合到主动噪声控制(ANC)增强噪声降低性能
主动噪声控制(ANC)已成为一种广泛使用的降噪技术。基本原理是通过产生与外界噪音相等的反向声波,将噪音中和,从而达到降噪的效果。ANC系统通常包括以下几个部分:参考麦克风、处理芯片、扬声器和误差麦克风。参考麦克风用于捕捉环境中的噪声信号;处理芯片则分析这些噪声曲线,并
- 2024-04-13P6594 [YsOI2020] 换寝室
P6594[YsOI2020]换寝室树上差分+树形dp题意:给定一棵树,每条边有边权,割掉一些边,使得被割掉的边边权和不超过kk,最小化剩余连通块点权极差的最大值。看到最小化最大值,可以考虑二分。此时二分了\(x\),那么每个连通块的极差都不能超过\(x\)。考虑需要判断是否存在一个连通块的
- 2024-04-12P9433 [NAPC-#1] Stage5 - Conveyors
P9433[NAPC-#1]Stage5-Conveyorslca维护树上路径但是这题不是难在这里,考察的是分析问题答案构成的能力。我们可以从数据范围出发。\(s=t,k=n\)每条边都要走两遍,显然是树上所有边权和\(\times2\)。\(k=n\)可以构造一种走法,使得\(t\)先到\(s\),按照上面的走法走完
- 2024-04-11P9352 [JOI 2023 Final] Cat Exercise
P9352[JOI2023Final]CatExercise树形dp+trick+并查集若我们以当前猫在的位置\(u\)为根,那么猫的下一步移动就会走到其中一个子树中。猫只有在我们把障碍放到当前的位置时才会移动,所以一定无法回到\(u\)点。要指定进入某个子树,只需要把其他子树都堵住即可。考虑树形dp
- 2024-04-06CF613D Kingdom and its Cities
CF613DKingdomanditsCities虚树优化dp考虑无解的情况,若有两个重要城市相邻,那么无解。对于有解的情况,朴素的如何求解最少占领的城市数?考虑从叶子节点开始向上贪心,假如当前\(u\)节点为关键点,那么对于它的子树\(v\),若它的关键点能到\(v\),就要和他断开。如果\(u\)节点不
- 2024-04-06P2495 [SDOI2011] 消耗战
P2495[SDOI2011]消耗战虚树优化dp模板题考虑\(m=1\)。只需要简单的树形dp,设\(f_i\)表示\(i\)子树中的关键点都到不了\(i\)点的最小代价。转移枚举子节点\(v\),有:若\(v\)点为关键点,\(f_u=f_u+w(u,v)\)。否则,\(f_u=f_u+\min(f_v,w(u,v))\)。如果每次询问都跑一遍
- 2024-04-05拓扑排序--有向无环图中一个节点的所有祖先
题目描述给你一个正整数 n ,它表示一个 有向无环图 中节点的数目,节点编号为 0 到 n-1 (包括两者)。给你一个二维整数数组 edges ,其中 edges[i]=[fromi,toi] 表示图中一条从 fromi 到 toi 的单向边。请你返回一个数组 answer,其中 answer[i]是第 i 个节
- 2023-08-08【树论典题。】P6071 『MdOI R1』Treequery
前言:输了,被水杯提醒我一直很失败。正片:简要题意求\([l,r]\top\)的路径的交的边权和。Solution:\(O(n\log^2n)\)巨大分讨做法。考虑分类讨论。其一,\(p\)根本就不属于路径上的点,这个求区间LCA可以解决\(p\toanc_{[l,r]}\)其二,\(p\)是\(anc_{l,r}\)的祖
- 2023-07-05【线段树】 HDOJ 5274 Dylans loves tree
用dfs序构建线段树,然后用lca求出两点间路径的xor和。。。#include<iostream>#include<queue>#include<stack>#include<map>#include<set>#include<bitset>#include<cstdio>#include<algorithm>#include<cstring>#include
- 2023-07-05HDOJ 5296 Annoying problem
根据每次的加点删点求对答案的贡献。。。#include<iostream>#include<queue>#include<stack>#include<map>#include<set>#include<bitset>#include<cstdio>#include<algorithm>#include<cstring>#include<climits&g
- 2023-07-02CF842E Nikita and game 题解
题意一棵树初始只有一个编号为1的根结点。\(n\)次操作,每次新增一个点作为\(p_i\)的子结点,询问更新后有多少点可以作为树直径的端点。\(n\le3\times10^5\)。题解以下\(dist(x,y)\)表示点\(x\)与点\(y\)在树上的距离。不难发现若干条直径必然叠合于至少一点,任选这
- 2023-02-20ANC(Active Noise Control)基础介绍
介绍噪声控制的基本概念 环境中存在两种类型的噪声。一种是由湍流(turbuletnoise)引起的,完全是随机的。湍流噪声将其能量均匀地分布在各个频带上。它被称为
- 2023-02-14 关于北京君正:带ANC的2K网络摄像头用户案例
如果远程办公是您的未来,或者您经常通过视频通话与远方的朋友和亲戚交谈,那么您可以考虑购买网络摄像头以显著改善您的沟通。AnkerPowerConfC200是个不错的选择。深圳市雷龙
- 2022-12-22洛谷P2680 运输计划(LCA + 二分 + 树上边差分)
洛谷P2680运输计划 现在有一棵树,每条树边上都有正权值。接下来,有m个询问,每次询问给出两个结点,这两个结点之间有一条路径。现在你可以任选一条树边,将其边权置为0,请输
- 2022-12-22Codeforces Round #837 (Div. 2)(持续更新)
Preface补题ing上周由于疫情鸽了好多场,趁现在空下来尽量多写点吧A.HossamandCombinatoricsSB题,直接统计下最大的数和最小的数的个数即可注意所有数相同的情况要特
- 2022-10-28洛谷P8805题解
原题P8805[蓝桥杯2022国B]机房思路概述题意分析给定一个\(n\)个点的无根树,每个点的权值等于其出边数量。对于给定的\(m\)组询问,第\(i(1≤i≤n)\)组询问包
- 2022-10-25模板库
2022.10.25:模板库迁移至cnblogs。1.离散化//unordered_map<int,int>b;intb(intx){returnlower_bound(a+1,a+n+1,x)-a;//返回1~r的数}voiddisc
- 2022-10-24 LCA
倍增算法预处理O(nlogn)单次询问O(logn)voiddfs(intu,intfa){ for(inti=hd[u];i;i=g[i].nxt) { intv=g[i].to; if(v==fa) continue; d
- 2022-10-21主动噪声控制(Active Noise Control):宽带前馈ANC
宽带前馈ANC宽带前馈ANC的组成部分有:单个参考传感器(麦克风),单个次级声源,单个误差传感器。这种类型的ANC系统被简化之后的单通道管式ANC系统框图如下图1所示:其中输入信
- 2022-09-30CF1286E
考虑在每次加入一个字符后,求出所有合法后缀(即border)的权值和。容易想到用KMP算法解决。具体的,我们维护border的集合。加入一个字符\(c_i\)后,对集合的改变为:如果
- 2022-09-25【Coel.学习笔记】特殊的图 - 仙人掌与圆方树
你是什么仙人?引入仙人掌是一种特殊的无向图,它的任意一条边至多只出现在一条简单回路(每个点只出现一次的回路是简单回路,特殊地,自环不算简单回路)。这里借用一下[SHOI2006
- 2022-09-04LCA
定义LCA(LeastCommonAncestors),即最近公共祖先,指对于有根树TT的两个结点uu、vv,最近公共祖先LCA(T,u,v)LCA(T,u,v)表示一个结点xx,满足xx是uu、vv的祖先且xx