AtCoder ABC213 简要题解
这世道连 \(\rm ABC\) 都要写题解来续命了。。。
A - D
略。
E
有如下观察:
- 对于任意的四个方格,出去之后再回来可以调整为先在内部走到固定位置再走出去。
因此只需要考虑在一开始把内部的走法都连上即可不用考虑重复计算贡献的问题。
因此我们考虑对于每个点 \(P\) 按照下图连边:
.###.
##L##
#LPL#
##L##
.###.
对于每个 \(L\),若 \(L\) 不为障碍,我们从 \(P \rightarrow L\) 连一条边权为 \(0\) 的边;否则连边权为 \(1\) 的边。
对于每个 \(\#\),我们从 \(P\) 向其连一条边权为 \(1\) 的边。
注意到边权只有两种,于是可以使用双队列做到 \(\mathcal{O}(nm)\)。
更进一步的,我们发现边权为 \(0, 1\),那么实现的时候可以直接使用 \(\rm deque\) 代替优先队列。
F
对字符串 \(S\) 建出后缀树。
对于每个后缀,在后缀树上的祖先节点权值 \(+1\),每个后缀的答案就是祖先节点上权值之和,离线树上差分即可。
复杂度 \(\mathcal{O}(|\Sigma|n)\),注意由于后缀树是压缩的因此要考虑长度。
G
令 \(f_S\) 为只考虑 \(S\) 这个导出子图内部的边使得 \(S\) 联通的方案,\(cnt_S\) 为 \(S\) 这个导出子图内部的边,那么答案为:
\]
这部分可以直接计算,复杂度 \(\mathcal{O}(n2 ^ n)\),接下来考虑如何计算 \(f\)。
考虑容斥,不难得到转移(注意集合是无标号的,因此我们钦定一个元素在枚举集合内,由于本题需要求的 \(S\) 必须包含 \(1\),于是可以直接钦定 \(1\) 在枚举的子集内):
\]
由于本题数据范围较小,可以直接计算,复杂度 \(\mathcal{O}(3 ^ n)\)。
当然可以使用 \(\rm FWT\) 优化子集 \(\rm DP\) 做到 \(\mathcal{O}(n ^ 22 ^ n)\),好久没写过子集卷积了,于是写了这个做法。
H
考虑 \(\rm DP\),令 \(f_{i, j}\) 表示当且走到第 \(i\) 个点,已经走完了 \(j\) 的路程的方案,由于路径长度均 \(>1\) 所以可以直接转移。
考虑使用生成函数来刻画转移,令 \(F_i(x) = \sum\limits_j ^ \infty f_{i, j} x ^ j, G_{i, j}(x) = \sum\limits_{k = 1} ^ \infty p_{i, j, k}x ^ k\),那么有转移:
\]
做半在线卷积即可,复杂度 \(\mathcal{O}(mT \log ^ 2T)\)。
最新文章
- sql 补齐字段位数
- SPOJ : DIVCNT2 - Counting Divisors (square)
- oracle数据库从入门到精通之三
- 控制文本和外观------Style Binding(Style属性绑定)
- 选中CheckBoxList的值放到TextBox中,再次选中从textBox中删除
- Mac中QT程序发布
- angular 选中切换面板
- python编码你需要知道的编码风格
- 新建虚拟机_XP系统(二)
- Jquery 表单提交后3s禁用
- Underscore-逐行分析
- sql 和xml
- [KVM][guestfs] 安装 guestfs-python 出错
- Git的一些用法(下)
- ubuntu 终端$换行
- SQL SERVER 的操作复习
- ViewData和ViewBag的那些事
- 【MySQL优化】使用show status查看MySQL服务器状态信息
- 洛谷 P3393 逃离僵尸岛
- go语言学习之路 二:变量