电子科技大学第十一届 ACM 趣味程序设计竞赛第四场（正式赛）题解

Posted on In

A. 天气之子

题目描述

给定 个数 ，从左到右模拟以下过程：如果这个数大于 ，计数器加 ，后面所有数加 。询问最后计数器的值。

数据范围：。

题解

显然有一个 的做法，即直接模拟这个过程。

仍然考虑从左向右枚举。对于后面的数整体加 的这个操作，考虑维护增量，即可将暴力地给后面所有数都加 的这部分时间省下。

需要注意数据范围和数据类型的使用。

时间复杂度：，空间复杂度：。

参考程序：C++，Java。

Problem Setter: Vingying

P.S. P for Park ^ ^

B. 夜路

题目描述

给定一个 的网格，如果上下两行出现不同列有障碍或者一行两个格子有障碍则无法通行。求从左上角走到底部有多少种方案。

数据范围：。

题解

考虑如果可以走到一行，那么走到这行就有这行空位数那么多种方法。在判断掉非法状态后，利用乘法原理统计即可。如果能够走到底部，答案为 的 .. 行数次方（除去第一行）。

这道题有一个显而易见的 DP 做法。实际上，DP 与这样统计是等价的。还需要注意范围与数据类型的使用。

时间复杂度：，空间复杂度： 或 。

（因为每行判断是否合法只取决于这一行与上一行的状态，可以只保存这两行的状态以达到空间最优，但是对于本题来说没有太大必要）

参考程序：C++，Java。

Problem Setter: OrangeRain

C. 蔚蓝

题目描述

给定两个数列，每一个都有 个数，需要在两个数列中分别取出 个数，取出的数下标互不相同。这些数将组成一个长度为 的新数列，求这个新数列的所有元素之和的最小值。

数据范围：。

题解

本题可以看成一个集合划分问题，但是由于这道题的特殊性，我们可以换用其他解法。

首先，我们把原数组中的一个当做最终的答案数组，这里不妨设将 作为最终的答案数组。但是显然这个答案是错的，因为要恰好挑出 个数组 中的元素，我们还需要把其中 个 换成 。把一个 换成 ，所有元素和就会加上 。为了使得这个和最小，我们肯定要让加的这个值尽可能小，那么根据贪心的思路，我们选择最小的 个 加到所有元素和里，所得的结果就是答案了。

具体证明可以利用调整法，对于最优状态下任意一个被换走的 ，如果我们选择另一对 换，那么 的值将不小于目前这对，因此换走将可能会使答案变劣，换用相等的 的话对答案无影响，只是影响选择方案罢了。

（这道题甚至可以输出方案，扩大范围或者问有多少种方案）（废话

这里并没有卡排序，写复杂度合理的各种排序算法均可，根据题目数据范围写桶排序或者基数排序也可（但是需要注意负数的处理）。

时间复杂度： 或 或 ，空间复杂度： 或 。

参考程序：C++，Java。

Problem Setter: hbji

D. 外星货币

题目描述

求集合 的最小大小。这个集合内的数的子集进行加减运算，可以凑出 到 之间的所有整数，要求每个数不能和自己进行加减运算。

数据范围：。

题解

考虑这个集合 ，假设它满足要求，那么它可以表示的数的范围为 ，其中 为集合 内所有元素的和。如果再向其中加入一个数 ，那么与 组合能表示的数的范围为 。为了使加入 后满足要求，并且使得新表示的元素不与之前可以表示的数重复（即，不浪费新生成的数，这样可以使得集合尽可能小），则需要使得 ，因此 。

这样考虑递推，根据性质，如果集合 内元素和为 ，那么集合 可以为 时的答案。新加入的数永远为 。记 为当 时 内所有元素和，那么有如下递推关系：

当 时，。

因为要求最小数目，所以答案为第一个 的位置 。

根据递推关系，可知通项为 。这个数列在第 项时就已经超过了最大可能的 ，所以只需要求出这个数列的前 项进行比较即可。

还有一份来自 ZXyaang 的题解。对于一种货币的面值，如果计入答案的话可以有三种选择：加，减或者不选。只要规定一个值是加，比他小的所有面值都可以选择三态中的一个，所以每多选一个货币新增 个状态。答案就是 的前缀和。

时间复杂度：，空间复杂度：。

参考程序：C++，Java。

Problem Setter: qqq17770027225

E. 马拉松

题目描述

给定 条匀速直线的运动轨迹，这些轨迹都经过 上的互不相同的点。问所有人的总相遇次数。

数据范围：。

题解

是不是感觉和大地的裂变有点像？

考虑两人相遇满足什么条件。考虑两人起始点分别为 ，位移向量为 。则：

对于第一个式子，移项可得 。由题， 且 ，由此 。

两式联立，可化简为 ，进一步地，。

即，如果两人相遇，需要满足： 且 。利用数组统计一下即可。注意负数的处理。

（原来想卡 log 的但是被 Java 无情地拒绝了）

时间复杂度：，空间复杂度：。

参考程序：C++，Java。

Problem Setter: santongding

来自 Codeforces Round #478 (Div. 2) D. Ghosts