Reverse Card
\((a+b)\mid b\cdot \gcd(a, b)\) 计数。
先化式子,记 \(g=\gcd(a, b), a=a'g, b=b'g\) 。
\(g(a'+b')\mid g^2b'\) ,即 \((a'+b')\mid gb'\) 。
又 \(\gcd(a' + b', b')=\gcd(a', b') = 1\) ,所以 \((a'+b')\mid \gcd(a, b)\) 。
又因为 \(a'\le g = \frac{n}{a'}\) ,得到 \(a'\le \sqrt n\) ,同理得到 \(b'\le \sqrt m\) 。
直接枚举做到 \(O(n)\) 。
Record
Fair Elevator
题意即为分成若干个 \({\color{red}(}{\color{purple}(}{\color{green}(}\) \({\color{red})}{\color{purple})}{\color{green})}\) 的区间。
记 \(f_i\) 为前 \(i\) 个是否合法,然后枚举下一个 \(j\) 再判断 \((i, j]\) 是否合法。
判合法只需要考虑几种情况(样例基本就足够了)就可以 \(O(n)\) 做到了。
复杂度 \(O(n^3)\) 。
Record
Paths
如果 \(u\) 固定,长链剖分后贪心取前 \(k\) 长的链即可(链长要算上链顶连向父亲的边)。
\(u\rightarrow v\) 换根发现只有子树 \(v\) 内的一条长链会 \(-w\) ,子树 \(v\) 外的长链会 \(+w\) 。
使用 multiset
动态维护前 \(k\) 长,支持插入和删除元素。
加入/删除哪些元素可以换根 DP 求出,注意 \(v\) 的最/次长链要减去 \(w\) 。
Record
Two Dishes
同一道菜的不同步骤有严格的关系,所以收益形如做到第 \(i\) 步时,另一个菜做到了 \(j\) 步,如果 \(j\le lim_i\) ,则获得 \(i\) 的收益。
则问题可以抽象为平面上的一些点,有一条 \((0, 0)\rightarrow (n, m)\) 的折线,只能往右或上走。
如果某个点在折线下/上方则有一定的贡献。
先加上需要在上方的点 \((x, y)\) 的贡献,然后替换成 \((x-1,y+1)\) 的新点,贡献取负。
这样只要一个点在折线下方就有贡献。
记 \(f[i, j]\) 为走到 \((i, j)\) 的最大收益,则转移形如 \(f[i, j]=\max_{k\le j}f[i-1,k]+g(i, j)\) 。
\(g(i, j)\) 为\((i, j)\) 下方的点的权值和,转换贡献形式,对于每个点,能够贡献给其上方的点。
所以问题变成了先取前缀 \(\max\) ,又有若干个后缀加,经典的 整体 DP 。
使用 map
维护 \(f\) 的非 \(0\) 差分,后缀加是简单的。
取前缀 \(\max\) 只需要对所有 \(<0\) 的值和后一个差分值合并即可。
注意走到 \((n, j)\) 后不能再取前缀 \(\max\) 了。
Record