牛客网2022河南萌新联赛第（二）场：河南理工大学总结

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16488033.html

比赛总结

比赛情况

排名：14 / 1393
AC：10 / 12

题目总结

A

首先假如两数 $\gcd$ 不为1，中间有些地方就走不到，所以要求两数 $\gcd$ 为1

注意特判1、1的情况

B

问是否存在多少 $x$ 满足 $a_x=a_b\times a_c\times a_d\;\;(b,c,d>x)$

观察 $n\leqslant 1500$，考虑 $O(n^2\log n)$

移项：$\dfrac{a_x}{a_b}=a_c\times a_d$，然后右边用 $map$ 存起来，左边逐个枚举

关于限制问题，用map记录 $c,d$ 中较小值即可

然后发现超时，思考后发现由于 $a_i\leqslant 10^6$，可以直接用数组来存，复杂度 $O(n^2)$

C

模拟题，按题意模拟即可

D

要使 $\sum_{i=l}^r a_i\geqslant x+(r-l+1)\times y$，可以让 $a_i$ 先全部减个 $y$，变成 $\sum_{i=1}^r a_i\geqslant x$

用前缀和优化成 $S_r-S_{l-1}\geqslant x$，即 $S_r\geqslant S_{l-1}+x$，分别排序后跑个双指针，为了满足 $l\leqslant r$，套个树状数组优化即可

时间复杂度 $O(n\log n)$

E

F

$x^{\frac 2 3}=\sqrt[3]{x^2}$，相当于判断 $\sqrt[3]x$ 是否为有理数

把 $n$ 分解成一堆质因子乘积，要使其满足条件，每个质因子的幂次方必然是3的倍数，然后乘法原理乘起即可

因为某个质因子的幂次方如果小于3，可以直接忽略，所以质因子的循环范围到 $\sqrt[3]n$ 即可

时间复杂度 $O(\sqrt[3]n)$

G

打表输出前20个数，丢到oeis上，发现 $ans_n=f_{n+2}-1$，其中 $f_n$ 表示斐波那契数列第 $n$ 项

证明留坑

H

I

分两种情况讨论，位数小于 $n$，位数等于 $n$

先讨论位数小于 $n$

设 $f_{i,j}$ 表示 $i$ 位数和为 $j$ 的方案数，直接枚举这一位是什么:

$$\Large f_{i,j}=\sum_{k=0}^{\min(j,9)}f_{i-1,j-k}$$

初始化即 $f_{1,i}=1\;(i\in [1,9])$

答案是所有 $\sum f_{i,2\times i}$

位数等于 $n$ 的情况同理，但就是要加一个上界判断

J

要使 $a+b+c=d$，移项得 $a+b=d-c$，分别枚举用map维护即可

复杂度 $O(n^2\log n)$

K

很明显，加入原先乘了，下一次就是除，原先除了，下一次就是乘

然后就可以打棵线段树维护了

如果完全被包含，输出区间和-当前和即可

不被包含就标记下传

L

签到题

赛后总结

开场看到J交签到，果断点开，发现真得签到，2min时过

刷新排行榜，L题一堆人过，马上做，发现真签到题，4min时过

然后发现A很多人过，盲猜个gcd结论6min时wa了，调不出，F过的人似乎不少，去看看

过去看F，25min时交了一发，wa了，调了调，27min时过了

然后发现有几个人过了G，看完题后果断oeis，40min时过

然后回去调A，42min和46min各交一次，都wa了

发狂，B也过了些人，跑去看，感觉和J题类似，70min交了一次，发现除了0，70min再交一次，t了，觉得是map问题

把map改成数组，72min时交一发，发现有个地方没改完，72min再交一次，Al

C过得人不少，跑去看，发现就是个纯模拟，97min时A了

看看D，前面性质都推出来了，想用set，不会用，然后电脑死机，重启后就丢一边了

回去调A，131min时交了一次还是wa，后来终于想到时没特判1，1情况，133min时A了

捡回D，不会set，干脆用双指针+树状数组来做，145min时A

然后看看I，发现就是个dp，不过要分类讨论一下，174min时A了

最后看K，显然是个线段树，不过要弄个标记下传，197min时A了

剩下40分钟，发现E和H几乎很少人做出来，果断放弃