D

给定一个序列,$p_i$表示树的父亲,$p_i = i$表示根
求最小的修改次数使序列构成一棵树

贪心

首先确定根,剩下的节点只有三个情况

  • 在根的连通块 (不处理)
  • 不在根的连通块,构成环 (任意拆一个点到根)
  • 不在根的连通块,不构成环 (把连通块的根并到确定的根上)

E

有n个元素,选定每个元素的概率为$p_i$
有一个长度为k的队列,每次选一个元素进队(若在队中则将其换到队尾)
若队列满,则队首出队
问$10^{100}$次后每个元素在队列中的概率

概率DP

$d_{s} = d_{s}(\sum_{i in s}p_i - p_j) + \sum p[j]d_{s - j}$
$d_{s} = \frac{\sum p_jd_{s - j}}{\sum_{\text{i in s}}p_i - p_j}$
$ans_j = \sum_{\text{j in s and |s|} \leq k} {d_s}$