C – The Number Of Good Substrings
这道题比较傻逼。
考虑记录上一个最近的\(1\)的位置\(nxt_i\)，然后显然的是：如果在\( O(n \log n) \)时间的扫描中扫描到\([l, r]\)大于当前区间，那么就考虑\(l\)左边是否有足够的零来补足长度。然后这道题就可以愉快的 AC 了。
这道题比较傻逼。
考虑记录上一个最近的\(1\)的位置\(nxt_i\)，然后显然的是：如果在\( O(n \log n) \)时间的扫描中扫描到\([l, r]\)大于当前区间，那么就考虑\(l\)左边是否有足够的零来补足长度。然后这道题就可以愉快的 AC 了。
这道题还是很妙的，我只想到了最大费用最大流之后就想不动了。
我们在这里介绍边数为\(O(n)\)级别的解法。考虑把所有的端点离散化为\(2n\)个连续的点，然后相邻端点\(i, i+1\)相互连接流量无限、费用为零的边。考虑区间左右端点，左端点连到右端点，流量为\(1\)，费用为区间长度。最后源点连左端点，汇点连到右端点。
这样就可以强制满流，且费用最大。
这道题可以离线回答，很大概率是什么树上差分之类的东西。但是树上差分无法维护区间信息，然后想到用权值线段树来维护。如果暴力开\(1e5\)个线段树来维护会 GG，但是我们可以动态开点，然后每个点对应的线段树大小差不多为\(O(\log n)\)级别的，这样空间就可以接受的了。
既然有了很好用的动态开点线段树，我们就可以用树上差分那一套路，在端点和\(LCA\)处打标记，然后考虑从下往上合并答案。合并可以用线段树合并，复杂度为重合部分，差不多就是\(O(\log n)\)。然后就没了，很傻逼的一道题。
这道题原题解作者的思路非常的清晰。我来阐述一下。
首先思考答案的意义，一定是总的权值和减去：
我们可以用上面这三个元素组一个网络流，计算最小割使答案最大。
考虑将源点连入雌性，雄性连入雄性，流上限就是变性花费：如果将这种边割掉，那么就是不需要进行变性。考虑朋友的边，如果倾向于变雌性，源点连入，向所有的对应编号连边；如果雄性，连入汇点，所有对应编号的向该朋友连边。
这道题所有购买方案的取值上界为\(a_i \times k\)，差不多就是\(1e5\)级别。考虑超级大暴力，设置状态\(f[i][j][w]\)为选了\(i\)个次、最后一次是第\(j\)种硬币且当前总价为\(w\)是否可行。这个转移算上取值上限就差不多是\(O(n^4)\)的，只能过掉一部分分数。
考虑进行状态转化。我们先让所有商品的价格减去价格最小值，然后剩下购买的方案就变成了形如\(k*minVal + sum\)的形式，然后我们设置状态\(f[i][j]\)最后一次选第\(i\)种商品，且选到\(j\)的最少选择次数，统计次数小于\(k\)的状态就可以了。
真你妈毒瘤。
原式子是长这个样子的：
\[ f(n) = \sum_{i = 0}^n \sum_{j = 0}^i \begin{Bmatrix} i \\ j \end{Bmatrix} 2^j (j!) \]