Day49 【强联通分量】

今天的题相对较板，是我的错觉嘛？

杀人游戏

由于每个人是杀手的概率是等价的，因此如果查证了 $x$ 个人，那么安全的概率就为 $\frac{n-x}{n}$，问题转化为最小化查证的人数。

对于某个强联通分量，我们任选一个人都可以确定整个联通分量的身份，所以很自然的想到把原图缩点得到新图，我们又很自然的发现，我们只需要确定完入度为 $0$ 的强联通分量 ，整个图就确定了。

所以 $x=\sum [i{n}_i=0]$ ？？？看起来非常正确，但是 Wrong Answer，我们忽略了一种情况：如果原图一个点的后继都可以由其他点确定，且它的入度为 $0$，那么我们无需查证它，因为最后恰好只会剩下它一个未被查证，这是合法的。

考虑完这种情况就结束了。

Pro-Professor Szu

把 $36500$ 看成 $35600$ 硬控自己和 $\text{Limury}$ 一个多小时！！！
把 $36500$ 看成 $35600$ 硬控自己和 $\text{Limury}$ 一个多小时！！！
把 $36500$ 看成 $35600$ 硬控自己和 $\text{Limury}$ 一个多小时！！！

不难看出，如果我们走入了一个 $siz\ge 2$ 的强联通分量，那么就会有无穷多条路径。

所以我们先建反图，然后跑拓扑，如果当前点到 $n+1$ 的任意一条路径上有任意一个点是强联通分量，那么当前点就会有无穷多条路径，否则正常 $dp$ 算方案数即可。

注意有自环的情况，把这种情况视为 $siz\ge 2$ 的强联通分量即可。

还有个小细节是 $n+1$ 不能作为答案出现，因为它是主楼不是住宅楼。

抢掠计划

缩点板子题。

原图缩完点后跑拓扑求最长路，完了。

Two Faced Edges

假设当前考虑到边 $u\to v$

注意到有两种情况：

• 原图中存在一条 $v\to u$ 的路径。
• 原图中存在一条 $u\to v$ 且不经过当前边的路径。

考虑如下的局面：

• 情况 $1$ 成立且情况 $2$ 成立，此时无论 $(u,v)$ 反不反向，$u$ 和 $v$ 都在一个强联通分量里，所以强联通数目不会改变。
• 情况 $1$ 不成立且情况 $2$ 不成立，$u$ 和 $v$ 互不可达，此时 $(u,v)$ 的方向不产生任何影响，所以强联通数目不会改变。

所以当且仅当两个情况中恰好一个成立，强联通数目才会改变。

具体实现上，不妨枚举起点，第一种情况直接从该点开始 dfs，第二种情况先跑一边 dfs，标记一下那些边被选了，到达一个点判断 $u\to v$ 对应的边是否被选，然后把存边顺序 reverse 一下，再重复一遍上述过程即可。

建造军营

感觉是最有思维含量的一题。

不难发现在同一个强联通分量里的点，无论 $B$ 删哪条边都没有影响，所以自然而然想到缩点。

边双缩点后是棵树，所以优先考虑树形 dp。

很自然想到一个 $d{p}_{i,0/1}$ 表示第 $i$ 个点是否建造军营，其子树内合法的方案数目。
然而这样难以转移，并且状态数难以再增多了，所以我们考虑对 $dp$ 增加限制：

• $d{p}_{i,0}$ 表示该点子树内都不建造军营的方案数（包括自己）。
• $d{p}_{i,1}$ 表示该点建造军营，且通过只走被防御的边可以到达子树内所有其他建造军营的点的方案数。。
• 两种状态都限制除 $i$ 子树内都不建造军营。

这样就好转移了，假设 $i$ 有某一个儿子 $j$，有如下四种转移：

• $i$ 已处理过的子树内无军营，且 $j$ 子树内无军营，该边可选可不选，有 $d{p}_{i,0}\leftarrow d{p}_{i,0}\times d{p}_{j,0}\times 2$。
• $i$ 已处理过的子树内无军营，且 $j$ 子树内有军营，该边必选，有 $d{p}_{i,0}\leftarrow d{p}_{i,0}\times d{p}_{j,1}$。
• $i$ 已处理过的子树内有军营，且 $j$ 子树内有军营，该边必选，有 $d{p}_{i,1}\leftarrow d{p}_{i,1}\times d{p}_{j,1}$。
• $i$ 已处理过的子树内有军营，且 $j$ 子树内无军营，该边可选可不选，有 $d{p}_{i,1}\leftarrow d{p}_{i,1}\times d{p}_{j,0}\times 2$。

初始状态有：$d{p}_{i,0}=1,d{p}_{i,1}=2^{si{z}_i}-1$，其中 $si{z}_i$ 表示 $i$ 所属的强联通分量的大小，注意这里没有考虑边。

接下来考虑除了 $i$ 子树内割边的其它边的选择情况：

注意这里有一个去重小技巧，当前 $i$ 建造军营，那么我们钦定其父边不选，如果选的话那么这种方案肯定会在处理其父节点时候被统计到，做到了不重不漏。

所以对于每一个点都有 $ans\leftarrow ans+d{p}_{i,1}\times 2^{m-cn{t}_i-1}$，其中 $cn{t}_i$ 表示 $i$ 子树内割边的数量。
注意根节点没有父边！！！所以是 $2^{m-cn{t}_i}$。

所驼门王的宝藏

感觉这种建边方式已经烂大街了啊，很板。

不妨给每行给予一个新点，并把其向当前行所有点连边。
同理每一列给予一个新点，并把其向当前列所有点连边。

考虑宝藏的连边：

• $t_i=1$，当前点向行连边。
• $t_i=2$，当前点向列连边。
• $t_i=3$，当前点直接向 $8$ 个方向的格子连边。

然而这样会爆空间，考虑优化。

• 显然只有包含宝藏的行和列才有用，把行和列的数量缩减为 $n$。

• 同理只有包含宝藏的点才有用，所以行只向当前行内的宝藏连边，列同理，同理 $8$ 个格子有宝藏的才连边。

具体实现上，把宝藏的 $x,y$ 坐标离散化下来，给有宝藏的行和列给予新点就好了。

剩下的就是缩点跑最长路，和 T3 一模一样。

Knights of the Round Table

显然能坐在一桌的人两两之间有边，那么就是一个环，且题目限制了其是奇环。
那么坐在一桌的人肯定位于一个点双里，注意我们限制这里的点双满足 $siz\ge 3$。

所以相当于求有多少个点不在任意一个奇环上，也即求哪些点出现在了奇环上。

有一个结论，如果一个点双内有一个奇环，那么点双中所有点都出现在某一个奇环上，给出简易证明：

• 整个点双是一个大奇环，显然正确。
• 点双中有一个小奇环，那么剩下的点一定构成了另一个奇环，因为总点数为偶数。

而联通块存在奇环与联通块不是二分图是充分必要条件，所以只需要二分图染色判定即可。

原文地址：https://blog.csdn.net/cqbzliuhongyi/article/details/142826610

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！