偶尔刷刷题

题解

/ 注册

全部文章 / 题解（共7篇）

牛客NOIP暑期七天营-普及组6-D-Bunny的聚会

题目大意：数轴上有n个点，在总代价不超过m的情况下，至多可以将多少个点移到一起？（代价：每个点移动的距离）数据范围500万，递增输入，不需要排序，显然需要用O(n)做法才能满分，而且读入还可能被卡。能走到一起的，必然是连续的若干个点：如果一个区间中有个点没有移动过去，那么终点要么在他左边，要么在...

区间平移分配律单调性区间和单调递增数学前缀和

2019-08-25

2 1019

牛客NOIP暑期七天营-普及组5-A手术等级

题目大意：一个从1开始编号的数组的不完美度为，现在可以将数组分成两个从1开始编号的数组，请问分成的两个数组的不完美度之和最小是多少？将一个数组分成两半，左半边的不完美度的没有任何变化的。右半部分，假设是从i开始，区间是[i, n]：第i个元素由a[i]i变成了a[i]*1，第i+1个元素由a[i...

模拟查找枚举数学前缀和

2019-08-24

0 924

牛客OI周赛11-普及组-D凸包的交

题目大意：根据指定规则生成序列a，在所有长度不小于L的区间中，平均值最大是多少？ 1、递推计算序列：根据题目公式计算即可。 2、预处理前缀和：区间平均值，用到区间和，区间和可以通过前缀和O(1)算出来。 3、平均值即斜率：区间i+1到j的平均值是(s[j]-s[i]) / (j-i)，可以使用斜率优...

区间斜率优化数形结合斜率递推思维前缀和

2019-08-23

0 918

牛客NOIP暑期七天营-普及组4-D火龙果画

题目大意：输入n个直角三角形，被第i个三角形覆盖，美观度增加，请问所有被覆盖的点中，最大美观度是多少？暴力70分，但不开long long就只有20了。数据很水，开了long long，边加美味度边统计最大值都有70（23行放到16行之后）！暴力做法，不需要多想：对于每个三角形，包含在里面的点全...

差分标记差分模拟时间复杂度思维前缀和几何

2019-08-22

2 969

牛客NOIP暑期七天营-普及组3-D子段和

题目大意：对于一个永不超过250个数的序列，可以删除末尾数，可以在末尾增加一个数，中途询问是否有一个区间的和等于x，有就输出Yes，否则输出No。判断是否有连续一段的和（区间和）等于m，可以用前缀和+哈希表判断：对于每一个区间，必有起点l和终点r，元素之和为s[r] - s[l-1]，其中s记录...

区间平移二分单调性单调单调递增前缀和 map 哈希

2019-08-21

0 833

牛客NOIP暑期七天营-普及组3-C区间中最多的数

题目大意：给定n个数，q次询问，每次问区间[l, r]直接出现最多的数字是什么？并列的话输出较大数。从数据范围看，O(qn)超时，O(qa)不超时。空间限制128M，开一个100*200000的数组刚好不超时。预处理每种数字出现的前缀和，对于每个循环，分别O(1)求出每种数字的数量，记录最优值...

模拟时间复杂度空间复杂度前缀和

2019-08-21

0 822

牛客NOIP暑期七天营-普及组1-D矩阵

题目大意：给定一个n*m的矩阵，输出最大子矩阵（元素之和最大值）。对于每一个子矩阵，如果左上角是(x, y)，右下角是(p, q)，那么他每一行的元素之和是：用乘法分配率合并后即：这样，问题就转化为求数组a中的最大子段和以及数组b中的最大子段和问题了。当然，还需要注意细节： 1、对...

分配律数学分类讨论思维前缀和

2019-08-19

0 764