C++11 之后提供了一种方便实现匿名函数对象的方法, lambda. 然而在写树上 dp 时, 常常需要实现一个递归的 lambda 函数, 但我又很不想写完整的 function 类型, 此时涉及一些类型推导的事情也一并在本文描述(搞得好像我本来就知道一样). 基础用法 一个 lambda 表达式由以下部分构成: capture: 描述变量如何捕获 param: 描述该函...

简单学习一下树上 dp 基本概念 在给定关系以树形式存在的问题中时, 如果遇到了符合 dp 解法的情况可以使用树上 dp. 举个例子, 经典的快乐指数问题. 给定一个树, 选择其中的结点满足以下规则: 结点权重和最大 一个结点若被选中, 则其父结点必定不能被选中 很显然, 大体思路是基于 DFS 的 DP. 对于一个结点而言存在三种状态: 父结点不在集合内, 自...

inline 的作用, 对编译器建议使用函数定义的代码替换每次对该函数的调用. 理论上, 这能够加速运行速度, 因为减少了函数调用的开销. 主要是消除了: 推送返回地址入栈, 推送参数入栈, 跳转到对应函数, 对应函数完成时返回这一系列过程. 额外, 我们应当注意, inline 只是建议编译器进行优化, 而非指定编译器进行优化. 编译器内部会根据一些判断决定是否真的值得要内联该函数. 将...

SEMI 提出的一种文件格式, 相较于 GDSII 能够更好压缩信息, 在 SEMI 处可以下载到有关 OASIS 的手册, 这是本文的主要参考内容. 除开这个文档外, Klayout 有关 OASIS IO 部分的源码(dbOASISReader)也一并做为本文的参考内容. 一些惯用语 考虑到本人大量接触 Klayout 的源码, 因此难免将 Klayout 中的一些定义带入本文, 未...

算得上一些基本的编程技巧了, 但过去我这块本身就学得不牢靠, 这里总结一下重新学习 基础 与(AND) a & b: 对应位都为 1 时, 结果为 1 或(OR) a | b: 对应位存在 1 时, 结果为 1 异或(XOR) a ^ b: 对应位不同时, 结果为 1 取反 ~a: 二进制数补码对应位取反 额外的, 似乎肌肉里存在着一句俗语”取反加一”...

理论上来讲前缀和以及差分两种思路应该是算法基础, 是那种堪比排序的基础, 按理说应该掌握得很好才对. 但由于没有系统性学习, 导致后面在学习部分变种树结构的时候非常吃力. 前缀和 是一种预处理方法, 能够实现后续相关查询达到 $O(1)$ 的时间, 以下又分几种情况 一维前缀和 这个方法通常解决”数组前 n 项之和”这个问题, 如下 std::vector<int> p...

注意事项 解析一下 Klayout 中 Flatten Cell 功能是如何实现的. 与之相似的功能有: Flatten Instance, Flatten Region, 相似功能会在介绍过程中提及. 当然, 在了解如何实现之前, 首先得明确理解这个功能是什么, Klayout 文档中清晰描述了这个: The “flatten cell” operation flattens a...

在任何情况下, 都请使用 using using 的使用方式与 typedef 一致, 可以帮助另取类型别名我们省略一大段的类型拼写(尤其在各种类嵌套的情况), 同时还能够增加代码的可读性. 一般的理解中, using 与 typedef 的作用完全一致, 仅仅存在语法上的不同, 如下: typedef unstable_box_tree <box_type, vector...