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

分类 题解 下的文章

有一个 n (n \leq 20) 的骰子,分别写着 0 \cdots (n - 1) ,每个数被投掷出来的概率是相同的,现在我们投掷了 m (m \leq 2\times10^5) 次,造成的伤害为 m 次骰子的点数和 \xi ,求 Pr[a \leq \xi \leq b]

Link

READ MORE

DZY 开始有 n 个点,现在他对这 n 个点进行了 m 次操作,对于第 i 个操作(从 1 开始编号)有可能的三种情况:

  • Add a b: 表示在 ab 之间连了一条长度为 i 的边(注意,i 是操作编号)。保证 1 \leq a,b \leq n
  • Delete k: 表示删除了当前图中边权最大的 k 条边。保证 k 一定不会比当前图中边的条数多。
  • Return: 表示撤销第 i−1 次操作。保证第 1 次操作不是 Return 且第 i−1 次不是 Return 操作。

请你在每次操作后告诉 DZY 当前图的最小生成树边权和。如果最小生成树不存在则输出 0

n \leq 3\times10^5, m \leq 5\times10^5

Link

READ MORE

给定 n 和一个数组 \{s\} ,对于满足一下条件的五元组 (a, b, c, d, e)

  • 0 \leq a, b, c, d, e \leq n
  • (s_a | s_b) & s_c & (s_d ^ s_e) = 2^i ,其中 i \in \mathbb{N}
  • s_a & s_b = 0

能够给答案产生 f(s_a | s_b) \times f(s_c) \times f(s_d ^ s_e) 的贡献,其中 f 是斐波那契数列,即 f(0) = 0, f(1) = 1.\forall i > 1, f(i) = f(i - 1) + f(i - 2)

READ MORE

依次抛 n + m 枚硬币,每次有 p 的概率正面朝上, 1 - p 的概率反面朝下。其中 p 是给定的常数且对 T 组数据均相同。已知其中 n 次正面朝上,剩余 m 次反面朝上。维护一个计分器 s ,如果硬币是正面那么使 s 自增,如果硬币是反面且 s 是正数,那么使 s 自减。求 s 的期望。
(n + m), T \leq 2.5 \times 10^5, 0 < P' < 1000 ,其中 P' = P / 1000

Link

READ MORE

定义 \otimes_1, \otimes_2, \otimes_3 分别为按位与、按位或、按位异或运算。记 a_i 表示 a 的从低位到高位的第 i 个二进制位。定义一个作用在 w 位二进制数上的新运算 \oplus,满足对于结果 a\oplus b 的每一位 (a\oplus b)_i(a\oplus b)_i = a_i \otimes_{o_i} b_i。不难验证 \oplus 运算满足结合律和交换律。

给出一张 n 个点 m 条边的无向图,每一条边的权值是一个 w 位二进制数(即小于 2^w 的非负整数)。请你找一棵原图的生成树。设你找出的生成树中的边边权分别为 v_1,\cdots,v_{n-1},请你最大化 v_1\oplus v_2\oplus\cdots\oplus v_{n-1}

READ MORE

\forall i \in [1, n] ,连续性随机变量 f[i][0, 1] 范围内生成,\forall i < j, f_i < f_j 存在一条 i \leftrightarrow j 的双向边,求联通块的大小的期望乘积。

READ MORE

假设序列有多段最大前缀和,我们只取右端点最左的那一段。已知每个序列都有唯一的最大前缀和 \operatorname{sum}(1, k) 且满足 \operatorname{sum}(2 \cdots k, k) > 0 \text{ or } \operatorname{sum}(k, k + 1 \cdots n) \leq 0

考虑状压 DP ,分别枚举左边和右边的数,然后合并起来即可。需要注意处理下 \operatorname{sum}(1, k) \leq 0 的情况。

READ MORE