Skip to content

Latest commit

 

History

History
45 lines (27 loc) · 3.05 KB

D6.md

File metadata and controls

45 lines (27 loc) · 3.05 KB

题意:

给定一个长度为 $N$ 的排列 $a$,定义一个排列是合法的当且仅当标记的数满足单调递增。 每次等概率选择一个未标记过的且标记后序列合法的数标记,无法标记时结束,求期望的标记个数。 对 $10^9+7$ 取模。($N\le 2000$)。

题解:

这题我自己思考的时候掉进了一个概率学的怪坑——因为它的选到的概率必须依赖于前面的概率,并且选到每个点的概率是会动态变化并且连数据结构都难以维护……在追求正确的过程中,我探索期望的前路被堵上了。

那么这时,就像上次那个 Nim 那题那样,我们直接假设一个 $f_{l,r}$,表示区间 $(l,r)$ 的期望次数,这时你会发现这个期望可以直接统计了,不会有什么平均分布之类的问题: $$ f_{l,r}=\frac 1{r\left(l,r\right)}\cdot\left(r\left(l,r\right)+\sum_{k\in[l,r],a_k\in(a_l,a_r)}f_{l,k}+f_{k,r}\right) $$ 然后这个显然可以树状数组优化,时间复杂度:$O(n^2\log n)$,评测链接:AC Submission

题意:

给定一棵 $N$ 个点的树,每个点可能染成黑色也可能染成白色,定义一种染色方案的权值为 所有黑色点中距离最远的两个点的距离 和 所有白色点中距离最远的两个点的距离 的最大值,询问所有可能染色方案的权值之和。 对 $10^9+7$ 取模,$N\le 1e5$。

题解:

这种问题先考虑直径,如果直径的两个端点是同种颜色,则直接把答案加上 $2^{n-1}\times D$;如果不同呢?

对于不是端点的一个点,离它最远的点一定包含直径的端点,那么这个点的 MaxDis 就在两个端点中选一个就行了。

根据这个条件,我们有一种巧妙的转化:$Ans=\sum_{k=1}^{+\infty}\sum [P_i\ge k]$,然后我们只需要统计答案大于等于每个 $k$ 的方案数;大于这个条件,直接统计不容易,我们补集转化,变成小于的方案数。

记每个点的到两个端点的距离分别为 $A_i,B_i$,当 $k\le min(A_i,B_i)$ 无解;当 $k\in[\min,\operatorname{max}]$ 时只有一种选择;当 $k\le \operatorname{max}$ 的时候有两种选择;求前缀积就可以了。

复杂度:$O(N\log N)$,评测链接:AC Submission

题意:

给定一个长度为 $K$ 的序列 $a$。判断是否存在一个满足下列条件的序列 $P$,若存在则输出字典序最小的 $P$$P$ 中只包含 $1\sim K$ 之间的数且数 $i$ 出现 $a_i$ 次。 对于 $P$ 中任意一个位置 $x$,都存在一个区间 $[l,r]$ 满足 $l \leq x\leq r$$P_l,P_l+1…,P_r$ 是一个长度为 $K$ 的排列。