总结
今天的暴力打的还行
T1 的卷积优化 dp 是真不会。
T2 正解如果花时间是好想的，赛时在做 t3。
t3 会了性质，但是不会维护。
t4 乱搞。
题解
monster
暴力 dp 显然，考虑优化。
设 \(f_{i,j}\) 表示选了 \(i\) 个非负整数，和为 \(j\) 的最大的 \(\sum s\)，直接做背包是 \(\mathcal O(nm^2)\) 的。
此时 dp 状态和 \(a\) 无关。发现我们只需求最终的 \(f_{n,*}\)，那么在 \(f_{i,*}\) 的基础上有
- \(\mathcal O(m^2)\) 暴力加入一个元素，即 \(f_{i+1,j}=\max(f_{i,k}+s_{j-k})\)，转移到 \(f_{i+1,*}\)，暴力 dp 做了 \(n\) 次这个操作。
- \(\mathcal O(m^2)\) 用 \(f_{i,*}\) 和自身做一个 \((\min,+)\) 卷积，即 \(f_{2i,j}=\max(f_{i,k},s_{j-k})\)，转移到 \(f_{2i,*}\)。
path
对于 DAG 的部分分，如果 \(s\) 能到 \(t\)，则每一步都贪心选能到 \(t\) 的字典序最小的点。
发现可以直接推广到不是 DAG 的情况，如果这样走出了环，就说明存在长度无限大的理想路径。
即可以在一个每个点都能到达 \(t\) 的环中一直走，且过程中走任意合法出边都会使得字典序变大。
那么对于每个 \(t\) 建立反图，预处理每个点走一条出边后能到达的后继。对于一组询问，处理使得不存在理想路径的情况。
倍增回答询问，时间复杂度为 \(\mathcal O(n(n+m)+(n^2+q)\log n)\)。
apple
回答单次询问。手玩发现判定规律：
先将区间全部 \(-1\)，若修改完后可以多次将序列的相邻两项 \(-1\) 后使得序列全为 \(0\) 则合法。
区间询问只需要分奇偶讨论，对区间内的 \(b_i\) 加或减 \(b_{l-1}\) 即可。由贪心得，若 \(b_i<0\) 或 \(b_r\neq0\) 则无解，否则有解。
用线段树分别维护偶数位置和奇数位置的最小值即可。 时间复杂度为 \(\mathcal O(q\log n)\)。
sale
0/1 分数规划，令 \(p_{i,j}=d_id_j\)，二分答案 \(x\)，即判定是否存在一个 \(p\)，满足
\[\sum_{i=1}^n\sum_{j=1}^n\left([i\neq j]a_ia_j\right)p_{i,j}-\sum_{i=1}^n(a_i^2x)p_{i,i}>0 \]最大化左边的式子即可完成 check，使用网络流，关于 \(p\) 跑最大权闭合子图即可。时间复杂度为 \(\mathcal O(n^4|\log\epsilon|)\)，\(\epsilon\) 是二分的精度。
标签：8.2,log,sum,模拟,mathcal,复杂度,dp,暴力 From： https://www.cnblogs.com/QcpyWcpyQ/p/18343998