杂题

CF1437F Emotional Fishermen

又一次卡在了排列类问题上……
还是一样的套路，首先应该排序，使得插入遵循一定的顺序
一下默认数组以从小到大排序
观察性质，对于一个数，小于其 \(1/2\) 的数都可以认为是跟着它进来的，设其位置为 \(pos\)
那么每考虑完一个数这个排列已经摆好的位置个数是固定的
设 \(f_i\) 表示考虑完前 \(i\) 个数的方案数
假如从 \(j\) 转移过来，那么需要把从 \(pos_j\) 到 \(pos_i\) 的数一起放进去，用 \(A\) 算一下

\[f[i]=\sum f[j]\frac{n-pos_j-2}{n-1-pos_i} \]

发现转移分子之和 \(j\) 有关，分母之和 \(i\) 有关，那么分子前缀和预处理一下即可做到 \(O(nlogn)\)，瓶颈在于排序

---

P1128 [HNOI2001] 求正整数

考虑 \(dp\)
设 \(f[i][j]\) 表示考虑了前 \(j\) 个质数因数个数有 \(i\) 个的最小数是多少
始终围绕 \(num=\prod (k_i+1)\) 展开
那么转移：

\[f[i][j]=min\{f[i/k][j-1]pri_j^{k-1}\} \]

发现答案实在太大了，那么把 \(dp\) 整体取对数
变成了

\[f[i][j]=min\{f[i/k][j-1]+(k-1)log(pri_j)\} \]

记录下 \(dp\) 从哪儿来倒推回去即可

---

P1437 [HNOI2004]敲砖块

推荐 这篇博客 的图
设 \(f[i][j][k]\) 表示第 \(i\) 行第 \(j\) 列选了 \(k\) 个的方案数
可以从 \((i-1,j),(i,j-1),(i+1,j-1)\) 转移过来
注意后两种转移是加一列的前缀和
注意初始化

---

P4211 [LNOI2014]LCA

考虑一种神奇的求 \(lca\) 的方式：
对于所有 \([l,r]\) 中的节点将其到根的路径标记加一
然后从目标点到根一路累加答案
发现问题具有可拆分性，差分处理
于是将所有询问离线每次加入点到根的路径
树剖维护