【题解】武汉工程大学第七届ACM程序设计竞赛

A. 一二和布布

题意： 个数里可重复地选 个，使和为 。

因为限制了必须选 个，所以不是背包。

我们知道选 个可以得到哪些数，像树上背包一样合并一下就知道选 个能得到哪些数。暴力 ，bitset ，FFT 。

知道选 个的合并就知道选 个的，知道选 个的合并就知道选 个的……因此套一个快速幂即可。

B. 评测

string 读入判相等即可。

C. Designant

使用 map 或数组对木棒进行计数，同时维护前缀 gcd，由于需要的木棒种类很少，可以每次都直接遍历所有需要的木棒长度，除以需要的数量并取最小值即为答案。复杂度 。

D. Designant（Ascendant）

这里需要用到一个结论，即调和级数 （表述不严谨，大概就是这个意思，具体可以百度调和级数复杂度）。

所以我们可以先对木棒进行计数，然后用两重循环，第一重遍历木棒长度，第二层遍历所有倍数考虑能否作为身体，使用组合数计算答案，在使用 作为基础长度 作为身体长度时，可能的组合即为 ， 表示长度为 的木棒的个数。

虽然 ， 跑一秒看起来不够，但由于 只有 ，且一种木棒最少要 根才可能作为基础长度 ，剪枝后实际复杂度会低很多。

E. Designant（After Ascension）

本题也需要一个结论，即前缀 gcd 的变化次数不会超过 次， 为值域。因为前缀 只会减小，每次减小最少也要除一个 ，因此变化次数不会超过 次。

因此我们就可以考虑在 不变时维护答案，变化时重新遍历一遍并计算答案。维护方法有很多种，这里只介绍一种。

因为这题也是需要维护拥有的木棒数量除以需要的木棒数量的最小值，我们可以考虑使用 map 维护 （即使用这种木棒能制造多少蚂蚁）的结果的出现次数，每次木棒数量变化时都修改出现次数，如果出现次数减为 就从 map 中删除，这样每次用 \texttt{begin()} 获取的最小值就是答案。

F. 小七爱玩股票

可以用一个 map 来记录当前价格第一次出现的位置，从前往后遍历买的价格，看是否存在满足条件的卖的价格。

注：

• 当本金无法购买当天价格的股票时，会出现 的情况，不特判掉可能会出现浮点错误。
• 赚的钱一定会是所买股票数的整数倍。

特别地，如果赚的钱为 ,那么可以额外记录每个价格第二次出现的位置，遍历来找符合条件的答案。

G. 强迫症

题意：有向图不断删边，求有唯一拓扑序的时刻数。

拓扑排序时我们总是把入度为 的点放到队列中，队列中的点都是可以下一步可以选择的点，因此

• 队列长度大于 则拓扑序不唯一。
• 队列长度为 则拓扑序不存在。

不断删边的过程，拓扑序的数量显然是单调不减的，因此合法时刻是连续的一段，只要找到开始、结束时刻即可。

容易想到二分，但被卡了。（我花了半天时间卡 C++ 的二分，放过其它语言的线性，虽然最后好像还是有二分过了）

先拓扑排序直到队列为空；再去删边直到有 入度的点，继续拓扑排序；重复上面过程，直到所有点都被遍历过，就能找到开始时刻。

反过来加边。队列长度为 就加拓扑排序，队列长度大于 就加边，直到所有点都被遍历过，就能找到结束时刻。

当然，其实写起来有其实有不同的写法。

H. 摸鱼实习生小 O VS Hacker No.1

本题可以由题意构造一个状态机，对每一个 IP 维护一个状态，最终找出为接受状态的 IP 即可，参见状态转换图。

I. 单粒子翻转

每一位翻转的概率是 意味着， 概率均为 ，答案与 无关。

每一位的期望都是 ，乘以位权再求和即可， 。

J. 魔法树

题意：子树前 层权值求和，乘以点的编号，再求和。

• 子树前 层不好考虑。反过来考虑一个点的权值会被哪些点收集，变成了一个点的权值对 距离内的祖先节点（一条链）有贡献。
• 前缀和实现。dfs 时记下祖先节点（即路径），自已加 ， 级祖先减 。然后从子树向上累加。

也有树剖过掉的，造数据时没有想到。