NOIP 模拟赛九

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