NEUQ-ACM 寒假集训欢乐赛1 官方题解

· · 个人记录

A 三角塔

考虑从前往后摆，摆第 i 层会多摆 i(i+1) 个方块。

所以一个循环求 \sum\limits_{i=1}^ni\cdot(i+1) 就行了。

wangrx update：也可以 O(1) ：\frac{n(n+1)(n+2)}{6}

B 写数列

根据题意， b 数组乘 i 之后显然是数组 a 的前缀和，所以 a_i = i \cdot b_i - (i - 1) \cdot b_{i - 1} 。

C 选数

对 a 排序

枚举选择的第一个数 x 和第二个数 y ，他们的和为 a_x+a_y ，可以在 a 里面二分找到最大的 a_z 满足 a_x+a_y+a_z\leq m

枚举时间复杂度为 n^2 二分时间复杂度为 \log n （也可以用 lower_bound ）

总时间复杂度为O(n^2\log n) 可以通过此题

总结：通过二分，将一维时间复杂度压到 \log 即可

D 跳一跳

设 f_i 代表以 i 为结尾且 i 被标记的方案数，那么显然 f_{1} = 1 并且有转移 f_{i + k \cdot a_{i}} \leftarrow f_{i} ，其中 k 是正整数，直接暴力转移时间复杂度为 O(n^{2}) ，可以通过本题。

下面是本题的加强版题解，可自取。

如果 n \le 5 \times 10 ^ {5} ，可以考虑根号分治。

不难发现 f 的转移可以根据 a_i 的大小进行根号分治。如果 a_i \ge \sqrt{n} ，直接暴力每次跳 a_i 进行转移，如果 a_i < \sqrt{n} ，因为从 i 能跳到的所有位置 p \bmod a_i 一定等于 i \bmod a_i ，所以可以直接开一个二维数组记录模 x 等于 y 的位置上被加的贡献。时间复杂度为 O(n\sqrt{n}) 。

E 怎么全是 bug ！？

注意到把 m行代码 这个条件删掉就是完全背包问题。

加上了这个条件就成了有限制的完全背包问题。

所以我们考虑多加一维来限制代码行数。

设 f_{i,j} 代表写了 i 行代码，j 个 bug 的方案数。

最外层枚举每一个学生，第二层枚举代码行数，第三层枚举写了多少个 bug 。

每次转移就是模拟一个学生写代码产生 bug 的过程就行了，从前一行/还没写这一行代码的状态转移过来即可。

时间复杂度 O(nmb)

F 只是一道简单的搜索

折半搜索（meet in the middle）

我们把这8个数分成前4个和后4个

对于前4个数我们搜索找出所有的集合 \{k_1,k_2,k_3,k_4\} ，令 b_i=a_1^{k_1}+a_2^{k_2}+a_3^{k_3}+a_4^{k_4} 满足 b_i\leq s

不难发现数组 b 不超过 30^4=810000 个。于是我们将数组 b 排序。

对于后4个数我们搜索找出所有的集合 \{k_5,k_6,k_7,k_8\} ，令 c_i=a_5^{k_5}+a_6^{k_6}+a_7^{k_7}+a_8^{k_8}

对于我们找出的每一个数 c_i ，只需要找出满足 b_i+c_i\leq s 的数量即是答案。所以可以二分或者lower_bound在b数组中找到小于 s-c_i 的数的数量，加起来即是答案。

令 k=log_2(maxa)

时间复杂度即为 O(k^\frac n2\log(k^\frac n2))