F round 题解

A.Flattening

这轮，这个A还是有点难，好多选手都挂了…

$O(N^3)$ 版本

1. 计算 $num[i][j], interval[i,…,j]$ 仅存在一块时需要改变的元素数目
2. $dp[i][k]$ 使得前 $i$ 块的石头中，$\# A_x \ne A_{x+1}\le k$ 需要改变的元素数目 易知，$dp[i][k] = \min_j dp[j][k-1]+num[j+1][i]$

github code

一些小bug

vector [] 操作， uncheck index out of size …也就是说 out of size 返回的值是 未定义的(i.e. 可能是 segment fault，也有可能是很奇怪的值，可见源码)

O(N^2logN) 版本

还没想通。。。

B.Teach Me

• skill[i] 表示拥有第 $i$ 项技能的人的集合(vector，递增顺序存储就好)
• ee[i], 第 $i$ 个人所具有的技能集合

那么对于每个人 $ee[i]$ 来说，它所不能交的人就是 $\bigcap_{s \in ee[i]} skill[s]$,注意由于 $|ee[i]|\le 5$, 上面的求解过程最坏是 $O(N)$,将ee去一下重，然后在暴力算就行了

github code

C.Spectating Villages

这波似乎全是dp..

树形dp，挺简单的..不说了

github code

细节

这题有个挺坑的地方，map,比 unordered_map 慢太多了，所以大数据就挂了，有时候能用unordered_map的还是就用unordered_map,比较好

版权声明

本作品为作者原创文章，采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

作者: taotao

仅允许非商业转载，转载请保留此版权声明，并注明出处