Mag1c0nch

分类

/ 注册

全部文章（共48篇）

题解 | #平均数为k的最长连续子数组#

当长为 len 的平均数等于 k 时，代表区间的和为 len*k ，特别的，当 k 为 0 时，区间的和也为0，代表 sum[r] == sum[l-1] ，所以我们可以先简化题意，将每一项都减去 k ，来求区间平均数为 0 的最长区间，那么对于每个区间前缀和 sum ，一定是和之前值等于 sum ...

2024-11-21

1 56

题解 | #小红的子序列逆序对#

对于一个逆序对 i j 来说，其在子序列中出现的次数是固定的，是 2^(n-2)，因为对于 n 个数而言，i 和 j 必须出现在逆序对中，而其他数都可以出现或者不出现，所以每个逆序对都会出现 2^(n-2) 次，答案就是逆序对数量乘 2^(n-2) 而求逆序对数量很简单了，实现方法很多，这里给一个树...

2024-11-21

3 51

题解 | #小球投盒#

每次 1 操作之后只有两种情况完成目标，同盒子 x 有过 2 操作，或者所有盒子都有过 1 操作每次 2 操作之后只有两种情况完成目标，同盒子 x 有过 1 操作，或者有其他盒子有过 2 操作可以使用map维护已经操作过的 1 和 2 操作，注意检查某操作是否存在（某个键是否存在）需要使用 coun...

2024-11-21

6 51

题解 | #小红结账#

按照题意模拟即可，需要注意的是 a/b 向上取整可以直接写为 (a+b-1)/b #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1...

2024-11-21

1 27

题解 | #小美的蛋糕切割#

维护好二维前缀和sum后，所有可能的 sum[i][m] 和 sum[n][i] 就是小美拥有的，而 sum[n][m] 减去小美拥有的就是小团拥有的，遍历所有可能性，维护好最小的二者的差的绝对值即可 #include <bits/stdc++.h> using namespace st...

2024-11-21

1 35

题解 | #小美走公路#

维护好前缀和b，那么 l 到 r 的要么正着走花费 b[r - 1] - b[l - 1] ，要么反着走花费 b[n] - b[r - 1] + b[l - 1]记得保证 l<r #include <bits/stdc++.h> using namespace std; #def...

2024-11-21

1 24

题解 | #【模板】差分#

使用差分数组维护区间修改即可 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 5; int __t = 1, n, m, l, r, k; int a[N], ...

2024-11-21

1 28

题解 | #【模板】静态矩阵和（二维前缀和）#

使用二维前缀和即可，需要注意不定长的二维数组可以使用vector #include <bits/stdc++.h> using namespace std; #define int long long const int N = 1005; int __t = 1, n, m, q, x...

2024-11-21

1 19

题解 | #【模板】线段树1#

板子题 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 5; int __t = 1, n, q; int a[N], bit[N]; void update(...

2024-11-21

3 30

题解 | #【模板】静态区间和（前缀和）#

使用前缀和维护 1 到 i 的元素和，存在 b 数组那么查询 l 到 r 的元素和就是 b[r]-b[l-1] #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e6 + ...

2024-11-21

1 38