大学生程序设计邀请赛（华东师范大学网络赛）题解

ultmaster edited 7 年，6 月前

首先声明本人不是所有题目的命题人，本人只是代表命题组发题解。好的我们开始。

A. 魔法拼音

这题确实没说清楚。比赛中也有很多人问这个怎么样，那个怎么样。但是很多问题问得不符合常理，比方说 iou 会不会出现。本题还提供了所谓了「拼音标准」，并不是没有用的。作为程序设计竞赛，不单单是算法重要，解决实际问题的能力也很重要。比方说，编码问题；比方说，合理性问题。

至于用 C/C++ 的输出问题直接复制题中的字符后使用 printf / cout 都可以，如果编译器报错请自行调整编译器的选项。

B. 分词

考虑动态规划。从一个点出发可以检查后面每一个可能的单词的权值，然后更新它的后继状态。可以用 map 或者 trie 来维护（map 可能需要适当优化，否则很容易超时）。有几个小技巧：

最后回溯的时候，只要在每一个走过的地方打一个点，然后从左往右一个一个字符输出，碰到点就输个空格就好了。
使用 map 的注意优化：单词长度不超过 30。这样的话超过 30 的单词直接认为权值是 0 就好了。

C. 袋鼠妈妈找孩子

由于数据范围很小，直接搜索就可以了。考虑 DFS，每一个要走的格子，周围最多只能有一格（其实就是走过来的那一格）是走过的。全部搜一遍就结束了。

出题人：过的人少得不可思议。

D. 实验室传染病

很多人的做法是先对每个点找出最右边传染病可以到达的位置，再找出最左边可以达到的位置，然后二者相减。
这样做很明显的问题是你最右边可以达到的位置可能是在你左边的人所传染的。

一种做法是可以二分预处理出来每个点单次传染到的左右范围，再用线段树维护每个点最终的范围最小值、最大值，利用线段树不断扩大范围并更新。你可以随机一个 $1$ ~ $n$ 的序列利用线段树更新，这样速度会变得很快，或其他优化方法均可。

这里提供另一种很奇怪的方法：从左往右扫，用一个 latest 保证一个点只计算一次。在计算每个点的过程中，先把当前点的影响范围暂存为它左边影响的点的影响范围并上它本身的影响范围。然后对它本身影响范围内的点没有计算过的进行递归计算，计算完了之后重新统计。
很容易产生的一个问题就是如果递归的点计算需要这个点的数据怎么办？我们认为这种情况是不影响的。因为事实上，这个点的数据之所以不对是因为它后面的点还没有进行计算。我们会把后面的点都并到正在计算的点的计算范围，然后我们还是会对后面的点进行计算。
同样用线段树维护查询。

PS：此题数据无误，请发 Clarification 前认真思考自己的程序。

E. 黑心啤酒厂

求 $i \div gcd(x,i)$。

F. 丽娃河的狼人传说

按右端点排序，然后对于不满足条件的尽量往右垒就好了。贪心的证明：由于左边的都已经垒满了，所以垒左边的肯定是没意义的。垒中间肯定没有垒右边的号，因为右边的区间不可能长得断开，使得垒在左边收益更大。这样就可以实现 $O(n^2)$。

本题虽然不作要求，但是可以做到 $O(n \log^2 n)$，用线段树维护，不符合条件可能需要二分。具体细节留给读者思考。

G. 铁路修复计划

二分 $k$，然后每次对边重新赋值排序后，就是经典的 MST 问题了。
复杂度 $O(n \log^2n)$

H. 法国传统舞蹈

由于每一步操作可逆，所以从初始状态到目标状态跟目标到初始是等价的。先枚举将英文字母用不重复的数代替的方案。然后，考虑在目标状态中每一个数的后继。注意到在初始状态中对于每一个数是有唯一的合法后继的。每一次操作，可以发现，一定是交换了两个数的后继。反过来，每一次交换两个数的后继，都有唯一的操作与之对应。那么，题目就可以转换为，要将某一后继的排列，通过每次交换两个数的后继，变成某一合法的后继排列的交换次数。  
还可以进一步转换，注意到唯一合法后继是一个唯一的 $1$ 到 $N+M$ 的排列，那么必然存在一个映射，将这个排列变成 $1$ 到 $N+M$ 的有序排列。对目标状态也做这样一个映射，题目就可以转换为将 $1$ 到 $N+M$ 的某一个排列，通过每次交换两个数，变成有序的数列的最少交换次数。这就是个经典题了。答案就是总数减去循环节的个数。或者可以用其他奇怪的方法来处理。