lcp专题

LCP 485. 最大连续 1 的个数[lleetcode -11]

从今天起，我们的算法开始研究搜索，首先就是DFS深度优先搜索（depth-first seach，DFS）在搜索到一个新的节点时，立即对该新节点进行遍历；因此遍历需要用先入后出的栈来实现，也可以通过与栈等价的递归来实现。对于树结构而言，由于总是对新节点调用遍历，因此看起来是向着“深”的方向前进。下面是一个一维的DFS算法 LCP 485. 最大连续 1 的个数给定一个二进制数组 nu

树链剖分 + 后缀数组 - E. Misha and LCP on Tree

E. Misha and LCP on Tree Problem's Link Mean: 给出一棵树，每个结点上有一个字母。每个询问给出两个路径，问这两个路径的串的最长公共前缀。 analyse: 做法：树链剖分+后缀数组. 记录每条链的串，正反都需要标记，组成一个长串. 然后记录每条链对应的串在大串中的位置,对大串求后缀数组,最后询问就是在一些链

LCP 633 平方数之和 [leetcode - 8]

最近是在研究双指针啊，leetcode刷的题都是这方面的。都记录在最近的文章里，大家有兴趣可以去我主页看看 LCP633 平方数之和给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。示例 1：输入：c = 5输出：true解释：1 * 1 + 2 * 2 = 5 方法1：食我双指针啊显然，这里是在给定范围内找找两个数字满足

LeetCode LCP 61. 气温变化趋势

别怕麻烦，模拟题有时候就是要多写一些条件（或者你思维很活跃找出规律），代码如下： class Solution {public:int temperatureTrend(vector<int>& temperatureA, vector<int>& temperatureB) {int n = temperatureA.size(),ans = 0,k = 0;for(int

力扣LCP 08.剧情触发时间

力扣LCP 08.剧情触发时间前缀和 + 二分对increase求前缀和在前缀和数组上做二分找到符合要求的最小时间 class Solution {public:vector<int> getTriggerTime(vector<vector<int>>& increase, vector<vector<int>>& requirements) {//第一维increase.si

【一百零四】【算法分析与设计】【模板】二维差分,2132. 用邮票贴满网格图,LCP 74. 最强祝福力场,二位差分,差分思想,记录变化值,离散化技巧

【模板】二维差分描述给你一个n行m列的矩阵，下标从1开始。接下来有q次操作，每次操作输入5个参数x1, y1, x2, y2, k 表示把以(x1, y1)为左上角,(x2,y2)为右下角的子矩阵的每个元素都加上k，请输出操作后的矩阵。输入描述：第一行包含三个整数n,m,q. 接下来n行，每行m个整数，代表矩阵的元素接下来q行，每行5个整数x1, y1, x2, y2, k，分别

leetcode(js) LCP 06. 拿硬币

LCP 06. 拿硬币桌上有 n 堆力扣币，每堆的数量保存在数组 coins 中。我们每次可以选择任意一堆，拿走其中的一枚或者两枚，求拿完所有力扣币的最少次数。示例 1：输入：[4,2,1] 输出：4 解释：第一堆力扣币最少需要拿 2 次，第二堆最少需要拿 1 次，第三堆最少需要拿 1 次，总共 4 次即可拿完。示例 2：输入：[2,3,10] 输出：8 限制： 1 <

LCP poj 2217 寻找最长公共子串

题目：http://poj.org/problem?id=2217 首先解释，DP中的最长公共子序列和此处的最长公共子串区别-------------------序列可以是不连续的，但是子串是连续的其次，LCP，lcp[i]就是lcp[rank[i]]和lcp[rank[i]+1]的最长公共前缀，那么把两个字符串接起来，然后找最长的lcp，就是答案思路还是比较清晰的上代码

CodeForces 1154F: Shovels Shop LCP

传送门题目描述小a要去水果店给队友们买水果，水果店有 n 个水果第i个水果需要 a_i 元. 小a需要购买k个水果，每个水果只能购买一次水果店有m种促销活动，第i种优惠表明小a可以依此优惠购买xi个水果，在购买的xi个水果中，yi个最便宜的可以免费赠送.即买xi个水果免较便宜的yi个水果的花费小a可以使用同一种优惠多次，也可以使用多种优惠，但不可以同时使用两种优惠，当然，他也可

CodeForces 615C: Running Track LCP

传送门题目描述将所给的串反转，所求串分别与正串，反串比较，选择最优的记录分析预处理出正反字符串的lcp，然后暴力比较即可代码 #include <iostream>#include <cstdio>#include <cmath>#include <algorithm>#include <queue>#include <cstring>#define debug(

CodeForces 611D:New Year and Ancient Prophecy DP + lcp

传送门题目描述给一个n位数，要求将该n位数拆分成若干数字，且需满足：数字的顺序要严格递增数字都是正整数没有前导零求所有可能的方案数分析这道题写了好几天了2333 首先如何判断两个A和B谁大谁小首先，如果A长度大于B长度，A大于B，反之亦然如果AB长度相同，那么比较他俩的最长公共前缀，如果等于AB的长度，说明A等于B，如果不等于，那么就比较最强公共前缀的下一位即可我们用数

【Python】【难度：简单】Leetcode LCP 06. 拿硬币

桌上有 n 堆力扣币，每堆的数量保存在数组 coins 中。我们每次可以选择任意一堆，拿走其中的一枚或者两枚，求拿完所有力扣币的最少次数。示例 1：输入：[4,2,1] 输出：4 解释：第一堆力扣币最少需要拿 2 次，第二堆最少需要拿 1 次，第三堆最少需要拿 1 次，总共 4 次即可拿完。示例 2：输入：[2,3,10] 输出：8 限制： 1 <= n <= 4 1 <

【二分图】【二分图最大匹配】LCP 04. 覆盖

作者推荐视频算法专题本文涉及知识点二分图二分图最大匹配 LeetCode LCP 04. 覆盖你有一块棋盘，棋盘上有一些格子已经坏掉了。你还有无穷块大小为1 * 2的多米诺骨牌，你想把这些骨牌不重叠地覆盖在完好的格子上，请找出你最多能在棋盘上放多少块骨牌？这些骨牌可以横着或者竖着放。输入：n, m代表棋盘的大小；broken是一个b * 2的二维数组，其中每个元素代表棋盘上每

力扣OJ（3x）LCP

目录 LCP 01. 猜数字 LCP 02. 分式化简 LCP 06. 拿硬币 LCP 07. 传递信息 LCP 11. 期望个数统计 LCP 14. 切分数组 LCP 17. 速算机器人 LCP 18. 早餐组合 LCP 23. 魔术排列 LCP 24. 数字游戏 LCP 26. 导航装置 LCP 30. 魔塔游戏 LCP 33. 蓄水 LCP 41. 黑白翻转棋

【图论】【割点】【双连通分类】LCP 54. 夺回据点

本文涉及知识点图论割点双连通分类割点原理及封装好的割点类 LeetCode LCP 54. 夺回据点魔物了占领若干据点，这些据点被若干条道路相连接，roads[i] = [x, y] 表示编号 x、y 的两个据点通过一条道路连接。现在勇者要将按照以下原则将这些据点逐一夺回：在开始的时候，勇者可以花费资源先夺回一些据点，初始夺回第 j 个据点所需消耗的资源数量为 cost[j]

LeetCode：LCP 30. 魔塔游戏（贪心 Java）

目录 LCP 30. 魔塔游戏题目描述：实现代码与解析：贪心原理思路： LCP 30. 魔塔游戏题目描述：小扣当前位于魔塔游戏第一层，共有 N 个房间，编号为 0 ~ N-1。每个房间的补血道具/怪物对于血量影响记于数组 nums，其中正数表示道具补血数值，即血量增加对应数值；负数表示怪物造成伤害值，即血量减少对应数值；0 表示房间对血量无影

【动态规划】【前缀和】【C++算法】LCP 57. 打地鼠

作者推荐视频算法专题本文涉及知识点动态规划汇总 C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频 LCP 57. 打地鼠勇者面前有一个大小为3*3 的打地鼠游戏机，地鼠将随机出现在各个位置，moles[i] = [t,x,y] 表示在第 t 秒会有地鼠出现在 (x,y) 位置上，并于第 t+1 秒该地鼠消失。勇者有一把可敲打地鼠的锤子，初始时刻（即第

LeetCode每日一题 | LCP 30. 魔塔游戏

文章目录题目描述问题分析程序代码题目描述原题链接小扣当前位于魔塔游戏第一层，共有 N 个房间，编号为 0 ~ N-1。每个房间的补血道具/怪物对于血量影响记于数组 nums，其中正数表示道具补血数值，即血量增加对应数值；负数表示怪物造成伤害值，即血量减少对应数值；0 表示房间对血量无影响。小扣初始血量为 1，且无上限。假定小扣原计划按房间编号升序访问所有房间

LCP 30. 魔塔游戏

LCP 30. 魔塔游戏难度: 中等题目: 小扣当前位于魔塔游戏第一层，共有 N 个房间，编号为 0 ~ N-1。每个房间的补血道具/怪物对于血量影响记于数组 nums，其中正数表示道具补血数值，即血量增加对应数值；负数表示怪物造成伤害值，即血量减少对应数值；0 表示房间对血量无影响。小扣初始血量为 1，且无上限。假定小扣原计划按房间编号升序访问所有房间补血/打怪，为保证血量始终

【教3妹学编程-算法题】LCP 30. 魔塔游戏

3妹：2哥，干嘛呢，一个人闷闷不乐的，在看什么呢。 2哥 : 这不快过年了嘛，想回家过年给我的小侄子买个礼物，结果他张口说想要个ps5. 那玩意我都没有，他还想要。我看看网上有什么好的礼物适合他的。 3妹：神马，他才6岁吧，就这么喜欢玩游戏啦？ 2哥 :是啊，这小子不让人省心，只要一碰到手机就是在玩游戏。 3妹：哎，想我们小的时候没有手机，童年一样过的很开心，现在科技进步了，反而孩子们的

LeetCode：LCP 24. 数字游戏（对顶堆求中位数 Java）

目录 LCP 24. 数字游戏题目描述：实现代码与解析：原理思路： LCP 24. 数字游戏题目描述：小扣在秋日市集入口处发现了一个数字游戏。主办方共有 N 个计数器，计数器编号为 0 ~ N-1。每个计数器上分别显示了一个数字，小扣按计数器编号升序将所显示的数字记于数组 nums。每个计数器上有两个按钮，分别可以实现将显示数字加一或减一。小扣每

差分转换+堆维护中位数，LeetCode LCP 24. 数字游戏

一、题目 1、题目描述小扣在秋日市集入口处发现了一个数字游戏。主办方共有 N 个计数器，计数器编号为 0 ~ N-1。每个计数器上分别显示了一个数字，小扣按计数器编号升序将所显示的数字记于数组 nums。每个计数器上有两个按钮，分别可以实现将显示数字加一或减一。小扣每一次操作可以选择一个计数器，按下加一或减一按钮。主办方请小扣回答出一个长度为 N 的数组，第 i 个元素(0 <= i <

LCP 13. 寻宝(Leetcode每日一题-2020.07.29)--抄答案。。。。

Problem 我们得到了一副藏宝图，藏宝图显示，在一个迷宫中存在着未被世人发现的宝藏。迷宫是一个二维矩阵，用一个字符串数组表示。它标识了唯一的入口（用 ‘S’ 表示），和唯一的宝藏地点（用 ‘T’ 表示）。但是，宝藏被一些隐蔽的机关保护了起来。在地图上有若干个机关点（用 ‘M’ 表示），只有所有机关均被触发，才可以拿到宝藏。要保持机关的触发，需要把一个重石放在上面。迷宫中有若干个石堆（

后缀数组(lcp)+st表-hdu4622

hdu4622 后缀数组基础题？昨天学了后缀排序其实最有用的是后缀数组求 l c p lcp lcp？用了一个 h e i g h t [ i ] = l c p ( s a [ i ] , s a [ i − 1 ] ) height[i]=lcp(sa[i],sa[i-1]) height[i]=lcp(sa[i],sa[i−1])，也就是排名为 i i i的和排名 i − 1 i-1

SAM+虚树--CF1073G Yet Another LCP Problem

传送门这题调的我两眼发黑。。。首先想 S A M SAM SAM建出来就是反串的后缀树，那么把原串反转一下，求后缀的 l c p lcp lcp就变成了求前缀的最长后缀，在 S A M SAM SAM上就是两个代表节点 l c a lca lca的 l e n len len，用这些关键点和他们的 l c a lca lca建出虚树，然后在虚树上跑，设 s i z a [ u ] , s

【LeetCode】LCP 2. 分式化简

有一个同学在学习分式。他需要将一个连分数化成最简分数，你能帮助他吗？连分数是形如上图的分式。在本题中，所有系数都是大于等于0的整数。输入的cont代表连分数的系数（cont[0]代表上图的a0，以此类推）。返回一个长度为2的数组[n, m]，使得连分数的值等于n / m，且n, m最大公约数为1。示例 1：输入：cont = [3, 2, 0, 2] 输出：[13,