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篇）

送礼物（算法竞赛进阶指南 P105，双向搜索）

一.题目链接：送礼物二.题目大意：大容量背包问题. 三.分析：直接搜会 T 掉，那么就双向搜索. 先搜一半，把答案记录下来，再搜后一半，二分查找即可. 四.代码实现： #include <set> #include <map> #include &l...

2019-08-16

0 779

Addition Chains （POJ - 2248，迭代加深搜索）

一.题目链接： POJ-2248 二.题目大意：序列 x 有如下性质： ① x[1] = 1 ② x[m] = n ③ x[1] < x[2] < ... < x[m - 1] < x[m] ④ 对于每个 k （2 ≤ k ≤ m），都存在两个整数 i，j ...

2019-08-16

0 560

题解 | 算法竞赛进阶指南生日蛋糕（DFS + 剪枝）

一.题目链接：生日礼物二.题目大意：目标为做一个体积为 πn 层数为 m 的蛋糕. 并使得蛋糕从上到下，半径与高度均递增. 现往蛋糕上抹奶油（覆盖蛋糕表面，最底层的底面除外）为了使花费最小，找出一种制作蛋糕的方法，使得奶油的覆盖面积最小. 输出奶油...

2019-08-16

6 1012

All men are brothers（2019牛客暑期多校训练营（第九场）E，并查集 + 线段树）

一.题目链接： All men are brothers 二.题目大意： n 个人，m 次操作. 每次操作让两个人交朋友，朋友关系互逆且可传递. 每次操作后，输出四人组的种数，使得这四个人中每每两个人均不为朋友. 三.分析：并查集很容易想到，这题其实可以用组合数学来解的，可惜我太菜，...

2019-08-16

1 822

Sticks （POJ - 1011 ，DFS + 强力剪枝）

一.题目链接： POJ-1011 二.题目大意：给你 n 个小木棍，要求将其中不超过 50 长度的木棍拼成若干个木棒. 并且使木棒的长度均相同，最后输出木棒的最小长度. 三.分析：这道 dfs 剪枝快剪成了。。。 ①：确定答案的的范围：答案必定比最长木棍长且必定为不超过 5...

2019-08-14

0 872

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

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

2019-08-14

0 655

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

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

2019-08-13

0 506

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

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

2019-08-13

0 755

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

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

2019-08-12

0 603

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

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

2019-08-09

0 620