首页 > 其他分享 >不知道记哪的小tips

不知道记哪的小tips

时间:2024-06-20 16:32:22浏览次数:26  
标签:cnt 半边 奇数 ++ 可以 大小 tips 知道

Tips

  1. 对于\(a_i\le n\),可以连边\((i,a_i)\),然后就变成一棵内向基环树森林

  2. 一种图论题目可以把边挂在点上(可以挂一半,也可以挂全部),当然也可以把点权挂在边上

  3. 要求图的度都为奇数,等价于要求图的连通块大小都为偶数

    证明:

    必要性:反证,考虑若有一个连通块大小奇数,那么图的总度数为奇数,不成立,证毕

    充分性:若有把一个偶数大小连通块变成树,一个点若有奇数个儿子,就断父亲的边,否则就上传,可以发现上传的子树大小为奇数,独立的子树大小为偶数,所以到根节点的度一定为奇数,证毕

  4. 动态判断图是否为二分图,把每个点拆成两个\(x_1,x_2\),然后用可撤回并查集交叉连边,若\(x_1,x_2\)联通,则不是二分图

  5. 全局+整数,可以离线下来,变成全局+非负数

  6. a[++cnt]=b[cnt]=x要慎用,linux下好像等价于b[cnt]=x,a[++cnt]=x,但在windows下是a[++cnt]=x,b[cnt]=x

    • 补充:a[x]=a[++x]或者a[x]=a[--x]也要慎用(其实是不能用,2024.1.25又因为它调了1h)
  7. 如链覆盖的网络流模型,如果有类似但无法处理的问题,可以考虑转化为费用流(如k条互不相交的链最多覆盖几个点)

  8. dp中出现了偏序关系可以考虑分治,先处理左半边,然后把左半边贡献在右半边,在处理右半边

  9. 当dp出现枚举子集\(O(3^n)\)时,用sosdp优化成\(n2^n\),巧妙利用高维前缀和、差分

  10. 最大流转最小割:ABC332G,芙蓉王(源)

  11. \(max(a_i,a_{i+1},a_{i+2})-min(a_i,a_{i+1},a_{i+2})\)可以转化为\(b_i=a_i-a_{i+1},max(|b_i|,|b_{i+1}|,|b_i+b_{i+1}|)\)

  12. 树上有很多问题,如背包...,跟子树大小(或叶子节点个数)有关,而且子树大小相等时贡献一样时,可以发现最多只有 \(\sqrt n\) 种

  13. 排列的容斥:

    \[(|S|=n的方案数)-(|S|=n-1的方案数)+(|S|=n-2的方案数)... \]

  14. \[\sum_{i=1}^n \frac 1i=\ln n+C\\ \sum_{i=1}^n \frac 1{i^2}=\frac{\pi^2}6 \]

  15. 如同统计答案和,方案数的dp,我们常把它相乘进行转移,计算期望和概率也是这个原理

  16. 有向强连通图中最小平均权值回路:一种简单做法,01分数规划+SPFA判负环

标签:cnt,半边,奇数,++,可以,大小,tips,知道
From: https://www.cnblogs.com/zhy114514/p/18258946

相关文章

  • 单细胞测序最好的教程(十六):关于RNA速率你想知道的都在这
    作者按本章节详细讲解了基于RNA速率的三种拟时序模型,包括稳态模型,EM模型和深度学习模型,并对比了不同模型的适用场景与计算特点。本教程首发于单细胞最好的中文教程,未经授权许可,禁止转载。全文字数|预计阅读时间:5000|10min——Starlitnightly(星夜)5.2RNA速率1.背景单细......
  • 大型语言模型的“不知道”:一种新的不确定性敏感训练方法
    大型语言模型(LLMs)在各种任务中展现出惊人的能力,但仍然面临着诸如幻觉等挑战。幻觉是指LLMs生成与事实不符或毫无意义的响应。造成幻觉的一个潜在原因是缺乏相关知识或上下文。因此,一个很有前景的解决方案是指示LLMs在问题超出其知识范围或提供的上下文时,回答“我不知道”。......
  • 我们仍未知道那天所看见的求和法的名字
    TheMethodofSnakeOil进行组合求和的蛇油法。确定求和所依赖的自由变量,例如\(n\)。为您正在处理的求和命名;称之为\(f_n\)。让\(F(x)\)成为\(f(n)\)的生成函数,即您想要求和的和。将和乘以\(x^n\),然后对\(n\)求和。您的生成函数现在表示为对\(n\)的双重求和,以及......
  • 硬盘几个关键指标你一定要知道!
    硬盘是数据中心中存储数据的重要部件,其关键指标影响硬盘的性能、可靠性和适用性。以下是一些常见的硬盘关键指标,并附上详细解释和举例:容量(Capacity)解释:硬盘的容量指其能存储数据的总量,通常以GB(千兆字节)或TB(太字节)为单位。举例:一个1TB的硬盘可以存储大约250,000张照片(假......
  • 国产数据库介绍~目前最火的五款国产数据库,看看都知道哪些?
    一、TiDB:分布式NewSQL数据库简介TiDB是一款开源的分布式NewSQL数据库,由PingCAP公司开发。它采用了分布式事务和强一致性的设计理念,结合了传统关系型数据库和NoSQL的优点,能够满足高并发、大规模数据存储和实时分析的需求。优点分布式架构:TiDB采用分布式架构,可以水平扩展,支......
  • 正则表达式,你不知道的先行断言与后行断言
    正则表达式可以分为两个主要部分:标记和修饰符:标记(Token):是正则表达式的基本构建块,它们表示具体的字符文字、元字符、字符类别、重复限定符、边界匹配、分组和捕获等;修饰符(Modifier):是用来修改正则表达式的匹配行为的标志,例如忽略大小写、全局匹配、多行模式等。修饰符可以影......
  • 【90%人不知道的状态识别/故障诊断新方法】注意熵Attention Entropy及其5种多尺度熵-M
    目录引言数据集特征提取分类器诊断流程友情提示Matlab代码下载点击链接跳转:引言注意熵(AttentionEntropy,翻译可能不准确哈,请谅解)于2023年发表在顶级期刊IEEEtrans系列-IEEETransactionsonAffectiveComputing(影响因子:11.2)。注意熵首次提出并运用于心跳间隔时......
  • uniapp 随笔 各位同学如果uniapp有问题,请留言,我有时间,我会去做一下,将解答的操作会
    1. up-popup弹窗后禁止底层的页面继续滚动   直接在u-popup包一个view然后加上一个方法@touchmove.stop.prevent="prevent"  然后在方法prevent加一个空方法就行了  代码如下:     <viewclass="my"@touchmove.stop.prevent="prevent">  ......
  • 我不允许你们不知道,这么优秀的开源项目!smart-admin
    概述都2024年了,我不允许你们不知道的优秀开源项目,他是国内首个满足网络安全数据安全三级等保支持登录限制支持加解密等等一系列安全措施的开源项目!这个开源项目叫smart-admin是由1024创新实验室开发的。官网官网地址:https://smartadmin.vip/源码地址:https://gi......
  • PYTHON学习过程中的一些有用tips.
    开头语大家好,我是小安同学,我是大一开始学习python,面对这一门陌生的语言中间有许多的弯路,希望可以对大家的学习有所帮助。目前Python可以说是非常流行,在目前的编程语言中,Python的抽象程度是最高的,是最接近自然语言的,很容易上手。你可以用它来完成很多任务,比如数据科学、机器学......