02.01
没补完。
T1
考虑把区间从短到长排列后双指针,那么需要维护一个集合,加区间删区间询问是否有点被覆盖 \(m\) 次,这个 SGT 就行了。
02.02
T1
现在不想写。
T2
这不就是 P9981。
考虑这个字典序怎么维护,建分层最长路,在每一层中维护所有节点的相对顺序,则比对两个后继只用比对当前边的边权以及后继点连出的最长路的相对大小。无解用拓扑来找,预先拓扑求最长路。
之前做 P9981 时打算用可持久化线段树维护最长路径的哈希值,倒也可以。
T3
\[F_n = F_{n-1}+F_{n-2}+2\sqrt{3+F_{n-1}F_{n-2}} \\ (F_{n+1}-(F_n+F_{n-1}))^2=4F_nF_{n-1}+12 \\ F_{n+1}^2+F_n^2+F_{n-1}^2-2F_{n+1}F_n-2F_{n+1}F_{n-1}-2F_nF_{n-1}=12\\ F_{n}^2+F_{n-1}^2+F_{n-2}^2-2F_{n}F_{n-1}-2F_{n}F_{n-2}-2F_{n-1}F_{n-2}=12 \\ (F_{n+1}-F_{n-2})(F_{n+1}+F_{n-2})-2(F_n-F_{n-1})(F_{n+1}-F_{n-2})=0 \\ F_{n+1}-F_{n-2}-2F_n+2F_{n-1}=0 \]02.03
T1
赛时写了定向,赛后觉得自己是什么 nt。
有唯一一个点满足它周边的所有点的 dis 都比它大一,找到那个点即可。
T2
考虑一个 dp:\(f_{i, j} = \max(f_{i-1, j}, f_{i-1, j+w_i}+v_i)\)。
把连续的相等数看做相同,则每次做的形如:取出一个连续段,把其中 \(> w_i\) 的部分左移 \(w_i\) 并加上 \(v_i\)。
注意到只有位于 \([S-maxw, S]\) 内的起始值是有用的,这样复杂度就只与 \(maxw\) 有关了,是 \(O(w \log w)\)。
标签:week,12,maxw,T1,2F,日志,24.02,最长,维护 From: https://www.cnblogs.com/purplevine/p/18005270