我们发现如果a和b都是正数，相同的时候无解，不同的时候只需要给小的数加上大的数即可，然后特判一下和0有关的情况 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n, a, b; void solve() { cin >> a >> b; if (a == 0 && b == 0) { cout << "1 1\n"; ...

从1到m的循环编号我们很快就能联想到取余，但是取余的下标是从0开始的，例如对m取余，代表着从0到m-1循环编号，我们发现可以提前给x减去1然后取余结束后再加一即可 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n, m, x; void solve() { cin >> m >> x; cout << (x - 1) % m + 1 << "\n&q...

快速幂模板题 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n, a, b, p; int kpow(int a, int b, int p) { int ans = 1; while (b) { if (b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } ...

因子题我们首先关注数据范围如果 t 和 x 都是 1e5 左右的大小，我们可以选择暴力预处理出每个数的因子个数储存下来，然后实现O1的查询本题 t=10 而 x 是 1e9 的范围，显然我们只需要求出这至多十个数的因子个数即可，对于一个 1e9 范围内的数，遍历 1e9 范围内的数是不是其因子是行不通的，时间复杂度是 O(n) ，但是我们小学二年级的时候学过，一个数 n 最多只会有一个大于根号 n 的“大”因子，所以我们只需要遍历根号范围内的数，然后顺便将其除掉，那么最后如果剩下了一个1，代表这个数 n 没有大于根号 n 的因子了，而如果是其他数，那么一定是一个“大”质数，我们就可以只用根号 ...

lcm尽可能大，代表gcd尽可能小，所以一定是a和b互质时的 a*b 是最大的lcm，同时因为是二者的乘积，所以二者要尽可能的靠近 n/2 才行，所以从中间情况开始检查这一组a和b是否合法即可 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n; void solve() { cin >> n; int a = n / 2, b = n - a; while (__gcd(a, b) !=...

枚举所有 x ，可能的 y 最多只有三个，x 也很少因为是阶乘 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n, y, fac = 2, ans, ansx = 1, ansy = 1; void ck(int x, int y) { if (y == 2 || y == 0) return; if (abs((fac - 1) * y - n) < ans) { a...

每个点到达圆心的距离固定，最终的半径也一定是某点到达圆心的距离，所以维护好每个点到圆心的距离和权值，按距离排序然后顺次选取即可，记得开ll #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n, m, x, y, v; void solve() { cin >> n >> m; vector<pair<int, int>> ve; for (int i =...

二分答案+滑动窗口我们来看看为什么可以想出这个思路首先我们假设所有的人都是数轴上的点，他们的坐标就是 a ，权值就是 b 对于一个隔阂值 m ，代表在数轴上选择一段长度为 m 的区间，区间里点的权值和就是贡献那么这个区间就是滑动窗口，他的右端点一定在一个点上，因为从贪心的角度来看，如果右端点不在一个点上，那么我们可以把右端点向左移动，这样就可能会覆盖其他点，权值和就可能会增加我们可以遍历维护出这个窗口，每次向右滑动到一个新的点，这时窗口中已经存在的点可能会离开窗口，但是一定是最左边的点离开，所以我们可以用一个双端队列来维护，同时记录最大的权值和，如果大于等于 k ，代表这个 m 是合法的然后我...

从第二个元素开始遍历数组，如果当前元素和前一个元素之差的绝对值不超过1，则当前稳定子数组的长度加1，否则，重置当前稳定子数组的长度为1，然后维护一个最大的答案即可 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n, a[N]; void solve() { cin >> n; int sum = 1, ans = 1; for (int i = 1; i <= n; i++) ...

观察函数，发现函数 F(x) 在区间 [l, r] 上是一个单峰函数，所以可以三分，注意 eps 设置到比给定标准小一点就行 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 5e5 + 5; const double EPS = 1e-7; int __t = 1, n; double l, r; struct Fx { int k, a, b; }; vector<Fx> fxs; double f(Fx fx, double x) { ...

模板，按照题意模拟即可，记得讨论清楚边界 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n, q, op, l, r, x, k; void solve() { vector<int> a; cin >> n >> q; for (int i = 0; i < n; i++) cin >> x, a.push_back(x); ...

当长为 len 的平均数等于 k 时，代表区间的和为 len*k ，特别的，当 k 为 0 时，区间的和也为0，代表 sum[r] == sum[l-1] ，所以我们可以先简化题意，将每一项都减去 k ，来求区间平均数为 0 的最长区间，那么对于每个区间前缀和 sum ，一定是和之前值等于 sum ，且下标最小的一项构成最长区间，所以我们可以使用 map 维护每个前缀和值最早出现的下标，如果一个前缀和之前出现过，就用他们两个的下标来更新答案，最后维护最大的答案即可 #include <bits/stdc++.h> using namespace std; #define int l...

对于一个逆序对 i j 来说，其在子序列中出现的次数是固定的，是 2^(n-2)，因为对于 n 个数而言，i 和 j 必须出现在逆序对中，而其他数都可以出现或者不出现，所以每个逆序对都会出现 2^(n-2) 次，答案就是逆序对数量乘 2^(n-2) 而求逆序对数量很简单了，实现方法很多，这里给一个树状数组实现的方法 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 5; const int mod = 1e9 + 7; int __t = 1, n, a[N...

每次 1 操作之后只有两种情况完成目标，同盒子 x 有过 2 操作，或者所有盒子都有过 1 操作每次 2 操作之后只有两种情况完成目标，同盒子 x 有过 1 操作，或者有其他盒子有过 2 操作可以使用map维护已经操作过的 1 和 2 操作，注意检查某操作是否存在（某个键是否存在）需要使用 count ，如果直接使用 mp[x]==0 来判断会创建这个元素 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n, m, k, x...