Virtual NOIP II Day 2 总结

### T1 Divisors 这是道数学题吗？并不是。 $30$分：考虑$m=1$的情况。我们$\text{O}(\sqrt{m})$枚举$a_1$的所有因数，数出因数的个数，得到$ans_1$；于是$ans_0=n-ans_1$。 $100$分：类似$m=1$的情况，我们枚举每一个数的因数，再统计每个因数出现了多少次即可。 但是$10^9$的数组开不下，怎么办？ 方法$1$：使用`std::map`，将每个因数插入到`map`中，记录他们的出现次数。 请记住`map`的食用方法。~~不然又要手敲Treap啦~~ ```cpp #include <iostream> #include <map> using namespace std; map<int,int> mmp; int main(void){ mmp[0]=1; mmp[1]=0; if (mmp.find(2)==mmp.end()) mmp.insert(make_pair(2,3)); cout << mmp.count(2) << endl; if (!mmp.empty()) mmp.insert(make_pair(3,4)); cout << (mmp.lower_bound(3)->second) << endl; return 0; } ``` 方法$2$：使用`std::sort`。对于每一个数，把它的所有因数加入数组，最后对数组排序，数出每个元素出现的个数即可。 ### T2 Market $60$分：离线背包即可。 把物品按时间从小到大排序，再把询问从小到大排序。由于背包问题$\text{dp}$的状态$f[i][j]$的意义是前$i$个物品，背包大小为$j$时的最大总价值，因此我们只要输出对应的$f[i][j]$值即可。 $100$分：考虑逆映射。 我们观察数据范围：$n=300,m=100000$，$c_i,M_i\le 10^9, v_i\le 300,t_i,T_i \le 300$。 按理说$v_i$和$c_i$应该是同步增大的，但是为什么这里$c_i$这么大，$v_i$这么小呢？是为了不爆`int`吗？显然没有那么简单。 如果$c_i\le 300$，我们就可以毫无压力地跑朴素背包，但是这里$c_i$特别大。怎么办呢？ 我们考虑逆映射，即计算出价值至少为$v_i$时，背包容量的最小值，接着我们使用二分法或尺取法即可。 怎么把逆映射算出来呢？我们设$f[i][j]$表示前$i$个物品中，价值至少为$j$的选择方案中背包容量的最小值（“至少”是为了保证数组内元素的单调性）。那么对于某个物品$\left( c_i,v_i \right)$，更新$f[i][v_i+k]=\min(f[i-1][v_i+k],f[i-1][k]+c_i)$。计算完毕后对$f$数组取一次后缀$\min$即可满足“至少”性质。可以用滚动数组优化空间，计算时从大到小循环。 我们把同一个时间的查询排序在一起，再以$c$作为第二关键字排序，接着利用$c$单调递增时$v$一定不减的性质扫过$f$数组，或在$f$中二分即可。 逆映射的思想应用广泛，如$\text{LIS}$的单调数组解法。在正向映射难以满足要求的时候，我们可以考虑逆映射，用一个$\log$换来实现的可能。 ### T3 Dash Speed $20$分：对于$n\le 20$的数据，我们枚举$S$，分别$\text{dfs}$即可。 $40$分：对于$l_i=1$且树退化成链的数据，我们采用冰茶姬维护。 把边按$r$从大到小加入图中，同时从大到小枚举$q$。对于某个时刻，最长路的长度即为最大的冰茶姬的大小$-1$。 $60$分：对于其余树退化成链的数据，我们用线段树辅助。 从小到大枚举$q$。对于某条边$(l_i,r_i)$，我们在$l_i$时刻把这条边接上，在$r_i+1$时刻把这条边断开。 带断开的冰茶姬？！！有点可怕…… 幸好我们可以用线段树辅助。把边的连通和断开用$1$和$0$代表，那么问题就变成了，求最长的全$1$区间的长度。 这个问题我们是不是在哪里见到过呢？是的，在[String Master](https://sweetlemon.blog.luogu.org/virtual-noip-2018-ii-day1)里面，我们也解决过类似的问题，但是当时是只查询一次，且查询一次的复杂度是$\text{O}(n)$的，这里无法承受。 怎么办呢？上高级数据结构——线段树。 线段树的每个节点维护区间内最长的全$1$区间长、最长的全$1$前缀长和最长的全$1$后缀长，合并的方法类似[带修改的最大连续字段和问题](https://www.luogu.org/problemnew/show/SP1716)。 这样，查询和修改都是$\text{O}(\log n)$的了。 $[80,100]$分 题解没看懂，$\text{kule}$。