摘要：
原题链接：https://www.luogu.com.cn/problem/P1966 题意解读：计算两个序列∑(ai−bi)^2的最小值，对10^8-3取模。 解题思路： 1、贪心思路 要使得两个序列对应位置元素之差的平方和最小，必须满足两个序列相对排序是一致的，什么意思？ 设a序列有两个元素 阅读全文
posted @ 2024-09-12 09:47
hackerchef
阅读(78)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/P1908 题意解读：求序列逆序对数。 解题思路： 1、暴力法 对于每一个数，寻找后面有多少数比其小，或者采用冒泡排序，交换的次数即逆序对的个数，复杂度为O(n^2) 2、归并排序法 在归并排序过程中，会进行有序序列的合并， 阅读全文
posted @ 2024-09-11 14:07
hackerchef
阅读(147)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/P1177 题意解读：归并排序模版题。 解题思路： 第一步：确定分界点。mid = ( l + r) / 2 第二步：排序。对左右两边递归排序 第三步：归并。合并左右两边排序好的内容 关键在第三步：通过双指针对两个有序数组进 阅读全文
posted @ 2024-09-11 10:12
hackerchef
阅读(128)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/P1714 题意解读：求长度不超过m的最大子段和 解题思路： 1、暴力法 设a[N]表示原数组，s[N]是a[N]的前缀和，对于每一个元素s[i]，计算其与前m个元素之差，取差值最大值，用代码表示： for(int i = 阅读全文
posted @ 2024-09-10 18:20
hackerchef
阅读(107)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/P2880 题意解读：在若干个不定长区间里，求区间最大值与最小值之差 解题思路： 对于区间求最值，通常有几种方式： 1、暴力法，通过枚举所有的区间来计算区间最值 2、单调队列，针对区间长度固定的情况 3、ST表，针对区间长度 阅读全文
posted @ 2024-09-10 15:22
hackerchef
阅读(149)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/P1886 题意解读：单调队列模版题。 解题思路： 采用双端队列维护单调的序列，单调队列三部曲： 1、去头，当窗口内元素个数超过k，队头出队 2、去尾，当要加入的元素会破坏单调性，队尾出队，这是因为如果当前元素比队尾元素更优 阅读全文
posted @ 2024-09-09 16:22
hackerchef
阅读(161)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/P3467 题意解读：用长方形的海报覆盖建筑的侧面，最少需要的海报数 如上图，左边最少需要3张，右边最少需要4张 解题思路： 可以看出，需要海报数与建筑宽度无关，只与高度有关。 当建筑高度与之前不同时，肯定需要增加一张海报； 阅读全文
posted @ 2024-09-06 10:48
hackerchef
阅读(103)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/P1578 题意解读：在有障碍点的矩形内找到一个最大矩形，内部不能包含障碍点，边缘可以包含障碍点。 解题思路： 求最大矩形的两种算法：极大矩形法、悬线法，背景知识阅读：浅谈用极大化思想解决最大子矩阵问题 关于悬线法，前面在玉 阅读全文
posted @ 2024-09-06 10:27
hackerchef
阅读(109)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/P3143 题意解读：找到两个不相交的最长连续序列，使得序列最大值和最小值差不超过k，求两个最长的序列长度和。 解题思路： 先将所有数从小到大排序，记为a[] 要找到两个不相交的最长连续序列，可以采用下面技巧： 设b[i]表 阅读全文
posted @ 2024-09-04 11:10
hackerchef
阅读(101)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/P4653 题意解读：选中的灯泡中，某一类较少的总权值减去灯泡数量所得到的收益最大值。 解题思路： 注意，此题关键是：要使得较少的收益最大化 1、要最大化，意味着每次应该选择尽可能大权值的灯泡 2、要使A、B类中较少的收益最 阅读全文
posted @ 2024-09-04 10:10
hackerchef
阅读(102)
评论(0)
推荐(0)
浙公网安备 33010602011771号