月度归档： 2018 年 7 月

发布于

[算法学习] 可持久化线段树基础题 SPOJ D-query

题意问给出一个序列然后q个询问问[l,r]之间有多少种不同的数。这里最简单的思想就是用可持久化线段树，每加入一个点作为一个版本，然后如果某一个点之前出现过那么就在新版本里把那个位置点的计数-1，再把现在这个位置+1，这样的话要求[l,r]中的数字有多少种那就只需要对第r个版本的线段树求[l,r]之间的和就行了，思路并不复杂（毕竟入门题 继续阅读“[算法学习] 可持久化线段树基础题 SPOJ D-query”

发布于

[算法学习] 可持久化线段树基础题 K-th Number

终于要搞可持久化数据结构了

在综合看了了n个大犇的博客和clj的论文之后总算是写了第一道可持久化线段树的题目。话说SCU真的很严格，这个代码在其他地方都过了就是在SCU上TLE。。。所以这个更快版本的今天先放着以后搞出来再说。。。

其实思路倒也不是很复杂，首先说求[1,n]的第k大。 继续阅读“[算法学习] 可持久化线段树基础题 K-th Number”

发布于

[训练指南]UVa11825 状压dp 集合问题 二进制状态枚举所有集合

感觉如果早知道那个快速枚举子集的算法的话其实也就很简单。。太弱了orz

这个问题可以抽象成，将n个集合划分成尽可能多的组，满足约束每个组里的集合之和（所有的相或）都是全集，在这里注意这里说的原本的集合是对应于题中的节点的，一个节点和与他相邻的所有节点这一坨东西算一个基本集合。N<=16，很容易想到用二进制数字来表示集合，比如P[1]=011010表示1节点对应的集合里有1，3，4这三个节点。然后要预处理出不同每个原来的集合之间相或的结果用cov表 继续阅读“[训练指南]UVa11825 状压dp 集合问题 二进制状态枚举所有集合”