教练说我们数据结构太差,让我们多做点数据结构题。

CF176E Archaeology

树上 k 个点的导出子树边权和即将他们按 dfs 序排序后 \displaystyle \frac 12 \sum_{i=1}^{k} \operatorname{dis}(a_i, a_{i \bmod k+1}) 。根据 dfs 序开个 std::set 乱搞即可。

CF380C Sereja and Brackets

线段树,每层记录下左边不匹配的右括号和右边不匹配的左括号个数。

CF609E Minimum spanning tree for each edge

给定 n 个点 m 条边,对于每一条边分别计算固定这条边后的最小生成树权值

可以写 LCT 动态维护 MST ,或者直接 LCT / 树剖查询链上最大值

CF359D Pair of Numbers

定义一个区间是合法的当且仅当这个区间里每一个树都是区间中的某一个数的倍数,求极长的合法区间的个数、长度和位置

枚举被固定的那个数,然后线段树 + 二分一波即可

CF555B Case of Fugitive

有一些不相交线段和一些桥,桥可以架在两个相邻的线段上。求现有的桥是否可以使所有线段连通

排序后贪心

CF555C Case of Chocolate

动态开点线段树

none

已有 6 条评论

  1. 兹磁洛谷 兹磁洛谷

    哇太强了我一个题都不会做欸

  2. 一般提高400+要学什么数据结构呢?NOIP很少有像省选这种专门考数据结构的题吧~~
    线段树、平衡树、树状数组,应该够了吧qwq
    今年11月第一次打TG,不知道数据结构要学多少.....

    1. 都学上好了,不过要上四百应该都用不上

  3. 在您的博客里水着水着就看到您又发了一篇博客orz

    请问还有别的好题吗?蒟蒻也想跟着做做。

    1. 这篇博客里没什么好题啊 QAQ

      其实我的博客很多博文都是不公开的(((出于一些特殊缘故

      如果您感兴趣的话可以 QQ 上找我