The__Flash

未归档

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

/ 注册

全部文章 / 未归档（共135篇）

矩阵距离（算法竞赛进阶指南 P109，BFS）

一.题目链接：矩阵距离二.题目大意：给你一个 n × m 的 01 矩阵 A，现求矩阵 B. 三.分析：每个点 BFS 肯定会 T. 一开始想的是从（1,1）开始搜，记一下曼哈顿距离，之后二分查找做差，写完之后发现思路根本不对。。。正解是把每个 1 在一开始加到队列...

2019-08-17

0 656

Snowy Smile （HDU - 6638，稀疏矩阵子矩阵最大和）

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

2019-08-14

0 640

Sort （HDU - 5884，K 叉哈弗曼树）

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

2019-08-13

0 493

Sudoku （POJ - 3074，DFS + 位运算优化）

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

2019-08-13

0 739

可达性统计（算法竞赛进阶指南 P93，拓扑排序 + 状态压缩）

一.题目链接：可达性统计二.题目大意：给定一张N个点M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。三.分析：第一想法是暴搜。。。。（我是不是没救了） T是肯定的了。。。对于每个点 x，他所能到达的点的个数 == y 能到达点的个数 + 1，其中存在 x 到 y...

2019-08-12

0 587

Sliding Window （POJ - 2823，单调队列求区间最值）

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

2019-08-09

0 612

荷马史诗（算法竞赛进阶指南 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

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 524