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

对于一个 1 \cdots n (n \leq 5 \times 10^5) 的排列 p_{1 \cdots n} ,定义 next_i 为第一个 j 满足 i < j, p_i < p_j ,如果不存在这样的 j ,则 next_i = n + 1 。给定一个缺失若干位的 next 数组,求构造任一合法的 p 数组。

READ MORE

一个 n ( n \leq 17 ) 个节点的树,和一个 n 个节点的图,要求给出一个 1 \cdots n 的排列 p_{1 \cdots n} ,满足树上任意一条边 (u,v) ,图中一定要有边 (p_u, p_v) ,求方案数。

READ MORE

有一个 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 + 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

当中考与 OI 风格的游记碰撞在一起,会摩擦出怎样的火花呢?

Q: 为什么写的是「杭州中考」而不是「杭州中考 2019」?

A: 因为貌似抽不到再来一次。

READ MORE