作者： itewqq

发布于

[训练指南][字典树][简单] strcmp的比较次数 UVa11732

题目给了strcmp()的代码，然后问给出n个串两两之间strcmp总共会用到多少次==操作。建立一棵字典树，节点信息存储一个前缀之前出现的次数即可，另外还需要存储的信息是当前节点 是多少个串的结束点（这样就不用把’\n’也加入树了）

坑点的话，自己wa的原因是没有看到他大小写数字都可以有TAT我用我的只考虑了小写字母的Trie送了好几发wa（貌似每次这种题出错都是这样？

继续阅读“[训练指南][字典树][简单] strcmp的比较次数 UVa11732”

发布于

[训练指南][字典树] 使用前缀关系进行递推 字典树加速 LA 3942

题意给一个字符串和单词字典，问把字符串分割成词典中存在的单词可以有多少种方法（单词可以重复使用）首先是像dp那样考虑，令d(i)为从第i个字符开始到结束的字符串的方案数，然后可以得出d(i)=sum{d(i+len(x))|单词x是S[i,l]的前缀}。然后就是找一个串有多少个单词前缀了。。。字典树搜索即可搞定，就是在Trie中查找S[i,l]，一路查过去把遇到的是单词节点的地方加上那里的d就可以了。
继续阅读“[训练指南][字典树] 使用前缀关系进行递推 字典树加速 LA 3942”

发布于

[训练指南][单调队列][DP] 滑动窗口单调队列优化线性dp 输出格式坑 LA3983

我上次wa两个小时是什么时候？？？妈的这个题格式。。。提示一个PE能死啊我去

直接暴力dp很好想但是复杂度爆炸，经过转换后可以把i和j分离开，然后j的那一部分就成了独立的只跟j有关的，这时候就可以把他当成一个新的量，然后求的时候就是在weight(j+1,i)<c的条件下（可以发现这其实是一个滑动的窗口）求出使得wav最小的j，就很像基本的dp了，只不过求最小j的时候用单调队列优化了。 继续阅读“[训练指南][单调队列][DP] 滑动窗口单调队列优化线性dp 输出格式坑 LA3983”

发布于

[训练指南] 树形DP 多目标最优化 有优先级的优化量 UVa10859

题意给出森林，让在放置的点数尽量少的情况下保证每条边都被点覆盖到（乍一看二分图匹配？），然后在此前提下再要求被两个点同时覆盖到的边最多。两个需要解决的的：1 怎么把这个多目标最优化解决了 2  怎么处理不同节点之间的影响

继续阅读“[训练指南] 树形DP 多目标最优化 有优先级的优化量 UVa10859”

发布于

[训练指南] 复习线段树区间修改 基本操作题 UVa11992

感觉真的是被期末考试掏空身体了，，，这个代码自己写完之后调试出来5个bug，没办法对照着lrj的代码一行一行看才找到所有错误。。都是泪啊

题也就很简单，本身都是基础操作没什么可说的，只是set标记优先级在add标记之上罢了
继续阅读“[训练指南] 复习线段树区间修改 基本操作题 UVa11992”

发布于

[算法学习] 可持久化线段树基础题 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 集合问题 二进制状态枚举所有集合”