考虑莫队，需要看看对于一个窗口，加窗口，和出窗口信息如何维护，下面只介绍如何维护信息： 对于绝对值不等式，对于数组 ，需要求加入后产生的贡献，需要拆绝对值式子，对于小于的，计算方式为，其中sum为比小的总和，为个数。对于大于的数同理。 维护和可以考虑用两个树状数组分别维护即可。  关于莫队的内容，可以自行搜索学习  #include <bits/stdc++.h> #define close ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define endl '\n' #define int long long us...

对于本题，需要发现平均值具有单调性，可以使用二分。如果给定了平均值。需要检查是否满足存在一个至少长度为的子数组，平均值大于给出的。实现为代码中的函数。 首先如果子数组没有长度限制求子数组最大值，可以求出一个数组的前缀和，对于任意子数组,区间和为。那么我们可以枚举,同时维护左边的对应的最小值，这样就可以求出子数组的最大值。 如果有了长度限制，只不过是让的长度大于而已。 这样我们可以减原数组都减去，然后判断是否有长度大于等于的子数组和大于0，如果有，说明这个平均值满足，否则不满足。 void solve(){ int n,f; cin >> n >> f; vector&l...

首先对于,可以通过质因数分解，求出所有的质因数次数。 对于质因数,次数为，由于次方，那么变为。 约数和可以这样表示： 对于单独的。需要求解这个等差数列的和。由于给出的模数为质数，根据等比数列求和公式。分子下面可以用逆元求得。 还有一种精妙的分治法也可以求得，题解区有就不多赘述，代码中也有体现。 //快速幂 int pow(int x,int n,int m){ int res = 1; while(n){ if(n & 1) res = res * x % m; x = x * x % m; n >>= 1; } return res; } //分治法求等比数列和 int ...

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

exgcd的做法，题解区有一个这么讲的了，这里按照我自己的理解解释一遍。 首先是要求我们找到的最大的，那么必然存在有解。 因为和互质，那么一定存在解。将2式左右同时减1得到：。然后代入1的值得到： 。 3式无解，必然需要满足。又由于,同时都是正整数，那么ab一定异号。可以分成如下两种情况讨论，并且都需要满足：  当,那么必然大于等于0， 为了无解，需要让 ,也就是 ,贪心的取最大就是 当,那么必然大于等于0， 为了无解，需要让 ,也就是 ,贪心的取最大就是   需要注意，两种情况的x'和y'不一样。都是满足等式的情况下的最小值，这里也很好理解，因为x'和y'是此消彼长的存在，一个大，一个就会小...

由于互质和唯一分解定理，和是没有相同的质因数。 那么可以得出： 本题的做法就是，计算出一个总和，然后对于每一个,需要重新计算自己本身，因为和并不互质，不满足等式1，然后加上即可。 #include <bits/stdc++.h> using namespace std; #define close ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define int long long #define endl '\n' #define MAXN 1000010 int n,k; int a[MAXN]; v...

裴蜀定理的推广，不会的可以搜索一下，只要保证就行了。 #include <bits/stdc++.h> using namespace std; #define close ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define int long long #define endl '\n' int a,b,c,m; void solve(){ cin >> a >> b >> c >> m; if(m % gcd(a,gcd(b,c)) == 0) co...

由题意可知，。也就可以可以通过的后面一项和的后面两项推出来。 那么可以得到如下矩阵形式：  这个形式就可以通过矩阵快速幂求出。 import sys from collections import Counter from heapq import heappop, heappush from math import inf, lcm, comb from typing import List # 输入加速 input = sys.stdin.readline """矩阵快速幂部分""" def matrix_multiply(A, B, mod=None): rows_A = len(A) ...

这道题看了其他大佬的题解才看出来，首先就是需要让每一个独立的区间内部没有倍数，这可以通过收缩左边界实现。 然后假设全要，这个时候需要的就是找出和没有倍数关系的有几个。 我们从开始枚举，我们要满足 ，也就是乘一个倍数过后，仍然小于d。那么可以反解出k。 然后我们又需要让,那么最大的一个数就是,个数就是. 然后类似数论分块那样到下一个倍数k的区间即可。  理解如果有误欢迎大佬指正  import sys read = sys.stdin.readline if __name__ == "__main__": a,b,c,d = map(int,read().split()) a = max(a,b...

根据间隔分组，也就是和是一组的，然后对于每一个组内元素，由于操作只能够加，不能减，所以所有元素一定会变为最大值。 设每一个组的最大值为,个数为,总和为,那么代价为。 那么求出所有组的总需求量，如果不够，那么直接返回。 然后将扣除后剩下的贪心的全部分给一组，那么就只要枚举组，记录哪一个最大即可。 import sys # 输入加速 input = sys.stdin.readline if __name__ == '__main__': t = int(input()) for _ in range(t): n, k, x = map(int, input().split()) a = list...

大思路是二分+dijkstra。 需要注意到车的重量越小，我们可以走的路越多，越能够到达终点，具有二段性，可以二分。 我们可以二分车可以达到的最大重量，假设为,然后对题目给出的图跑dijkstra,注意图的边有效的条件是他的可承受重量小于车的重量。  时间复杂度,cpp能跑过，python过不了。  #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e18; int main() { ios::sync_with_stdio(false); cin.tie(0); ...

本题好像只要用支持区间加，区间重置的线段树也能过，但是不能够在过程中取模？ 大思路就是，我们给原数组排序，因为每次加减都是在所有数的上面操作，然后加法不会改变顺序，而减法可能会导致从某个位置开始往左全是0，具有二段性，我们可以二分找到这个位置，然后将左边的全部置为0，右边的正常减就行了。 由于涉及到了比大小，所以不能在中间取模，所以最后的求和数会很大，直接用了__int128。 #include <bits/stdc++.h> using namespace std; typedef __int128 ll; const int MOD = 1e9 + 7; class LazyS...

实际上就是求一个这个函数所能够达到的最小值，这个是一个关于的函数，我们可以对他进行求导，让，可以得出如下式子： 。 import sys from math import sqrt # 输入加速 input = sys.stdin.readline if __name__ == '__main__': v0,x,y = map(int,input().split()) t = max((sqrt(x * y) - v0) / x,0) res = t + y / (v0 + t * x) print(f"{res:.6f}")

提供一种序列分治的思路。还算比较general。 首先我们需要知道，0的个数取决于和的个数的最小值。启示我们预处理出每一个数字中5的个数和2的个数。 根据的个数来进行排序，然后我们定义如下分治函数,会将区间分割为.那么答案就拆分为计算左右区间之间跨区间的个数，然后分治计算。 关键是如何跨区间，由于我们已经对的个数来排序了，那么对于右区间，我们可以从往右遍历，然后对于左区间，从开始从右往左遍历。 由于有序性质，我们可以枚举右区间，这个时候如果的2个数与的2个数大于等于x，那么可以减1，并且这是一个循环的过程，尝试找到更多的符合条件的元素，而且指针不会回退。 这样我们只需要知道之间5的个数符合的元...