首页 > 其他分享 >杂记

杂记

时间:2023-02-21 09:00:47浏览次数:25  
标签:题目 分块 复杂度 杂记 lca 线段 DP

  • 钦定顺序特别重要,这不仅关乎到可能的去重,也关乎到简化问题。当然,错误的顺序可能会使问题更复杂(来自图上状压计数)。

  • 如果觉得题目无从下手,考虑 DP(来自蜜蜂搬家)。

    • 尝试着设计一个不管有多复杂的 DP 状态,然后一点一点把握题目中各个要素的关系,找到转移的途径。

    • 考虑尽量简洁地描述题目要素之间的关系,不管这种关系看起来多么地不可转移。那是实现的事情。

    • 一定要敢 DP!

  • 如果有机会——如果有机会——尽量不要把算法大改特改。请最好保持它本来的样子——这样内聚性比较好,调起来也比较好调,不会出现难以名状的客制化错误(来自某个线段树优化长剖,其中由于链长最大为 \(m\) 的题设改动了长剖的结构却没有注意到,导致剖假了)。

  • 准备扫尾的时候好好想想你的扫尾复杂度对不对(来自最短路,使用了回溯到 \(S\) 求路径长度的方式,复杂度 \(O(n^2)\)...work 部分的复杂度是 \(O(m)\))!!!

  • 复杂度平衡。复杂度平衡。复杂度平衡。

  • 拓扑排序也是排序!倒不如说它是验证序的存在性的。存在的话随便找一条。

  • 不要老是试图对不要求 \(O(1)\) 的题目猜结论然后打补丁(来自 \(\text{CF1698C,CF1728D}\))。

  • 分块之于线段树,恰如齐纳协议之于 OGAS。它只有一层,明白吗?想想分块的特点是什么——块内暴力!线段树做得到吗?区间太大就做不到。分块恰恰像是舍弃了嵌套,换取了暴力...

  • 给出一种维护树上若干点是否共链的做法:维护一个 set,内部关键字为到起点的距离,加的时候求 \(lca(s,x)\oplus lca(x,t)\oplus lca(s,t)\),可以证明这就是这三条路径的交点(如果有),对等于 \(s/t/x\) 分讨,如果改 \(s\) 那么对距离做整体偏移。删除时同理,注意整体偏移。

标签:题目,分块,复杂度,杂记,lca,线段,DP
From: https://www.cnblogs.com/weixin2024/p/17139672.html

相关文章

  • 一周杂记(2023.2.13~2.17)
    好久没看博客园,忽然想到这个博客还有作随笔之用,于是决定在校的时候随便记录点事情,顺便锻炼一下文字。2023.2.13周一在普通班还是有些不适应,不是因为它是普通班,而是因为......
  • 算法杂记 2023/02/16
    算法杂记2023/02/16目录算法杂记2023/02/16D.DifferentArrays2000今天分享的是Codeforce上的一道2000分的动态规划+计数题。目前的目标是从紫冲橙。D.Dif......
  • 算法杂记 2023/02/15
    算法杂记2023/02/15目录算法杂记2023/02/15453.MinimumMovestoEqualArrayElements462.MinimumMovestoEqualArrayElementsIInull今天分享的是两个力扣上的......
  • CN特色无公网 | IPv6杂记
    最近又开始折腾自己的影视库,本来想搞软路由的,但是人还在家没啥搞的必要,就想着先整个公网IPv6来玩。结果就是:被国内网络运营环境整吐了。我家的网络拓扑首先是光猫IPv6......
  • 杂记
    ---------------------------------------------------------------------------------------------------------------------------20230207孔伟给职场新人建议1.先升......
  • Redshift Elastic Resize杂记
    Redshift的扩容的节点数不是随意可以配置的,而是和初始状态的集群节点数成比例关系:  Resize大约3T的集群大概20-30分钟,期间集群不可用(已经建立的数据库连接查询会卡......
  • jn07 杂记
    \(\bold{2023/1/30}\)英语水平遭到质疑。装逼被抓,嘴硬。喜欢做梦。......
  • 杂记5
    1.switchswitch后带表达式时,switch-case只能模拟相等的情况;如果不带表达式(即空switch),case后就可以跟任意的条件表达式,例:switch{caseadd(5)>10:fmt.Pr......
  • 编程软件基础知识(杂记)
    1电脑知识1.12编译型语言和解释型语言编程语言分为编译型语言和解释型语言2.1编译型语言C和C++这两种语言是编译型语言,编译型语言的特点是执行速度快,缺点是什么呢?......
  • 杂记4
    1.为任意类型添加方法(包括系统定义的)例:1typeUserMapmap[int]User23func(umUserMap)GetUser(idint)User{4returnum[id]5} 2.匿名结构体(通......