「JZOJ6284」玩具
链接题目描述随机一棵以 $1$ 为根，且节点编号满足小根堆性质的树的期望最大深度。 $n \leq 200$题解这个题我考试的时候连 $n \leq 20$ 都不会..还是自己太菜了。一开始的一个想法是记 $f_{i,j}$ 表示前 $i$ 个点深度为 $j$ 的树的个数，然后发现不太能转移需要记录最后一层的节点个数。。然后还要记录前面层的所以复杂度就炸了。 然后我们考虑放宽限制，对森林计数...
链接题目描述随机一棵以 $1$ 为根，且节点编号满足小根堆性质的树的期望最大深度。 $n \leq 200$题解这个题我考试的时候连 $n \leq 20$ 都不会..还是自己太菜了。一开始的一个想法是记 $f_{i,j}$ 表示前 $i$ 个点深度为 $j$ 的树的个数，然后发现不太能转移需要记录最后一层的节点个数。。然后还要记录前面层的所以复杂度就炸了。 然后我们考虑放宽限制，对森林计数...
题目链接题解一个我想不到的性质：每个点至多会被覆盖两次。 因为如果一个点被覆盖三次，那么肯定有一条线段的效果是可以被另外两条完全表达出来的，所以可以删去这个线段。 我们先将线段按照右端点排个序，有了这个性质，又因为它是个最优化问题，启发我们设 $f_{i,j}$ 表示考虑到了前 $i$ 个线段，最后一段被覆盖了一次的线段是 $[j,r_i]$ 的最小代价。答案就是所有 $r_i = n$ 的...
题目描述令 $s_i$ 表示第 $i$ 个字符串，我们有递推式 $s_i = s_{i-2}+s_{i-1}$（其中+ 是将两个字符串拼接起来的符号） 现在需要你构造出长度为 $n$ 的 $s_1$ 和长度为 $m$ 的 $s_2$ ，满足 $s_k$ 中串 AC 作为子串出现了 $x$ 次。 $3 \leq k \leq 50,0 \leq x \leq 10^9,1 \leq n,m \...
C - Minimization普及组题，不说了。 代码D - Snuke Numbers题意将 $x$ 的数字和记作 $S(x)$。 称 $n$ 是好的，当且仅当 $\forall m>n, n \leq m$ 。 求第 $K$ 个好的数字。 保证答案不超过 $10^{15}$。题解全场最难的题。。。 我们设 $f(x)$ 表示满足 $\forall t>x ,\frac{t}{S(t)}...
题意给你若干限制，限制为 $lca(u,v) = c$ 和 $(u,v)$ 有连边，数一下以一为根的满足限制的树的个数。 $n \leq 13$，限制总数 $\leq 100$题解这个题目太神仙了。。远古 CF 场的题目还是好。 考虑设 $f_{v,S}$ 表示 $v$ 节点子树内的点是 $S$ 的树的个数。答案是 $f_{0,U}$ （将点的标号减一后） 首先我们考虑一下不考虑限制怎么转移...