Ideas

放一些出题的想法

求带边权树上经过点 \(i\) 的所有简单路经长度之和，要求 \(O(n)\) 算法

首先若从一个点出发有长度为 \(c_1,c_2,c_3,...,c_n\) 的若干路径，那么答案为 \((\sum_{i=1}^{n}c_i)^2-\sum_{i=1}^{n}c_i^2\)

记 \(\sum_{i=1}^{n}c_i\) 为 \(f\)，\(\sum_{i=1}^{n}c_i^2\) 为 \(g\) ，\(i\) 号点的答案即为 \(f_i^2-g_i\)

下面考虑如何求解 \(f,g\)

套路地先求解 \(i\) 子树内的 \(f',g'\)，即先只考虑从 \(i\) 出发到达 \(i\) 子树内的路径

设辅助数组 \(h_i\) 表示从 \(i\) 出发的路径条数， \(h'_i\) 数组表示从 \(i\) 出发到达子树内的路径条数

所以有

\(h'_i=\sum_{j∈son_i}h'_j\)
\(f'_i=\sum_{j∈son_i}(f'_j+h'_j*w_{ij})\)
\(g'_i=\sum_{j∈son_i}(g'_j+2*w_{ij}*f'_j+h'_j*w_{ij}^2)\)

先通过一遍自底向上的 \(Dfs\) 求出 \(f',g',h'\)，下面就要考虑如何自顶向下求解

首先，若从 \(i\) 出发，第一步要么走入 \(i\) 的子树(这部分我们已经求过)，要么向上走到 \(i\) 的父亲 \(fa\)

不难发现走到 \(fa\) 后接下来的路径信息相当于 \(f_{fa},g_{fa},h_{fa}\) 减去 \(i\) 的贡献得到的(因为简单路径不能往回走)，那么 \(f_i,g_i,h_i\) 就等于 \(f'_i,g'_i,h'_i\) 加上走到父亲后的路径贡献即可

复杂度 \(O(n)\)

思维难度：NOIP提高组D1T3
代码难度：NOIP提高组D1T2

有 \(k\) 种接收器，每种接收器都可以接受 \(0,1,2...m-1\) 中的任一数字并吐出一新数字 ，给出 \(k\) 种接收器的输入输出规则，支持修改某个位置上接收器的种类，多次询问一个数字依次通过 \(n\) 个接收器后的值是多少

在线段树上维护一种抽象的"接收器"，\(O(m)\) \(pushup\)即可

思维难度：NOIP提高组D2T1
代码难度：NOIP提高组D2T1

\(q\) 次询问，每次钦定 \(i\)，问区间 \([l,r]\) 中满足\(a_j > a_i(j∈[l,r])\)的 \(j\) 中 \(|i-j|\) 最小是多少，要求 \(O(nlogn)\) 做法

不妨假设 \(i < l\)，那么二分下标 \(mid\)，找到最靠左的使 \(max_{j=l}^{mid}{a_j} > a_i\) 的 \(j\) 即可(倍增也可)，其他情况同理

利用 \(st\) 表可以做到一个 \(log\)

思维难度：NOIP提高组D2T2
代码难度：NOIP提高组D2T2

坐标系上有 \(n\) 个补给站，在每个补给站 \(i\) 可以选择花费 \(w_i\) 加满油(油箱容量为 \(L\) )并获得价值 \(c_i\) 的矿石(只能获得一次)。车只能向右和向上走，移动一次消耗一格油，求从 \(1\) 号补给站走到 \(n\) 号补给站的 "价值-花费" 最大值

曼哈顿距离转切比雪夫距离，用KdTree优化建图，之后跑最长路即可

思维难度：NOI D2T1 （
代码难度：NOI D2T1 （

Ideas

原文：https://www.cnblogs.com/study-ysj/p/11229552.html