Codeforces Round #606 (Div. 1)

前言

可能当场上橙的场次，字符串防 $AK$ 题根本看不到啊，虽然赛后也写了好久qwq。

题解

D - Tree Elimination

等价于求不同操作序列的个数，考虑树形 $dp$ 。
令 $dp[u][s]$ 为以 $u$ 为根的子树在节点 $u$ 的删除情况为 $s$ 的方案数， $p$ 为 $u$ 的父亲。 $s$ 共三种：

$s=0$ ， $u$ 在遇到节点 $p$ 前被删除。
$s=1$ ， $u$ 在遇到节点 $p$ 时被删除。
$s=2$ ， $u$ 在遇到节点 $p$ 后被删除。

显然三个状态相互独立，考虑如何转移。
将 $u$ 的 $n$ 个儿子 $v$ 按照 $idx[u,v]$ 排序，其中 $idx[u,v1...v_k]<idx[u,p]$ ， $idx[u,v_{k+1}...v_n]>idx[u,p]$ 。

如果 $u$ 在遇到 $p$ 之前被删除，那么 $u$ 必然在与某个儿子 $v_i$ $i\in[1,k]$ 相遇时被删除。
依次考虑这样的 $v_1,v_2,v_3...v_k$ ，如果 $u$ 被 $v_i$ 删除,则 $v_i$ 必须在遇到 $u$ 之后被删除，则 $v_j$ $j\in[1,i-1]$ 需在遇到 $u$ 之前或者遇到 $u$ 时被删除， $v_j$ $j\in[i+1,n]$ 则可以在遇到 $u$ 前被删除或遇到 $u$ 之后被删除但是不能在遇到 $u$ 时被删除。
于是显然有 $dp[u][0]=\sum_{i=1}^{k}(\prod_{j=1}^{i-1}(dp[v_j][0]+dp[v_j][1])*dp[v_i][2]*\prod_{j=i+1}^{n}(dp[v_j][0]+dp[v_j][2]))$ 。
如果 $u$ 在遇到 $p$ 时被删除，则 $v_i$ $i\in[1,k]$ 需要在遇到 $u$ 之前或者遇到 $u$ 时被删除， $v_i$ $i\in[k+1,n]$ 需要在可以在遇到 $u$ 之前或者遇到 $u$ 之后被删除但是不能在遇到 $u$ 时被删除。
于是显然有 $dp[u][1]=\prod_{i=1}^{k}(dp[i][0]+dp[i][1])\prod_{i=k+1}^{n}(dp[i][0]+dp[i][2])$
如果 $u$ 在遇到 $p$ 之后被删除，假设 $u$ 在遇到 $v_i$ 时被删除，那么对于 $v_i$ $i\in[1,i-1]$ ， $v_i$ 必须在遇到 $u$ 之前被删除或者遇到 $u$ 时被删除，则 $v_i$ $i\in[i+1,k]$ 必须在遇到 $u$ 之前或遇到 $u$ 之后被删除， $v_i$
那么 $dp[u][2]=\sum_{i=k+1}^{n}(\prod_{j=1}^{i-1}(dp[v_j][0]+dp[v_j][1])*dp[v_i][2]*\prod_{j=i+1}^{n} (dp[v_j][0]+dp[v_j][2]))+\prod_{i=1}^{n}(dp[v_i][0]+dp[v_i][1])$ ，后者为不删除的情况qwq。
而叶子节点 $u$ 的初值为 $dp[u][0]=0,dp[u][1]=1,dp[u][2]=1$ 。

全部评论

推荐最新楼层

2025-12-28 16:32

重庆邮电大学 Java

28双非一段实习，这简历能冲中大厂吗

菜菜，救救，帮帮😭😭😭   

程序员花海：1.技能放最后，来面试默认你都会，技能没啥用 2.实习写的看起来没啥含金量，多读读部门文档，包装下接LLM这个没含金量也不要用重构这种不会给实习生做的 3.抽奖这个还是Demo项目，实际在公司里面要考虑策略，满减，触发点，触发规则库存之类的，不是这个项目这么简单 4.教育背景提前，格式为教育背景实习项目技能自我评价

简历被挂麻了，求建议

点赞评论收藏