The__Flash

分类

-------------各大OJ-------------(54) 2018 - 2019 寒假训练(29) POJ(2) SDNU ACM-ICPC 2019 Training We(1) UVA(3) ZOJ(3) 博弈(3) 容斥原理(3) 未归档(135) 模拟(3) 牛客(1) 算法竞赛入门经典(7) 莫队算法(2) 贪心(3) 题解(4)

/ 注册

全部文章（共253篇）

荷马史诗（算法竞赛进阶指南 P81，K 叉哈夫曼树）

一.题目链接：荷马史诗二.题目大意：给出每个单词的出现次数. 现要求用 k 进制数设计前缀编码. 使得文章总长度最小. 输出文章总长度的最小值和最长单词编码的最小长度. 三.分析：很容易想到哈弗曼树. 这里是 k 叉哈弗曼树，对应 0 ~ k - 1. 有一点需要注意：初...

2019-08-07

0 506

Supermarket（ POJ - 1456，小根堆 + 贪心）

一.题目链接： POJ-1456 二.题目大意：有 n 个商品. 每个商品有两个属性，保质期天数和利润. 一天只能卖一个商品且过期的商品无法销售，求最大利润. 三.分析：首先对保质期由小到大排序. 准备一个小根堆存放商品的利润. 小根堆的大小 size 表示 1~size ...

2019-08-07

0 574

Super Mario （HDU - 4417，主席树查询区间小于 k 的个数）

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

2019-08-07

0 558

three arrays （HDU - 6625，字典树 + 贪心）

一.题目链接： HDU-6625 二.题目大意：给两个长度为 n 的数组 a，b. 定义 c = a ^ b. 先让你变换 a，b 中元素的顺序，使得 c 的字典序最小. 三.分析：看到第一眼就想到字典树了，可是有些地方不会写...... 赛后发现其实不难，本质与这道题一样，就是...

2019-08-07

0 517

The XOR Largest Pair（算法竞赛进阶指南 P72，Trie）

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

2019-08-06

0 523

后缀数组（算法竞赛进阶指南 P64，字符串 Hash + 二分答案）

一.题目链接：后缀数组二.题目大意：给字符串 s 的所有后缀按照字典序排序. 输出排序后的编号和排序后后缀数组 i 与 i - 1 的最大前缀长度. 三.分析：如果直接用 sort 对每一个后缀排序，时间复杂度为，需要优化. 在 cmp 函数中，对于两个后缀 a，b 来讲...

2019-08-05

0 469

Palindrome （POJ - 3974 ，字符串 Hash + 二分 || Manacher）

一.题目链接 POJ-3974 二.题目大意：求 s 的最大回文子串长度. 三.分析：此题可以用字符串 Hash + 二分或者是 Manacher 算法.（后者明显比前者块）由于这是 Manacher 的模板题，所以这里只讲第一种方法. O（N）扫描字符串 s，建立前缀与后缀...

2019-08-05

0 611

兔子与兔子（算法竞赛进阶指南 P62，字符串 Hash）

一.题目链接：兔子与兔子二.题目大意：给一个串 s. q 次询问，每次询问给出 l1, r1, l2, r2. 让你判断 s[l1, r1] == s[l2, r2] ? 三.分析：感觉这个挺 nb 的，就写个博客（题解请见书）纪念一下. 字符串 Hash 可以 O（...

2019-08-05

0 656

Snowflake Snow Snowflakes （POJ - 3349 ，Hash表查找）

一.题目链接： POJ-3349 二.题目大意：有 n 片雪花，每片雪花有六个角，若六个角均相同，则称两片雪花相等. 雪花六个角的记录可能顺时针，可能逆时针，开始点不确定. 让你判断是否存在两片相同的雪花. 三.分析：居然还有考 Hash 表的题一直觉得数据结构课本很鸡肋题目...

2019-08-05

0 458

最大子序和（算法竞赛进阶指南 P53，单调队列）

一.题目链接：最大子序和二.题目大意：给出长度为 n 的序列，求长度不超过 m 的最大子序和. 三.分析：单调队列模板题 ps：这里 q[] 存的是开区间左端点大佬的博客：单调队列学习四.代码实现： #include <set> #include <...

2019-08-05

0 449