标签 巧妙的思路 下的文章

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

有一个 n 个数的序列,每一个数在 1 \dotsc D 中随机生成,定义一个序列是合法的当且仅当能取出至少 m 个对子(相同的数),对于 D^n 种可能的序列,求合法序列数。D \leq 10^5, n, m \leq 10^9

羡慕你们能去 CTS 的 [大哭]

READ MORE

定义一个基环树的点分治过程如下

  • 选定一个点 u
  • 断开所有与 u 相连的边
  • 对于剩下的每个联通块递归点分

定义一种选点方式的代价为每层的 size 之和。

求每次选点都在当前联通块内随机选择的期望代价。

n \leq 3000

READ MORE

给定 n 个节点的树,每个点有个权值 a_i,保证 \{a_{1 \cdots n}\} 是一个 1n 的排列,求:

\frac 1 {n(n-1)} \sum_{i=1}^n \sum_{j=1}^n \varphi(a_i \times a_j) \times \operatorname{dist}(i, j)

READ MORE