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

后缀数组（算法竞赛进阶指南 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

Upgrading Technology（2019牛客暑期多校训练营（第六场）J，预处理 + 枚举）

一.题目链接： Upgrading Technology 二.题目大意：有 n 件物品，每个物品都有 m 个等级. 当物品 i 从等级 j - 1 升级到时 j 时，需花费 c[i][j]. 当所有物品都超过 j 级时，将会获得 d[j]. 三.分析：枚举最低等级，根据贪心的原...

2019-08-05

0 809

七夕祭（算法竞赛进阶指南 P29，中位数 + 思维？）

一.题目链接：七夕祭二.题目大意：中文题不解释. 三.分析： { 根据移动规则易得：上下交换两个点，该列中所需摊位个数不变. 左右交换两个点，该行中所需摊位个数不变. 那不妨先上下移动实现 row ，再左右移动实现 col. 立即推：若 t 为 n 的倍数，则可实现 r...

2019-07-26

0 585

Inviting Friends （HDU - 3244，二分 + 完全背包）

一.题目链接： HDU-3244 二.题目大意：有 n 种原料，每种原料有 6 个属性. x：每个人需要此原料的量 y：已有的量 s1：小包原料的数量 p1：小包原料的价钱 s2：大包原料的数量 p2：大包原料的价钱现有 m 元，求最多的人数. 三.分析：二分人数，ch...

2019-07-25

0 688

Second Large Rectangle（2019牛客暑期多校训练营（第二场）H，全 1 次大子矩阵）

一.题目链接： Second Large Rectangle 二.题目大意：给你一个 n × m 大小的由{0，1} 组成的矩阵. 求全由 1 构成的子矩阵中面积的次大值，不存在则输出 0. 三.分析：求存在障碍点的最大子矩阵，可以用悬线法或单调栈. 不过这里让求次大子矩阵（悬线法...

2019-07-22

0 1103

Kth Minimum Clique（2019牛客暑期多校训练营（第二场）D，K 大完全子图）

一.题目链接： Kth Minimum Clique 二.题目大意：有 n 个点，有着各自的点权. 给出连通的边. 求权值 k 大的完全子图. 三.分析：由于 n ≤ 1e3，所以直接暴搜即可. 这里和状压 DP 有点像，搜索的是状态以及对应的权值. 考虑状态的转移，比如在什么...

2019-07-22

0 896

Plants vs. Zombies （ZOJ - 4062，二分答案 + 细节）

一.题目链接： ZOJ-4062 二.题目大意： n 个植物排成一排. 水壶只能移动 m 步. 水壶一步移动一个单位长度，所到达的位置，该植物的防御值会相应增加. 求浇水之后，所有植物防御值中最小值最大可以为多少. 三.分析：二分答案即可. 不过要加限制条件，在 check(mi...

2019-07-20

0 446

Plants vs. Zombies （ZOJ - 4062，二分答案 + 细节）

一.题目链接： ZOJ-4062 二.题目大意： n 个植物排成一排. 水壶只能移动 m 步. 水壶一步移动一个单位长度，所到达的位置，该植物的防御值会相应增加. 求浇水之后，所有植物防御值中最小值最大可以为多少. 三.分析：二分答案即可. 不过要加限制条件，在 check(mi...

2019-07-20

0 526