Virtual NOIP II Day 4 总结

### T1 Merchant $22$分：考虑第$1$个$\text{Subtask}$，$n\le 20$，直接枚举每个物品是否选择即可。 $30$分：考虑$k_i\le 0$的情况。由于题目保证有解，且此时一切方案的$k\le 0$，知$t=0$。直接输出$0$即可。 $66$分：考虑$k_i\ge 0$的情况，此时一切方案的$k\ge 0$，因此如果$t_1<t_2$且$t_1$可行，则$t_2$也可行，即答案满足单调性。因此我们可以二分$t$，对某一个$t$，计算出此时的函数值并从小到大排序，取最大且大于$0$的至多$m$个函数值相加，如果所得和大于$k$，则可行，否则不可行。 $100$分：二分的方法看上去复杂度比较正确，我们继续考虑二分。 刚才我们已经证明，对于一切$\sum k\ge 0$的方案，单调性都是成立的。那么如果$\sum k<0$怎么办呢？ 如果存在一个可行的方案满足$\sum k<0$，那么答案一定是$0$，因为对于这个可行方案，总价值关于时间的函数单调减，所以$t=0$时一定可行。 于是我们可以先`check(0)`，如果可行则直接输出$0$；否则说明所有可行方案的$\sum k> 0$，知$\sum k\le 0$的方案都不可行，不会影响二分性质。接下来按照上面的方法进行二分即可。 但注意到$n\le 10^6$，但二分并排序所有函数值的时间复杂度为$\text{O}(n\log n\log t)$，无法承受。 但是注意到，我们只是需要知道前$m$大的函数值是多少，并不需要把所有函数值从小到大排序，因此我们只需要把前$m$大的函数值划分出来即可。 $\text{STL}$有一个函数`nth_element`，可以把前$m$小的元素放到数组的前$m$个位置，把其余元素往后面放；这个函数使用了类似快排划分的算法，但同时使用了优化，使得最坏时间复杂度和平均时间复杂度都是$\text{O}(n)$。它接受三个参数：`void nth_element(RandomIter first, RandomIter nth, RandomIter last);`，分别为排序的首指针、指向第$m$个位置的指针和超尾指针，还可以在末尾增加比较器参数。这个函数运用了类似`sort`的玄学优化，其效率是手写的划分所无法企及的。 于是时间复杂度降到$\text{O}(n\log t)$，可以承受。 ### T2 Equation 定义根深度为$0$。经过探索，我们发现，深度为奇数的点$i$，有方程$x_1+x_i=t_i$；深度为偶数的点$j$，有方程$x_1-x_j=t_j$。 经消元后发现，$t_1=0$，如果一个点$i$的深度为奇数，那么$t_i=t_{f_i}+w_i$；如果一个点$j$的深度为偶数，那么$t_j=t_{f_j}-w_{j}$。 如果题目又给出两个点$u$和$v$的方程$x_u+x_v=y$，情况如何呢？ 如果两个点的深度奇偶性相同，那么经过消元，可以得到$x_u-x_v=\pm (t_u-t_v)$的方程，那么如果解为整数，就能根据关系求出$x_1$，否则为$\text{none}$。 如果两个点的深度奇偶性不同，那么经过消元，可以得到$x_u+x_v=\pm (t_u-t_v)$的方程，如果与给出的条件矛盾则为$\text{none}$，否则为$\text{inf}$。 于是我们只需要根据树的关系维护$t$，即可回答询问。 但是修改$w$值时如何维护好$t$的变化呢？最朴素的方法是，在父节点的$w$值变化时，计算以其为根的子树种所有节点的新$t$值，但如果这么做，一次修改的最坏时间复杂度为$\text{O}(n)$，无法承受。 如何迅速更新同一棵子树所有节点的权值呢？我们考虑到区间操作数据结构。我们先按照$\text{dfs}$序给节点重新编号，使得同一棵子树内的节点的编号连续；接着用差分树状数组即可在$\text{O}(\log n)$的时间内进行区间操作和单点查询操作。 在考场上，我在实现这道题的代码的时候，犯了两个低级错误：一是直接使用未处理的差分数组充当了差分树状数组，没有进行建树操作；二是在进行$\text{dfs}$时，把$t$值的计算错误地放在了递归调用`dfs`之后，导致子节点无法利用父节点的$t$值进行递推。 为什么会出现这样的低级错误呢？因为在写这道题的时候，我只过了一个仅有$2$个节点的小样例，此时时间不太足够，我就跳到$\text{T}3$继续编写代码了。因此写完程序一定要认真进行静态查错，并进行大数据的对拍，一定不能盲目相信情况简单的小样例，不要放弃很可能是正解的题目去写下一题的暴力。 ### T3 Rectangle