Table of Contents
Algorithm
Evacuation: http://poj.org/problem?id=3057
https://dreamume.medium.com/poj-evacuation-c16bd37ca443
Review
梳状滤波器
https://ccrma.stanford.edu/~jos/pasp/Comb_Filters.html
淑状滤波器是数字化音频音效的基本构建块。之前的声学回音模拟就是一个梳状滤波器的一个例子。本节呈现两种基本的梳状滤波器类型，前向反馈和后向反馈，且给出一个频率反应分析
前向反馈梳状滤波器
前向反馈梳状滤波器如下图。直接信号在延迟线上前向反馈。输出是直接和延迟信号的一个线性组合
前向反馈梳状滤波器的微分等式为
$ y(n) = b_ {0}x(n) + b_ {M}x(n - M) $
我们看到前向反馈梳状滤波器是FIR过滤的一个特殊类型，它也是TDL的一个特殊例子
注意这个前向反馈梳状滤波器可通过设置 $ b_ {0} = 1, b_ {M} = g $来实现回音模拟。这样，它是一个单离散回音的计算物理模型。这是最简单的减弱（通过 $ | b_ {M} | < 1 $）由于“空气吸收”和/或球形扩散损失，且广播在cMT米距离上的延迟，T是秒单位的采样周期，c是声音速度，当空气吸收需要模拟得更精确，常量衰减因子 $ b_ {M} $可被一个线性、时间变化过滤的G(z)替代，给出一个在每个频率不同的减弱。由于空气吸收的物理性，G(z)一般有低通过的特性
后向反馈梳状过滤器
后向反馈梳状过滤器使用后向反馈信号，如下图
描述后向反馈梳状过滤器的微分等式为
$ y(n) = b_ {0}x(n) - a_ {M}y(n - M) $
后向反馈梳状过滤器是无限脉冲反应(IIR)数字化过滤的一个特殊例子，因为有一个从延迟输出到输入的反馈。后向反馈梳状过滤器可被视为一系列回音的计算物理模型，随时间指数型衰弱且统一空间。例如，特殊的例子
y(n) = x(n) + gy(n - M)
是一个理想平面波浪在两个平行墙上后向和前向反弹的一个计算模型；在这样的模型中，g表示总的旅行衰弱（两个墙到墙的旅行，包括两个反射）
对稳定性，反馈系数 $ a_ {M} $必须在幅度上小于1，例如，$ | a_ {M} | < 1 $。否则，如果 $ | a_ {M} | > 1 $，每个回音将比之前的大，产生一个决不停止，增长序列的回音
有时，输出信号从延迟线的尾端而不是开始出获取，这样微分方程变为
$ y(n) = b_ {M}x(n - M) - a_ {M}y(n - M) $
这个输出选择只延迟M个采样的输出信号
前向反馈梳状过滤器振幅反应
梳状过滤器，其名源于它们的振幅反应的梳子形状（增益及频率），如下两图
前向反馈梳状滤波器等式的转换函数是
$ H(z) = b_ {0} + b_ {M}z^{-M} $
这样振幅反应（增益及频率）为
$ G(\omega) \triangleq | H(e^{j \omega}) | = | b_ {0} + b_ {M}e^{-j \omega M} |, \qquad -\pi \le \omega \le \pi $
对下图M = 5, $ b_ {0} = 1, b_ {M} = 0.1, 0.5 $和0.9。当 $ b_ {0} = b_ {M} = 1 $，我们获得最简单的结果
$ G(\omega) = | 1 + e^{-j \omega M} | = | e^{-j \omega M / 2} | |e^{j \omega M / 2} + e^{- j \omega M / 2} | = 2 | \cos{(\omega \frac{M}{2})} | $
在这个例子中，我们获得M个nulls，其是振幅反应中0增益的点（频率）。注意在flangers音效中，这些nulls通过调制延迟长度M来随时间慢慢移动。这个平滑需求会干涉延迟线
向后反馈梳状过滤器振幅反应
下图显示向后反馈梳状过滤器振幅反应的一个家族，使用一个选择的反馈系数获得
下图显示一个相似的家族通过使用负反馈系数获得，反馈的相反信号在振幅反应上交换波峰和波谷
根据之前的章节，一个向后反馈梳状过滤器类可被定义为任意如下形式的微分等式
y(n) = x(n) + gy(n - M)
两边使用z转换并解 $ H(z) \triangleq Y(z) / X(z) $，向后反馈梳状过滤器的转换函数被发现为
$ H(z) = \frac{1}{1 = gz^{-M}} $
这样振幅反应为
$ G(\omega) \triangleq | H(e^{j \omega}) | = \frac{1}{| 1 - ge^{-j \omega M} |}, \qquad - \pi \le \omega \le \pi $
上上图为M = 5和g = 0.1, 0.5和0.9，上图显示相同的情况及向后反馈信号反转
对g = 1，向后反馈梳状振幅反应缩减为
$ G(\omega) = \frac{1}{2 |\sin{(\omega M / 2)} |} $
对g = -1
$ G(\omega) = \frac{1}{2 | \cos{(\omega M / 2)} |} $
精确反转前向反馈梳状过滤器的振幅反应，其增益为g = 1
注意对g > 0产生回响峰值在
$ \omega_ {k} = 2\pi \frac{k}{M}, \qquad k = 0, 1, 2, \ldots, M - 1 $
而对g < 0，峰值发生在这样的值的中间
已过滤反馈梳状过滤器
已过滤反馈梳状过滤器(FFBCF)使用已过滤反馈替代一个反馈增益
记反馈过滤转换函数为 $ H_ {l}(z) $，已过滤反馈梳状过滤器的转换函数可被写为
$ H(z) = \frac{b_ {0}}{1 - H_ {l}(z)z^{-M}} $
注意当 $ H_ {l}(z) $是一个起因过滤，FFBCF可被认为数学上一般所有极转换函数的特殊例子，头M - 1个分母系数限制为0
$ H(z) = \frac{b_ {0}}{1 + 0 + \cdots + 0 + a_ {M}z^{-M} + a_ {M+1}z^{-M+1} + \cdots} $
它是过滤器系数的“稀缺”使得FFBCF比其他的更能有效地计算，更有一般化目的，IIR 过滤结构
在之前章节中，我们提到了向后反馈梳状过滤器的物理解释为模拟一个平面波浪在两道墙之间前向后向的回响。在反馈循环中插入一个低通过滤进一步模拟在广播循环期间发生的频率依赖损失，如同真实房间中发生的一样
平面波浪衰减主要的物理源是空气吸收和每个墙的系数吸收。平面波浪在真实房间中额外的损失是由于发散。（平面波浪碰撞非墙的其他东西且已多个不同的方向反射）。在音乐厅中一个特别地发散是纹理墙表面。在射线跟踪模拟中，从这样的墙的反射是典型的玻璃发散部分的模型。一般来说，波浪长度相比墙纹理反射发散（任意墙运动导致的衰减）的颗粒大小要大，当波浪长度相当或小于纹理颗粒大小会发散到各种方向，称为反射的发散部分
已过滤反馈梳状过滤器在计算机音乐领域有许多应用程序。它有力地首先被Schroeder建议人造回声，且被Moorer首次实现。Karplus-Strong算法的物理解释，FFBCF可被视为一个摆线的物理模型转换函数。在弦和风乐器的数字化波浪指导模型中，FFBCF是典型地源于基于从双向延迟线发展来的某些初始化波浪指导模型
对稳定性，反馈过滤的振幅反应 $ H_ {l}(z) $必须小于1，在所有频率大小上，例如，$ | H_ {l}(e^{j \omega T}) | < 1, \forall \omega T \in [-\pi, \pi) $
并行梳状到TDL的相等性
容易显示之前的TDL相等于三个前向反馈梳状过滤器的并行组合。为看到这个，我们简单添加三个梳状过滤器转换函数和相等系数
$ \begin{aligned} H(z) &= (1 + g_ {1}z^{-M_ {1}}) + (1 + g_ {2}z^{-M_ {2}}) + (1 + g_ {3}z^{-M_ {3}}) \\ &= 3 + g_ {1}z^{-M_ {1}} + g_ {2}z^{-M_ {2}} + g_ {3}z^{-M_ {3}} \end{aligned} $
其意味着
$ b_ {0} = 3, b_ {M_ {1}} = g_ {1}, b_ {M_ {2}} = g_ {2}, b_ {M_ {3}} = g_ {3} $
我们看到平行梳状过滤器比对应TDL需要更多延迟内存（$ M_ {1} + M_ {2} + M_ {3} $元素），TDL只需要 $ max(M_ {1}, M_ {2}, M_ {3}) $个元素
系列梳状到TDL的相等性
可直接显示一系列前向反馈梳状过滤器的组合产生一个拍打延迟线。考虑两章节的例子，我们有
$ \begin{aligned} H(z) &= (1 + g_ {1}z^{-M_ {1}}) (1 + g_ {2}z^{-M_ {2}}) \\ &= 1 + g_ {1}z^{-M_ {1}} + g_ {2}z^{-M_ {2}} + g_ {1}g_ {2}z^{-(M_ {1} + M_ {2})} \end{aligned} $
这里
$ b_ {0} = 1, b_ {M_ {1}} = g_ {1}, b_ {M_ {2}} = g_ {2}, M_ {3} = M_ {1} + M_ {2}, b_ {M_ {3}} = g_ {1}g_ {2} $
这样，之前图片中的TDL相当于两个前向反馈梳状过滤器的系列组合。注意一些TDL结构忽略梳状过滤器的系列顺序
时间变化梳状过滤器
梳状过滤器可随时间缓慢改变来产生如下数字化音频音效：
- 相
- Flanging
- Chorus
- Leslie
因为所有这些音效包含随时间调制延迟长度，且因为时间变化延迟线典型地需要插入，这些应用程序会在第5章讨论。现在，我们将追求使用固定延迟线能完成的。也许最重要的应用程序是人造回声
Tips
设计模式之美 – 设计原理与思想：面向对象
封装指只暴露有限的接口，隐藏信息、保护数据，提高易读性
抽象隐藏方法的具体实现，让调用者只需关系方法提供了什么功能、简化模块复杂度
继承使代码复用
多态提高代码的可扩展性和复用性
类数据和方法分离，比如MVC三层结构
什么时候用抽象类什么时候用接口？
如果我们要表示一种is-a关系，并且是为了解决代码复用问题，我们就用抽象类；如果我们要表示一种has-a关系，并且是为了解决抽象而非代码复用问题，就可以使用接口
基于接口而非实现编程，这样可以把接口和实现分离、封装不稳定的实现、只暴露稳定的接口、降低耦合度、提高扩展性
越抽象、越顶层、越脱离具体实现的设计、越能提高代码灵活性，应对未来的需求变化。好的代码设计，不仅能应对当下的需求，而且在将来需求变化时，依然能在不破坏原有代码设计的情况下灵活应对
如果类之间继承结构稳定（不会轻易改变），继承层次较浅（比如，最多有两层继承关系），继承关系不复杂，我们就可以大胆使用继承。反之，系统越不稳定，继承层次很深，继承关系复杂，我们就尽量使用组合
此外，一些设计模式会固定使用继承或组合。比如，装饰器模式、策略模式、组合模式等使用组合，模板模式使用继承
贫血模式适合业务比较简单的系统开发，充血模式适合业务复杂的系统开发
充血模式根贫血莫斯相比，主要区别在Service层。在充血模式中，我们将部分原来在Service层的业务逻辑移动到充血的Domain领域模型中，让Service类实现依赖这个Domain类。Service类不会完全移除，而是负责一些不适合放在Domain类中的功能。比如，负责跟Repository层打交道、跨领域模型的业务聚集功能、幂等事务等非功能性工作
充血模式的DDD开发模型跟贫血模型相比，Controller层和Repository层代码基本相同。因为Repository层的Entity生命周期有限，Controller层的VO只是单纯作为一种DTO。两部分的业务逻辑都不会太复杂。业务逻辑主要集中在Service层。所以，Repository层和Controller层沿用贫血模式的设计思路是没有问题的
针对框架、类库、组件等非业务系统的开发，其中一个比较大的难点就是，需求一般都比较抽象、模糊，需要你自己去挖掘，做合理取舍、权衡、假设，把抽象的问题具象化，最终产生清晰的、可落地的需求定义。需求定义是否清晰、合理，直接影响后续的设计、编码实现是否顺畅。因此，需要重视前期的需求分析
需求分析的过程是一个不断迭代优化的过程。我们不要试图一下就能给出一个完美的解决方案，而是先给出一个粗糙的、基础的方案，有一个迭代的基础，然后再慢慢优化，这样的一个思考过程能让我们摆脱无从下手的窘境
如何进行面向对象编程：
- 划分职责进而识别出有哪些类
- 定义类及其属性和方法
- 定义类与类之间的交互关系
- 将类组装起来并提供执行入口
根据需求描述，把其中涉及的功能点，依次罗列出来，然后再去看哪些功能点职责相近，操作同样的属性，是否应该归为同一个类
针对复杂的需求开发，我们首先要进行模块划分，将需求先简单划分成几个小的、独立的功能模块，然后再在模块内部，进行职责划分并给出类。模块的划分和识别跟类的划分和识别，套路相似
类和类的交互关系有泛化、实现、聚合、组合、关联、依赖
泛化就是继承，实现一般指接口和实现类，聚合是一种包含关系，A类对象包含B类对象，B类对象生命周期不依赖A类对象生命周期。组合也是一种包含关系，A类对象包含B类对象，B类对象生命周期依赖A类对象生命周期，B类对象不能单独存在。关联是一种非常弱的关系，比如B类对象是A类对象的成员变量。依赖是最弱的关系，比如A类对象使用B类对象作为参数或返回值
Share
Light Up
https://crypto.stanford.edu/pbc/notes/zdd/lightup.html
友好的Light Up迷宫也是ZDD友好的。我们开始于每个放置灯泡的位置一个元素。然后对每一行，我们构建包含最多行中一个元素的ZDD集合。列相似
接着，对每个空白的方块，我们构建包含至少一个元素可用一个车从方块移动到达的ZDD集合
最后，对每个数字(n)，我们构建方块中围绕该数的包含(n)个元素的ZDD集合
这些ZDD的交是解决方案
这些迷宫跟八皇后迷宫相似，小心地写递归查找算法可解决得比ZDD更快些。然而，写ZDD更简单，提供已经实现的基本的方法。对小规模，我们可回答不完整迷宫的问题。例如，给定只有一些或不给定线索，有多少个解决方案？我们如何随机取一个？哪个有最大的权重，一个灯泡在行(x)和列(y)为(x+y)