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$ 。

全部评论

推荐最新楼层

11-25 19:33

南京理工大学 C++

C++选手秋招总结

秋招进行到现在终于能写总结了。完全没想到战线会拉这么长，过程会如此狼狈，不过更应该怪自己太菜了。好在所有的运气都用在了最后，也是有个去处。背景：双2本硕科班，无竞赛，本科一段研究所实习，硕士一段大厂暑期实习但无转正。技术栈是C++ & Golang，实习是客户端音视频（而且是鸿蒙端开发），简历两个C++项目一个Golang项目。主要投递岗位：后端，cpp软开，游戏服务端，测开，以及一些不拘泥于Java的岗位。从8月起总共投递123家公司，笔试数不清了，约面大约30家。offer/oc/意向：友塔游戏（第一个offer，面试体验很好，就是给钱好少南瑞继保（计算机科班点击就送（限男生），不...

乡土丁真真：佬很厉害，羡慕~虽然我还没有到校招的时候，也想讲一下自己的看法：我觉得不是CPP的问题，佬的背书双2，技术栈加了GO，有两段实习。投了123，面了30.拿到11个offer。这个数据已经很耀眼了。这不也是CPP带来的吗？当然也不止是CPP。至少来说在这个方向努力过的也会有好的结果和选择。同等学历和项目选java就会有更好的吗？我个人持疑问态度。当然CPP在方向选择上确实让人头大，但是我觉得能上岸，至于最后做什么方向，在我看来并不重要。至于CPP特殊，有岗位方向的随机性，java不是不挑方向，只是没得选而已。也希望自己以后校招的时候能offer满满