几度风雨几度春秋 风霜雪雨博激流
历尽苦难痴心不改 少年壮志不言愁

分类 题解 下的文章

你有一个多项式 P(x)=x,再给定一个次数为 n 的多项式 Q(x),你有两种操作:

选定一个常数 c,把 P(x) 的常数项加上 c。即 P(x) \leftarrow P(x)+c。 选定一个常数 k,把 P(x)k 次幂。即 P(x) \leftarrow P^k(x),其中 \leftarrow 为赋值。

请你给出一种总操作次数最小的构造方案,使用这两种操作把 P(x) 变为 Q(x),并输出方案。如果无解,请输出 -1

所有计算在 \bmod~998244353 的意义下进行。

READ MORE

有个算法比赛只有一道题,共有 n 人参赛,排名方式如右:先比答对题数,答对题数多的人名次在前,但若有多人答对题数相同,则 id 字典序较小的人名次靠前 (已知所有人 id 都不同)。

由于这个比赛参赛人数众多且题目的时间限制极长,所以需要花很多的时间判题。于是比赛结束后会先假设有上传代码的人都答对,并发布在此情况下所有参赛者的名次,直到判题结束后,才发布真正的名次。

现在给你一个数组 a,真正名次为第 i 名的人在判题前的名次为 a_i,首先判断是否存在对应到此数组的可能情况,若有的话,计算答对一题人数的最小和最大可能值。

多组数据1 \leq T \leq 3 \times 10^4,\ 1 \leq \sum n \leq 2 \times 10^5

READ MORE

给定一个长度为 n 的数组 \{a_i\}_{i=1}^nQ 次询问,每次给定 lr 查询 \operatorname{lcm}(\{a_i\}_{i=l}^r),答案对 10^9+7 取模。

多组数据T,n,Q \leq 300,\ a_i \leq 10^{18}

神仙 zx2003 的做法。

READ MORE

给定长度为 n 的序列 \{a_i\}_{i=1}^n,有 q 组询问 [l,r],定义三元组 (A,B,C)

  • 是合法的当且仅当 L \le A < B < C \le R(B-A) \leq (C-B)
  • 的权值为 a_A + a_B + a_C

求给定区间内三元组的最大权值。 n ,q \leq 5 \times 10^5,\ a_i \leq 10^9

READ MORE

给定一个序列 \{a_i\}_{i=1}^nQ 组询问形如 (m_i, k_i)。对于每个询问回答序列前 m 项构成的子序列中长度最长的满足其子序列中不存在长度超过 k 的 LIS 的子序列的长度。

n \leq 5 \times 10^4,\ Q \leq 2 \times 10^5,\ 1 \leq k_i \leq m_i \leq n

READ MORE

给定 k 种颜色的球,第 i 种颜色有 w_i 个,每次可以选取 1 种颜色 t,将剩下 k-1 种颜色的球各取出 1 个,染成颜色 t,求有多少本质不同的方案,答案对 998244353 取模。

k \leq 10^5,\;\sum_{i=1}^n w_i \leq 10^6

READ MORE

给定 n\{a_i\},满足 a_0 \geq a_1 \geq \cdots \geq a_{n - 1} \geq 0,求出在 n 维空间中从 (0, 0, \ldots, 0) 走到 (a_0, a_1, \ldots, a_{n - 1}),每一步使某一维坐标增加 1 的方案中随机选出一种,满足经过的所有点 (x_0, x_1, \ldots, x_{n - 1}) 都满足 x_0 \geq x_1 \geq \cdots \geq x_{n - 1} 的概率,答案模 1004535809 输出。

n, a_i \leq 5\times 10^5

READ MORE

定理:确定分块大小后,至多只有一种划分方案。

暴力 DP

DFS 自底向上计算,用 dp_u 表示到 u 为止,未被分块的节点个数。

每次需要重新枚举块的大小,时间复杂度为 O(n \cdot \sigma(n)) ,会获得 TLE 的好成绩。

巧妙的优化

有个显然的事情就是每个点只能属于一个联通块。

也就是说,前面我们统计的那个 dp_u ,在做到 u 这个点时,要么把自己和子树未被分配的点分到同一个块内,要么就留着自己等着之后配。也就是说,每个联通块的最高点(深度最浅点)一定满足其子树大小是当前块大小 size 的倍数。

可以证明如果以 size 为大小分块有一种划分方案,那么至少存在 n / size 个点的子树大小是 size 的倍数,反之亦然。

我们可以直接统计下每个点的子树大小放在桶里,然后枚举下分块大小去扫描。复杂度显然低于调和级数的复杂度,故上届为 O(n \log n) ,可以通过此题。

READ MORE