CUGBACM18 级训练#6 题解

A - Keywords Search HDU - 2222 #

题意： 给出单词和文章，问多少个单词在文章中出现过。

思路： AC 自动机板子题，之前也说过，不再赘述。

B - 病毒侵袭 HDU - 2896 #

题意： 给出 n 个单词（病毒）和 m 个长串（源码）问每个长串中有哪些单词出现过以及有多少个源码中有病毒。

思路： 和上个题类似，字符集不只是 26 个字母了……是所有 ASCII 可见字符，不过开到 130 就行，不用统计出现次数，新加一个数组记录病毒编号在字典树上的位置，查询的时候如果某个节点对应的病毒编号不为 0 就加入答案数组，排序之后输出，如果答案数组的大小不为 0，总个数加 1，最后输出总个数。

C - Sliding Window POJ - 2823 #

题意： 数组长度为 $n$ ,长度为 $k$ 的窗户在数组上滑动，问每次滑动后的窗户中的最大和最小值。

思路： 用线段树或者 st 表复杂度都是 $O(nlogn)$ ，单调队列可以做到 $O(n)$ ，如果求最大值就维护单调递增序列，方法如下：

不断从队尾出列，直到队尾元素大于待入队的数，因为又小又靠前面的数自然比不上又大又靠后的数。
不断从队首出列，直到队首元素的下标在窗户的范围之内。
输出队首元素，为当前窗户的最大值。

求最小值步骤类似，实际维护的时候为了容易实现第二步，队列中存的是下标。

D - Intersections Gym - 101853C #

题意： 给出两行序列，连接相同的数，问产生交点的个数。

思路： 如果两个数在上下两行中的相对位置发生了变化，连线的时候就会产生一个交点。

在读入第一行的时候记录每个数在数组中的位置。在读入第二行的时候将其替换为该数在第一行的出现位置，那么问题就变成了求逆序对（ $a_i>a_j,i<j$ ）个数的问题。

有两种求法：归并排序和树状数组。这里介绍树状数组的做法：将所有的数的在第一行出现的位置和在第二行出现的位置作为数对保存在数组中，按照第一行出现的位置从大到小排序，这样每次插入一个数的时候前面数字的个数就是插入这个数产生新的逆序对的个数，因为数组是从大到小排序，此时已经插入的数都是比当前数大的数，而位置在前面的数就是符合逆序对定义的数。而这就可以用树状数组实现，计算前面数的个数就是算前缀和，插入就是在第二次出现的位置 +1。

E - 维护序列 Gym - 237040G #

题意： 维护一个序列，支持以下操作：

把数列中的一段数全部乘一个值；
把数列中的一段数全部加一个值；
询问数列中的一段数的和模 $P$ 的值。

思路： 线段树改板子题，需要动点脑子，乘的时候加和乘的 lazy tag 都要更新。因为 $(val\cdot lazy_{mul}+lazy_{add})\cdot x=val\cdot lazy_{mul}\cdot x+lazy_{add}\cdot x$ 其他貌似就忘没的什差么不好多说了的了。

F - Little Elephant and Array CodeForces - 220B #

见我的另一篇文章

G - Tourists Gym - 101002I #

题意： 给出一棵树，计算所有两端其中一个是另一个倍数的路径长度和。

思路： 计算树上路径自然要用到 LCA，就是个倍增法板子题。

I - 二维树状数组：单点修改，区间查询 Gym - 237040E #

题意： 见题目。

思路： 见题目。

K - Jzzhu and Cities CodeForces - 449B #

题意： 一个图中有 $m$ 条道路和 $k$ 条通往首都（标号为 1 的点）的铁路。问最多可以去掉多少铁路使得所有城市到首都的最短距离不变。

思路： 把所有道路和铁路都放到图里，dijkstra 是可以记录最短路路径条数的！（好像考试考过？），原理就是当更新距离的时候如果和当前最短路径一样长就路径条数 +1，如果更短条数就置为 1。最后遍历所有铁路，如果当前铁路比最短路长那么就可以去掉，如果和最短路一样的话就要看最短路还剩几条，如果大于 1 的话就可以去掉并且把最短路的条数 -1。

L - Alyona and the Tree CodeForces - 682C #

题意： 给出一棵边权点权树，问最少去掉几个点使得不存在这样的点 $u$ ：其子树上存在某点 $v$ ，其点权 $a_v$ 大于 $v$ 到 $u$ 的距离。

思路： 计算树上所有的距离肯定超时，但是有这样一条性质，如果边权都是正数的话，如果 $\operatorname{dist}(u,v)> a_u,v\not = root$ 那么 $\operatorname{dist}(u,root)>a_u$ ，也就是说我们可以只计算到根节点的距离就行了，但是边权如果有负数上述性质就不成立了，但是我们可以稍加改动：当我们 dfs 的时候，如果当前点到根节点的距离小于 0，那么我们就应该将距离置为 0，然后接着 dfs，这样就避免了前面的负权路径产生的干扰。