一.题目链接： POJ-1011 二.题目大意： 给你 n 个小木棍，要求将其中不超过 50 长度的木棍拼成若干个木棒. 并且使木棒的长度均相同，最后输出木棒的最小长度. 三.分析： 这道 dfs 剪枝快剪成  了。。。 ①：确定答案的的范围：答案必定比最长木棍长 且 必定为不超过 50 木棍长度和的约数. ②：优化搜索顺序. ③：vis 标记去重 + 最优性剪枝 + 排除等效冗余剪枝. ④：空木棒的等效剪枝 + 贪心剪枝. 详见代码. 四.代码实现： #include <set> #include <map> #include <ct...

一.题目链接： HDU-6638 二.题目大意： 求稀疏矩阵子矩阵最大和. 三.分析： 离散 x 坐标，枚举 x. 线段树维护区间最大子段和 将  的算法优化到了  详见代码. 四.代码实现： #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <bitset> #include <vector> #include &...

一.题目链接： HDU-5884 二.题目大意： 给出 n 个数 和 一个数 t. 求最小的 k 值，使得这 n 个数对应的 k 叉哈弗曼树的 wpl 不大于 t. 三.分析： 二分 k 即可. 如果直接用优先队列模拟会 T. 这里用数组模拟. 详见代码. 四.代码实现： #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <bits...

一.题目链接： POJ-3074 二.题目大意： 就是普通的数独问题. 三.分析： 暂时没学跳舞链，这里用 dfs 写了一下. 这里需要预处理出好多东西，不然 T 死你. 以及各种优化，二进制 + 位运算 和 每次优先选取可能数少的点. 详见代码. 四.代码实现： #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <bitset&gt...

一.题目链接： 可达性统计 二.题目大意： 给定一张N个点M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。 三.分析： 第一想法是暴搜。。。。（我是不是没救了） T是肯定的了。。。 对于每个点 x，他所能到达的点的个数 == y 能到达点的个数 + 1，其中存在 x 到 y 的有向边. 那么，我们可以先拓扑排序，得到拓扑序列，之后倒序遍历，统计个数即可. 统计时，可用 bitset 统计，按位与之后所得到的即为 x 点能到达的点. 四.代码实现： #include <set> #include <map> #include <c...

一.题目链接： POJ-2823 二.题目大意： 有 n 个数，用一个窗口去扫描，窗口大小为 k. 求每次扫描得到的最小值与最大值. 三.分析： 单调队列 O（N）扫描即可. 又加深了自己对单调队列的理解. 四.代码实现： #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <bitset> #include <vector&...

一.题目链接： 荷马史诗 二.题目大意： 给出每个单词的出现次数. 现要求用 k 进制数设计前缀编码. 使得文章总长度最小. 输出文章总长度的最小值和最长单词编码的最小长度. 三.分析： 很容易想到哈弗曼树. 这里是 k 叉哈弗曼树，对应 0 ~ k - 1. 有一点需要注意：初始有 n 颗树，每次合并会减少 k - 1 棵树. 为了方便，可以加入若干个 0 节点，使得 (n - 1) % (k - 1) == 0. 四.代码实现： #include <set> #include <map> #include <ctime> #i...

一.题目链接： POJ-1456 二.题目大意： 有 n 个商品. 每个商品有两个属性，保质期天数 和 利润. 一天只能卖一个商品且过期的商品无法销售，求最大利润. 三.分析： 首先对保质期由小到大排序. 准备一个小根堆存放商品的利润. 小根堆的大小 size 表示 1~size 天的所售卖的商品. 之后遍历商品. 若该商品的保质期等于 size 且 该商品的利润大于小根堆的堆顶，则删除堆顶，加入该商品. 若该商品的保质期大于 size，则直接将该商品加入堆. 四.代码实现： #include <set> #include <map> #i...

一.题目链接： HDU-4417 二.题目大意： 查询区间小于 k 的个数 三.分析： 这里只是存个板子~~ 四.代码实现： #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <bitset> #include <vector> #include <cstdio> #include <sstream&gt...

一.题目链接： HDU-6625 二.题目大意： 给两个长度为 n 的数组 a，b. 定义 c = a ^ b. 先让你变换 a，b 中元素的顺序，使得 c 的字典序最小. 三.分析： 看到第一眼就想到字典树了，可是有些地方不会写...... 赛后发现其实不难，本质与这道题一样，就是麻烦了点. 我好菜啊.............. ps：用 memset TLE，必须边建树边初始化. 四.代码实现： #include <set> #include <map> #include <ctime> #include <queue&g...

一.题目链接： The XOR Largest Pair 二.题目大意： 有 n 个数，求任意两个数异或得到的最大值. 三.分析： 刚学习了字典树，觉得还不错. 把每个数分解为二进制存到字典树中，查询即可. 四.代码实现： #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <bitset> #include <vector&g...

一.题目链接： 后缀数组 二.题目大意： 给字符串 s 的所有后缀按照字典序排序. 输出排序后的编号 和 排序后后缀数组 i 与 i - 1 的最大前缀长度. 三.分析： 如果直接用 sort 对每一个后缀排序，时间复杂度为 ，需要优化. 在 cmp 函数中，对于两个后缀 a，b 来讲，分别对应 s[a ~ n] 和 s[b ~ n]. 那不妨求出第一个位置，使得 . 这点可用字符串 Hash 前缀 + 二分答案实现. 这样每次只比较 1 个字符，排序函数的复杂度降到了  得到排序后的 SA 数组（记录编号）后，再同样二分前缀最大长度即可. 四.代码实现： #inc...

一.题目链接 POJ-3974 二.题目大意： 求 s 的最大回文子串长度. 三.分析： 此题可以用 字符串 Hash + 二分 或者是 Manacher 算法.（后者明显比前者块） 由于这是 Manacher 的模板题，所以这里只讲第一种方法. O（N）扫描字符串 s，建立前缀与后缀 Hash 数组. 之后枚举回文串的中心位置，二分答案即可. ps：要分别处理奇偶长度的回文串.  的算法，Manacher 的时间复杂度为 ，但用时 Manacher 完胜第一种. 四.代码实现： 字符串 Hash + 二分 #include <set> #include...

一.题目链接： 兔子与兔子 二.题目大意： 给一个串 s. q 次询问，每次询问给出 l1, r1, l2, r2. 让你判断 s[l1, r1] == s[l2, r2] ? 三.分析： 感觉这个挺 nb 的，就写个博客（题解请见书）纪念一下. 字符串 Hash 可以 O（N） 预处理字符串的前缀哈希值，O（1）时间查询任意子串哈希值. 四.代码实现： #include <set> #include <map> #include <ctime> #include <queue> #include <cmath...