首页 > 其他分享 >CF Garphs

CF Garphs

时间:2022-11-01 12:55:23浏览次数:67  
标签:leftarrow sum Garphs CF 叶子 节点

CF746G New Roads

构造题。
显然优先满足强制叶子节点的限制,设第 \(i\) 层叶节点数 \(b_i\) 。考虑到 \(a_i>a_{i+1}\) 则必有第 \(i\) 层 \(b_i\leftarrow a_i-a_{i+1}\) 个点强制为叶子节点,钦定叶子节点后 \(a_i\leftarrow a_i-b_i, k\leftarrow k -\sum{}^{} b_i\) ,显然序列 \(a\) 为单调不降序列。
此时还需钦定 \(k\) 个叶节点,第 \(i\) 层仍有 \(a_i\) 个节点状态待定,我们只需从 \(\sum_{}^{} a_i\) 个待定节点选取 \(k\) 个作为叶节点即可。
时间复杂度 \(\mathcal{O}(n)\)
代码

标签:leftarrow,sum,Garphs,CF,叶子,节点
From: https://www.cnblogs.com/CAL522/p/CF_Graphs_Records.html

相关文章

  • CF1743E FTL(哈希,DP)——关于 xorshift 的哈希冲突
    CF1743EFTL有两把laser枪,一把伤害\(p_0\)两发间隔时间至少\(t_0\),另一把\(p_1,t_1\)。打敌方太空船,血量\(N\)防御值\(s\),如果某个时刻你对太空船打出\(P\)的......
  • CF809C
    思路转化题意注意到这个“没有出现过的最小正整数”很不舒服。改定义:\[b_{x,y}=a_{x+1,y+1}-1\]则我们有\[b_{x,y}=\operatorname{mex}(\{b_{x,k}|0\lek<y\}\cup\{b......
  • USB_CfgTypeDef
    /** *@brief USBInitializationStructuredefinition */typedefstruct{ uint32_tdev_endpoints;          /*!<DeviceEndpointsnumber.   ......
  • 【五期杨志】CCF-A(NeurIPS'20) Self-supervised multimodal versatile networks
    AlayracJB,RecasensA,SchneiderR,etal.Self-supervisedmultimodalversatilenetworks[J].AdvancesinNeuralInformationProcessingSystems,2020,33:2......
  • CF585E
    令\(s_n\)表示最大公因数恰好为\(n\)的集合个数,\(f_n\)表示与\(n\)互质的数的个数。那么我们要求的就是\(\sum_is_if_i\)。考虑求出\(s\)和\(f\)。考虑计算......
  • 【CF1292F】Nora's Toy Boxes(状压DP)
    考虑将点分为$A,B$两类。其中$[x\inA]\iff\exists_{y\neqx},y|x$。那么我们删去的点只可能在$B$类中,且当前$x\inB$可删当且仅当存在$y\inB,z\inA$使得$z|x......
  • 单片机 STM32 HAL PCF8574 例子代码
    #include"extgpio.h"#include"pcf8574.h"#include"74hc595.h"/******************笔记:1、X输入Y输出2、NPN(箭头向下)高电平时导通,PNP(箭头向上)低电平时导通;3、PCF8574......
  • CF487E Tourists(Tarjan,圆方树,树链剖分,线段树)
    CF487ETourists带权无向图\(N,M\),\(Q\)次询问\(s,t\)所有不经过重复点可能路径经过的最小值的最小值。CODE每次修改一个圆点\(u\)周围的方点有点难。可是李神......
  • cf
    10.31DivisibilitybyEight(1500)题目大意:给你一个不包含前导0的整数,位数100位,问是否可以在通过删除一些位数,且不能改变原有位置的情况下整除8?解题思路:我们可以发现1000......
  • CF149D Coloring Brackets
    题意:给出一串合法括号,按以下规则给括号染色:1.每个符号可以染红色、蓝色,或者不染色;2.相邻两个符号不能染同一种颜色,可以都不染色;3.一对括号有且仅有一个符号染色。求......