ZROI466小 G 的数
最近从某个地方看到了这个题。。。所以回来补一下题解。题目描述 题解直接求期望不太好求，我们可以考虑求出每一种条件下的概率，最后乘上直径长度就可以了。 我们设 $f_{i,j,k}$ 表示在以 $i$ 为根的子树里，目前不跨过 $i$ 节点的最长链是 $j$，子树的直径是 $k$ 的概率。 转移就用树 dp 合并子树那种方法来做...枚举一下根与待合并的子树之间的边权就可以了。 转移方程就咕了...
最近从某个地方看到了这个题。。。所以回来补一下题解。题目描述 题解直接求期望不太好求，我们可以考虑求出每一种条件下的概率，最后乘上直径长度就可以了。 我们设 $f_{i,j,k}$ 表示在以 $i$ 为根的子树里，目前不跨过 $i$ 节点的最长链是 $j$，子树的直径是 $k$ 的概率。 转移就用树 dp 合并子树那种方法来做...枚举一下根与待合并的子树之间的边权就可以了。 转移方程就咕了...
题目链接题目大意现在有一个 $n\times m$ 的矩阵，给定的起始点上有个钢琴，矩阵上有些方格是障碍物，用连续的区间 $[l,r]$ 和一个参数 $d$ 表示在时间 $[l,r]$ 时会向 $d$ 方向滑动（上下左右），当然每个时间点可以选择让钢琴不动，不允许钢琴超出边界或者碰到障碍，询问钢琴可能走的最远距离是多少。 其中 $1 \leq n,m \leq 200$,区间个数 $k \l...
题目链接题意有长度为 n 的序列，定义一个集合的代价是$(MAX-MIN)^2$，要求你找出 m 个集合，在满足下面图片的限制的情况下，使得总代价最小。 多组数据，每组数据 $n \leq 10^4,m \leq 5 \times 10^3$，保证答案在 int 范围内。题解观察题目 发现让你选取 M 个集合使得代价最小。 首先一个观察是，取得代价最小的方案一定是按照排序后按顺序取的，并且...
题目链接题目描述题目大意：给你前 $alphabet$ 个小写字母组成的字符集，以及 $n$ 个单词，定义一个串 s 的禁忌值为 $\sum_{i} [s[i] == Taboo[i]]$，其中 $Taboo[i]$ 是第 $i$ 个单词（禁忌值也就是找到一种分割字符串的方法 使得出现这N个字符串的次数最多的次数）。现在给定一个长度 $len$，求随机一个用字符集生成的长度为 $len$ 的...
没想到非 Chinese Round 也会出这么毒瘤的题目......题目大意：对于正整数序列 $A$，定义序列 $B$： $B_1=A_1,B_i=B_{i-1}\ or\ A_i,i\in[2,n]B $ 其中 or 为位或运算。 每一个序列合法，满足对于$ \forall i\in[1,n]$，有 $A_i\in[1,2^k])$ 而且对于 $\forall i\in[2,n]$，有$...