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

• Add a b： 表示在 a 与 b 之间连了一条长度为 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

本文写于 2019-04-28 16:03 公开于 2019-06-23 09:24

此题有一个神仙的转换为染色 + dp 做法，可以参考 这篇文章 ，然而我不会，神仙马文浩看懂了。

为了方便我们生成函数，此处的 d_i 表示第 i 个联通块的度数 -1 ，即题目中的 d_i 减掉 1 后的值。

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

定义 \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

前一晚打 CF 打到好晚，只能考试的时候补觉。。。

READ MORE

竟然签了。

READ MORE

定义一个图是好图当且仅当：

• 这个图只有一个点
• 这个图可以被划分为若干个好图
• 这个图的补图是好图

求 n 个点的的本质不同的好图数量，定义两个好图是本质相同的当且仅当可以通过重标号一个好图得到另外一个。

READ MORE

要求给出 k 不同的组合数使他们的和最大，要求对于其中的每个组合数 \displaystyle \binom n m 满足 0 \leq n \leq m \leq N 。定义两个组合数 \displaystyle \binom {n_1} {m_1} 和 \binom {n_2} {m_2} 不同当且仅当 n_1 \neq n_2 \text{ or } m_1 \neq m_2。

READ MORE