hungry123

题解题解

题解

/ 注册

题解

9 浏览 0 回复 2024-12-15

hungry123

+关注

https://ac.nowcoder.com/acm/contest/98726/A

前言

powered by 翘课协会
感谢 @pitless0514 @Zyh_277 的题目，感谢 @喜多鱼的物资准备
出题组预期难度

E<G<K<H<J<D<A<I<B<F<C
实际难度

G<E<K<H<D<J<I<B<F<A<C

正文

easy

E：等差数列

每次找到一段连续的最长等差数列 $[L,R]$ ，假设序列长度为 $k$ ，对答案的贡献就是 $\frac{k\times(k-1)}{2}$ ，之后继续在 $R$ 的后面找就行

记得加上长度为 $\rm 1$ 的等差数列

具体细节看代码

G：maximum independent set(easy version)

答案就是小于等于 $n$ 的素数个数

晒好质数后，做一个前缀和即可直接统计小于等于 $n$ 的素数个数

medium-easy

K：足球

二分初始容量 $k$

分别维护左右箱子的剩余量以及通用的容积，如果对应的箱子还有空余，则直接放入，否则令多出的球占用通用的容积即可

通用的容积在每次放入球之前加一

时间复杂度： $\rm O(n\log{n})$

H： maximum independent set(hard version)

诈骗题

首先证明 $n$ 个数字为何不能选取 $\lceil \frac{n}{2}\rceil 1$ 个数字

把每个数字都分解为 $2^k\times p$ 的形式，其中 $p$ 是奇数，这样 $n$ 个数字可以分为 $\lceil \frac{n}{2}\rceil$ 组，每组数字只能选取一个，根据鸽笼原理，最多选取 $\lceil \frac{n}{2}\rceil$ 个数字

其次构造大小 $\lceil \frac{n}{2}\rceil$ 的集合

直接输出 $\lfloor\frac{n}{2}\rfloor \sim n$ 即可

J：ptsd

数据结构优化 $\rm dp$ 的板子

令 $f_j$ 表示选取子序列中最后一个数字为 $j$

枚举 $i$ ，然后更新

$f_{a_i}=\max\{f_j\}(j \leq a_i-k \cup a_i k \leq j)$

值域线段树维护即可

D：相对分子质量

是一道给写不动其他题或者卡某个签到题的选手拉回差距的题目

但是看起来卡住了一些人（）

原题链接

medium

I： maximum independent set(extremely hard version)

选取较大的数只有可能与一个数的和是 $2$ 的幂次，但是选取较小的数可能影响更多，所以需要贪心的选取较大的数字

考虑对于一个区间 $[L, R]$ ，找到最大的 $2^k\leq R$ ，如果区间 $[2^k, R]$ 数字全选，那么区间 $[2^{k 1}-R, 2^k-1]$ 中间的数字全不选（会与选择的数字的和组成 $2^{k 1}$ ）

之后考虑区间 $[L, 2^{k 1}-R-1]$ 的子问题即可

时间复杂度： $\rm O(q\log{n})$

B：中位数（easy version）

考虑最后一定只剩下一个数字 $\frac{n}{2} 1$ 是满足条件的

令小于这个数字的数变为 $-1$ ，大于这个数字的数变为 $1$ ，做前缀和，记前缀和数组为 $sum$

设这个数字位置为 $k$ ，最优方案下，第一次一定是找到 $k$ 左端的第一个 $L$ 和右端的第一个 $R$ ，有 $sum_L=sum_R=0$ ，然后对区间 $[L,R]$ 进行操作

之后每次操作，向左移动一次 $L$ 或者向右移动一次 $R$ ，每次移动的要求是保证 $sum_L=sum_R=0$

假设有 $a$ 个 $i$ 使得 $sum_i=0$ 且 $i<k$ ，有 $b$ 个 $i$ 使得 $sum_i=0$ 且 $i>k$ ，总操作次数就是 $a b-1$ ，方案数为 $\binom{a b-2}{a-1}$

需要特殊考虑 $sum_k=0$ 的情况，这时第一次操作可以只使区间变为 $[L,k]$ 或者 $[k,R]$ ，最多操作数变为 $a b$ ，方案数为 $\binom{a b}{a}$

medium hard

A：匹配

$\sum\limits_{i=1}^{2n}i=n(2n 1)$ ，这个数对 $2n$ 取模为 $n$
$\sum\limits_{i=1}^{n}i=\frac{n(n 1)}{2}$ ，这个数对 $2n$ 取模为 $0$ 或者 $n$

考虑如何取到 $2$ 式

对于 $\bmod\ n$ 的剩余类，每个余数 $r$ 都恰好有两个数字与其对应（ $r,r n$ ），如果选择了其中的一个，一定要保证另外一个不选；如果其中一个不选，一定要保证选择另外一个

拿一组数据举例子

其中令 $1,4$ 为一组， $2,5$ 为一组， $3,6$ 为一组

首先选取 $1$ ， $5$ 不能选，强制选取 $2$ ， $3$ 不能选，强制选取 $6$ ， $4$ 不能选，强制选取 $1$

会发现，这种关系一定会形成一个环

这样子一直遍历下去，一定能保证每组数字恰好选取了一个

如果现在选取的数字和是 $2n$ 的倍数，直接输出答案即可；如果不是 $2n$ 的倍数，那么每一组交换选取的数字即可（根据题解开篇的等式可推出）

时间复杂度： $\rm O(n)$

F： multiply

注意到我们并不关心最后一个子序列具体乘积是多少，只关心这个子序列乘积是否 $\geq m$ 。

所以我们设计状态为 $f_{i, x}, g_{i, x}$ 表示当前考虑到了 $1 \sim i$ ，子序列乘积需要 $\times x$ 才能 $\geq m$ 的方案数和权值。

此时对于 $\geq m$ 的子序列乘积，他们都会等于 $g_{i, 1}$ ，因为此时表示子序列乘积 $\times 1 \geq m$ ，即子序列乘积已经大于等于 $m$ 。

而剩下的可能状态其实就是对每个 $i\in [1, m]$ ，都有 $\lceil \dfrac{m}{i} \rceil$ ，注意到这是一个整除分块的形式，经典结论可知只会有 $\sqrt{m}$ 级别的不同的数，单独处理之后，每次枚举这些状态和当前的值 $a_i$ ，刷表转移即可，转移方程看具体代码

时间复杂度： $O(n\sqrt{n})$

整除分块学习

其实这题的预期是 $\rm hard$ 难度，但是不少精通 $\rm dp$ 的选手切的很快哇

hard

猫猫头说不清，所以

@Zyh_277 催更

（这位鸽鸽在准备下周的 $\rm icpc$ 港澳，大家不要催他了，为他加油！！！）

举报

收藏

赞

评论加载中...