以诚丶

分类

题解(31)

/ 注册

全部文章（共29篇）

题解 | #Dragon Ball Super#

根据题目给出的关系，可以将所有的人利用并查集分组。分组后，可以使用莫队算法，窗口维护一个数组，代表了种类出现的次数,还需要维护，代表了个数。维护方式很简单，不多做赘述，见代码即可。 #include <bits/stdc++.h> #define close ios::sync_wi...

C++ 莫队

2025-10-20

1 18

题解 | #区间与绝对值#

考虑莫队，需要看看对于一个窗口，加窗口，和出窗口信息如何维护，下面只介绍如何维护信息：对于绝对值不等式，对于数组，需要求加入后产生的贡献，需要拆绝对值式子，对于小于的，计算方式为，其中sum为比小的总和，为个数。对于大于的数同理。维护和可以考虑用两个树状数组分别维护即可。关于莫队的内容，可...

C++ 莫队

2025-10-19

0 15

题解 | #Best Cow Fences#

对于本题，需要发现平均值具有单调性，可以使用二分。如果给定了平均值。需要检查是否满足存在一个至少长度为的子数组，平均值大于给出的。实现为代码中的函数。首先如果子数组没有长度限制求子数组最大值，可以求出一个数组的前缀和，对于任意子数组,区间和为。那么我们可以枚举,同时维护左边的对应的最小值，这样就可...

C++ 二分查找前缀和

2025-09-26

1 24

题解 | #Sumdiv#

首先对于,可以通过质因数分解，求出所有的质因数次数。对于质因数,次数为，由于次方，那么变为。约数和可以这样表示：对于单独的。需要求解这个等差数列的和。由于给出的模数为质数，根据等比数列求和公式。分子下面可以用逆元求得。还有一种精妙的分治法也可以求得，题解区有就不多赘述，代码中也有体现。 //...

C++ 质因数数论

2025-09-25

1 20

题解 | #算法配置#

区间重置线段树的简单应用，这里给出模板，请自行搜索学习： """所有下标都从0开始""" class LazySegmentTree: def __init__(self, n: int): self.n = n self.sum = [0] * (self...

pypy3 Python3 线段树差分数组

2025-09-10

1 24

题解 | #Sum Gcd#

由于互质和唯一分解定理，和是没有相同的质因数。那么可以得出：本题的做法就是，计算出一个总和，然后对于每一个,需要重新计算自己本身，因为和并不互质，不满足等式1，然后加上即可。 #include <bits/stdc++.h> using namespace std; #define ...

C++ 数学

2025-07-30

1 38

题解 | #生成函数#

裴蜀定理的推广，不会的可以搜索一下，只要保证就行了。 #include <bits/stdc++.h> using namespace std; #define close ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL...

C++ gcd

2025-07-30

1 36

题解 | #Fibonacci 前 n 项和#

由题意可知，。也就可以可以通过的后面一项和的后面两项推出来。那么可以得到如下矩阵形式：这个形式就可以通过矩阵快速幂求出。 import sys from collections import Counter from heapq import heappop, heappush from ma...

Python3 快速幂动态规划矩阵

2025-07-28

1 37

题解 | #倍集#

这道题看了其他大佬的题解才看出来，首先就是需要让每一个独立的区间内部没有倍数，这可以通过收缩左边界实现。然后假设全要，这个时候需要的就是找出和没有倍数关系的有几个。我们从开始枚举，我们要满足，也就是乘一个倍数过后，仍然小于d。那么可以反解出k。然后我们又需要让,那么最大的一个数就是,个数就是...

Python3 数学

2025-07-24

1 50

题解 | #游游的k-好数组#

根据间隔分组，也就是和是一组的，然后对于每一个组内元素，由于操作只能够加，不能减，所以所有元素一定会变为最大值。设每一个组的最大值为,个数为,总和为,那么代价为。那么求出所有组的总需求量，如果不够，那么直接返回。然后将扣除后剩下的贪心的全部分给一组，那么就只要枚举组，记录哪一个最大即可。 im...

Python3

2025-07-24

1 51