09-05 21:08 绵阳师范学院 C++ 发布于浙江

关注

小白月赛 120 出题人题解

A 牛牛的串串

用一个 map 维护字母出现次数，遍历 map 判断第二元是否依次加 1 即可。时间复杂度： $O(n\log n)$

牛牛的合数

特判 $1,2,3$ 的无解。

反之大于 $2$ 的偶数一定是合数，所以 $x$ 为奇数输出 $1$ ， $x$ 为偶数输出 $2$ 即可。

牛牛的排列

分类讨论：

特判 $n=2$ 时无解。

$n$ 为奇数，构造 $1,2,...,n$ 即可
$n$ 为偶数，构造 $4,2,1,3,5,...,n$ 即可

牛牛的子序列

每一个元素独立。

首先将 $a,b$ 中每一段相同元素视作一个整体，然后贪心匹配，若 $A_i\ne B_i$ 或者 $A_i$ 的数量比 $B_i$ 多则无解。

反之这一段的操作次数为 $\lceil\log_2|cnt[A_i]-cnt[B_i]|\rceil$ 。

总操作次数就是每一段操作次数的最大值。

使用双指针维护合并，时间复杂度： $O(n)$ 。

牛牛的约数

实际上这个问题约束很弱。

将原序列升序去重后，对于每个元素，如果直接枚举 $j\in[1,n]$ ，就是 $O(nd(V))$ 的。

而如果 $j$ 从 $i-1$ 开始枚举到 $1$ ，容易发现是很快就会找到解的，容易证明一个宽松的上界： $O(n\log V)$ ，因为如果 $a_{i-1}>\frac{a_i}{2}$ ，那么 $i$ 的答案就是 $i-1$ ，反正 $a_{i-1}\le\frac{a_i}{2}$ 跑暴力，最多跑 $O(\log V)$ 次暴力。

不过出题人认为远远达不到这个上界，但是不会证明更紧的上界。

以及一些其它的神秘写法，可能都是对的，而非错的。

牛牛的三角形

古典概型，计算合法方案数除以总方案数即可。容斥，合法方案等于总方案减去不合法方案。

根据三角形三边之和大于第三边性质，容易发现，若将选出来的边长升序，得到的相邻两个数的间距至少是一个斐波那契数列。

打表可得斐波那契数列在第 17 项后就会超过 1500，所以 $m\ge 17$ 时总是合法。

反之 dp 选出来的数即可， $dp_{i,j,k}$ 表示 $[1,i]$ 选出来 $k$ 个数，上一个数是 $j$ 的方案数，前缀和优化转移即可。

时间复杂度： $O(n^2\times 16)$ 。

全部评论

推荐最新楼层

Light_Cone

南京理工大学 golang

F 可以做到 O(16 * 16 * n). 考虑构造非法集合，必定是在长度为 m 的 fib 序列上进行增量。令 g_1 = f_1 + c_1, g2 = f_2 + c_2, 递推 g_m = g_{m - 1} + g_{m - 2} + c_n，则得到最终 g_m = f_{m - 1} + sum f_i c_i ，即要求 g_m <= n 即可。方案数即 c_i 的合法解，通过完全背包算出恰好的方案数，前缀和即可。

7 回复分享

发布于 09-05 21:42 江苏

GeometryFeng

北京邮电大学算法工程师

E鉴定为单调栈，先排序去重，当前的数能被栈顶整除就弹出（栈顶的数不优于当前数），最后如果空了就是-1，否则栈顶就是当前答案，时间复杂度O(n)

4 回复分享

发布于 09-05 23:12 河北

Nekorya

北京邮电大学 C++

E可以证明排序后第i个数要找的范围仅为[l,i-1]，其中l为最近的ans[]设为-1的位置。 ans[l]= -1代表前l-1个数都是a[l]的因数，如果a[i]不整除a[l]，答案为l,否则a[1~l-1]必定能被a[i]整除。a<=1e18,[l,i-1]的长度最长为64，复杂度64n

点赞回复分享

发布于 09-06 10:28 北京