微澜尛雨

题解

/ 注册

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

题解 | #逆序数#

题目考点：归并排序、二维偏序都可以写，也都是模板题题目大意：给定一个数组，对于数组中的每一个数ai,如果前面有一个数aj大于ai,那么(aj,ai)组成一组逆序对,数组中逆序数的个数为数组的逆序数，求逆序数的数量。思考：既然有不少同学写了归并排序，我就写一写二维偏序吧！思路很简单，我们把...

树状数组二分前缀和

2022-03-16

2 615

题解 | #糖糖别胡说，我真的不是签到题目# 来自专栏

题目考点：前缀和、枚举题目大意：两组糖糖站一排，顺序任意。遍历这一排时，当前糖糖会消除前面与他不同组而且数值比自己小的糖糖，遍历一个糖糖用时1秒。另外有m次施法，第x秒的施法可使前x个糖糖数值+1，求最后没有被消除的糖糖的个数。核心思想：设j > i, 若a[ j ] + 收益 > ...

枚举前缀和

2021-11-25

2 614

题解 | #毒瘤xor# 来自专栏

题目考点：前缀和、位运算题目大意：找到一个数X，使得X和数列区间内所有数字异或后，得到的值最大。题目分析：暴力解法O(d * 2e10)，其中d为区间长度、2e10为int正整数范围，用派蒙的脑子想想就知道不可取吧？换个想法来看，统计一下区间内的数字的第i位0的个数和1的个数：若第i位1的个数...

前缀和位运算

2021-11-25

1 523

题解 | #[NOIP2005]校门外的树# 来自专栏

考点：差分大意：在一个长区间内取走n和小区间，问取完后剩余的点数代码： #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 10...

差分前缀和

2021-07-09

0 401

题解 | #Let's Play Curling# 来自专栏

题目考点：离散化（其实怎么写都行，以个人目前能力感觉离散化+前缀和比较好上手）题目大意：一条线上红蓝两种石头随机排列，易知存在若干点使得这些点前后均为红色石头，且绝对不含蓝色石头，找到这些点中的前后红色石头数量最多的那个点，输出最大数量题目分析：如图，我们可以确定a[4]和a[5]之间的点，前后...

离散化前缀和

2021-05-13

8 828