这几天可能都会做各地省选题，所以这段时间就先放下新算法的讲解，重点讲解这些经典套题，那么几天就让我们走进SCOI 2006 DAY 1的奇幻旅程吧！ T1 zh_tree 题目描述： Description 张老师根据自己工作的需要，设计了一种特殊的二叉搜索树。他把这种二叉树起名为zh_tree，对于具有n个结点的zh_tree，其中序遍历恰好为(1，2，3，…，n)，其中数字1，2，...
昨天打了一下2005年的SCOI，虽然已经是十多年前的省选题了，但是很多题目还是不能一次AC（我太菜了QwQ），下面就让我来讲讲这套题的解法吧 T1 超级格雷码 题目描述： Description: 著名的格雷码是指2n个不同n位二进制数（即0~2n-1，不足n位在前补零）的一个排列，这个排列满足相邻的两 个二进制数的n位数字中最多只有一个数字不同（例如003和001就有一个数位不同，...
这几天我们市赛被其他选手吊起来打orz，在这之前自己学习了一下主席树，真的不长啊（40行以内），这篇文章我们就一同走进神奇的主席树吧|´・ω・)ノ 什么是主席树呢 传统意义上的主席树就是可持久化线段树，什么叫可持久化呢？就是这棵树啊，很持久(划掉)可以记录每一次修改的内容，换句话说，就是可以访问这棵树的历史记录。是不是很厉害呢？ 那么这种数据结构为什么要叫主席树呢？相传，发明主席树的人叫...
看了中山纪念中学宋新波dalao在NOI2018雅礼冬令营的分治算法后，大受启发，参考了一下dalao的PPT，下面就来讲一下神奇的分治算法的四种经典应用。 分治思想 分治(Divide-And-Conquer)就是“分而治之”的意思，其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。 其三个步骤如下： ①划分问题(D...
上篇博客我们重点讲解了tarjan算法的实现以及它最重要的用法——求解强连通分量。这篇博客我们就继续学习一下tarjan的其他经典用法。 运用tarjan求割点 什么是割点 在无向连通图中，如果将其中一个点以及所有连接该点的边去掉，图就不再连通，那么这个点就叫做割点（cut vertex / articulation point） 例如，在下图中，0、3是割点，因为将0和3中任意一个去掉...