CF 刷题计划 4

发布时间 2023-10-26 20:40:13作者: jiangtaizhe001

应该是 OI 退役前最后一次发「CF 刷题计划」了。
难度范围实时浮动,取决于智商浮动。

反正也不会再出模拟赛了,所以干脆都放上来吧。

难度标识(0-5 保留一位小数):
标准参考
1 一眼丁真
2 需要时间思考
3 需要题解提示
4 需要仔细阅读题解

CF1430G Yet Another DAG Problem

2600 3.2
tag: 状压 DP,图论,构造
状压DP,考虑转移顺序。
按照拓扑序一层一层转移,由于答案为 \(\sum \texttt{系数和}\times\texttt{这一层填的数字}\)。新建一层新的一层填 \(1\),其余的在原有基础上加 \(1\),所以直接加上所有的系数和即可。
新一层合法当且仅当新一层的所有入边都在原来的点集里。
\(O(3^n+2^nn)\)
https://codeforces.com/contest/1430/submission/229855729