2022.1.18 模拟赛

蛤?

T1 数论函数(arithmetic)

整了个杜教筛板子搁这儿糊弄人呢?

T2 数列(series)

首先出题人把题解写到题面里了,给你的递推式跟斐波那契一样一样的,告诉你用特征方程解出来是

\[a_i=T\left(A\left(\frac{2}{5}\right)^n+B\left(-\frac{6}{5}\right)^n\right) \]

为了 \(a_i\ge 0\),\(n\to\infty\) 时必须有 \(B=0\),所以 \(a_n=a_0\left(\frac{2}{5}\right)^n\)。

然后就转化为区间推平、区间求和问题,空间比较紧不能动态开点线段树,区间求和的话 ODT 不能直接用 \(\texttt{std::set<>}\),唯一的办法应当是手写平衡树。

T3 树(tree)

首先答案有个上界是只选一个最小值。

然后可能的答案就是一条全是 \(1\) 的链,和一条只有一个 \(2\)、其他都为 \(1\) 的链。

假设这条链上只有一个 \(3\)、其他都为 \(1\),不妨设 \(3\) 两侧有 \(a,b\) 个 \(1\),\(a>b\),有

\[\frac{3}{a+b+1}< \frac{1}{a} \]

可以得出无解。其他情况也是类似的推理。

然后随便树上 DP 拼一拼。


我真的不知道怎么吐槽这个出题人。

T1 只有 \(5\) 分的数据是 \(> 10^7\) 的;T2 区间查询在 \(\texttt{std::set<>}\) 上暴力扫也能过,线段树做法的空间也没卡满。

体验很差,我只想说我花了一上午打模拟赛是很认真的,你却拿脚造数据糊弄人,太过分了把。

上一篇:026 模块3-random库的使用


下一篇:洛谷p1423