网络流概述

来源
图论重要部分

网络

网络（Flow Network）不同于网络流（Flow）。
网络：一个有向图$G=(V,E)$,每条边$(u,v)$都有一个权值c，称为容量（capacity），若边不在E中，容量即为0.
有两个特殊点：源点（Source）和汇点（Sink）

最大流及dinic算法

Ford-Fulkerson 增广路算法

通过寻找增广路来更新最大流，有EK，Dinic，SAP，ISAP等算法。

Sticker Album

期望DP裸题，选取（现有卡数，还需抽卡期望）为状态。
期望DP最重要的方程是,从结果向前推，利用全概率公式：
$E=\sum_i p_i*(E_i+cost_i)$
在此问题中，已知后一步期望，则+1为转移过去的cost，乘p即可。

MVC模式

即：Model-View-Controller模式，用于分层开发。

• Model：一个存取数据的对象或POJO，可以有逻辑，在数据变化时更新控制器
• View：数据可视化
• Controller：作用于Model和View，控制数据流向Model，在数据变化时更新View。

设计模式六原则

单一原则

一个类，一个方法只负责一个功能。

LSP替换原理

子类拓展父类而不改变父类功能。
即利用多态，以父类为参数，传递子类实现不同的业务逻辑。

依赖倒置原则

面向接口编程，即使用接口传递信息，使用具体类实现逻辑。
即实现依赖于抽象，而抽象不能依赖于实现。

接口隔离原则

• 不依赖非必须的接口
• 接口尽量细分

但是细分接口会导致开发难度提升。

迪米特原则

一个对象对其他对象不应了解过多。

开闭原则

用抽象构建架构，用实现扩展“原则”。

即“对扩展开放，对修改关闭”。

比如要打折，不是去改价格，而是使用打折方法处理。

近日补题

最近量很少啊，都不敢打比赛了

动态规划

参考

阶段

阶段是指，在问题解决过程中，同一时刻可能出现的不同状态的集合。

短短几天内，我因为身体不适去打小号。。。

近日写的题

这两天状态火热，小（。。。）号直接上1700+了，这段时间训练重点是1700的题，最近打算冲紫，需要多出一些1900+的题。目前希望比赛能30min出完1500-的，30min出一道1600的。剩下出个1900（。。。不太现实）。

今天做的一些1600左右的cf题

其中需要特别注意的是一种对subarray处理的方法：遍历右端点