7.1 位运算
题目:求 \(a\times b\bmod p\)。\(1\le a,b,p\le 10^{18}\)。
思路:
方法一:快速乘。
类似 4.4 中快速幂的思想。
设 \(b\) 在二进制表示下有 \(k\) 位,其中第 \(i\;(0\le i<k)\) 位的数是 \(c_i\;(c_i\in\{0,1\})\),那么:
\[b=\sum_{i=0}^{k-1}c_{i}2^{i}\tag{7.1} \]于是有:
\[a\times b=a\times {\sum_{i=0}^{k-1}c_{i}2^{i}}=\sum_{i=0}^{k-1}a{c_i2^i}\tag{7.2} \]又因为 \(a\times 2^i=(a\times 2^{i-1})\times 2\),所以我们可以通过递推来求出每个乘积项。时间复杂度 \(O(n\log b)\)。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long
int a, b, p;
int mul(int a, int b, int p) {
int ans = 0;
while (b) {
if (b & 1) ans = (ans + a) % p;
a = a * 2 % p;
b >>= 1;
}
return ans;
}
signed main() {
scanf("%lld%lld%lld", &a, &b, &p);
printf("%lld\n", mul(a, b, p));
return 0;
}
方法二:光速乘。
利用 \(a\times b\bmod p=a\times b-\lfloor a\times b/p \rfloor\times p\),令 \(\lfloor a\times b/p \rfloor=c\),那我们如何计算 \(c\) 呢?如果我们用 long double
直接计算 \(a\times b/p\),其在十进制下的有效数字为 \(18\sim 19\) 位,当 \(a,b<p\) 时,\(c\) 也一定小于 \(p\),即 \(c\) 也在 \(18\) 位内。所以我们可以用 long double
计算出 \(a\times b/p\) 的精确值,再用 unsigned long long
将其强制转换为 \(c\)。
由于 \(a\times b-c\times p= a\times b\bmod p< 10^{18}<2^{64}\),则 \(a\times b-c\times p=(a\times b-c\times p)\bmod 2^{64}\),用 unsigned long long
计算 \(x=a\times b,y=c\times p\),最后用 long long
计算 \((x\bmod p-y\bmod p)\bmod p\) 即可。时间复杂度 \(O(1)\)。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll a, b, p;
ll mul(ll a, ll b, ll p) {
a %= p, b %= p;
ull c = (long double)a * b / p;
ull x = a * b, y = c * p;
ll ans = ((ll)x % p - (ll)y % p + p) % p;
return ans;
}
int main() {
scanf("%lld%lld%lld", &a, &b, &p);
printf("%lld\n", mul(a, b, p));
return 0;
}
7.2 递归与递推
题目:有 \(T\) 组数据,每组数据包含一个 \(5\times 5\) 的矩阵 \(a\),在每个位置 \((i,j)\;(1\le i,j\le 5)\) 上都有一个灯,若 \(a_{i,j}=0\) 表示灯是关着的,\(a_{i,j}=1\) 表示灯是开着的。每一次操作可以选取一盏灯,并改变其上下左右的灯(如果存在)和其本身的状态(即关着的变成开着的,开着的变成关着的),问能否通过 \(\le 6\) 次操作使所有的灯都打开。能则输出最小步数,不能则输出 -1
。\(1\le t\le 500\)。
思路:
显然,已操作过的灯(除非它是关着的)不需要再操作。所以我们可以先用二进制枚举第一行的操作情况,再从第一行枚举到第四行,若位于 \((i,j)\) 位置上的灯没有开,则将 \((i+1,j)\) 位置上的灯操作一次即可(防止影响到左边的灯)。最后判断第五行上的灯是否都打开了。时间复杂度 \(O(2^5\cdot 5^2 T)\)。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int dx[] = {-1, 0, 1, 0, 0}, dy[] = {0, -1, 0, 1, 0};
int t;
bool a[7][7], tmp[7][7];
void change(int x, int y) {
for (int i = 0; i < 5; ++i) {
int x_ = x+dx[i], y_ = y+dy[i];
if (x_ > 0 && x_ < 6 && y_ > 0 && y_ < 6)
a[x_][y_] ^= 1;
}
}
int main() {
scanf("%d", &t);
while (t -- ) {
for (int i = 1; i <= 5; ++i) {
for (int j = 1; j <= 5; ++j)
scanf("%1d", &a[i][j]);
}
int ans = 7, step = 0;
memcpy(tmp, a, sizeof a);
for (int s = 0; s < 32; ++s) {
step = 0; memcpy(a, tmp, sizeof tmp); // 注意要将原数组复制一遍,防止覆盖
for (int i = 1; i <= 5; ++i) {
if (s >> (i-1) & 1)
step ++, change(1, i);
}
for (int i = 1; i <= 4; ++i) {
for (int j = 1; j <= 5; ++j) {
if (!a[i][j])
step ++, change(i+1, j);
}
}
for (int i = 1; i <= 5; ++i) {
if (!a[5][i]) {
step = 7;
break;
}
}
ans = min(step, ans);
}
printf("%d\n", (ans > 6) ? -1 : ans);
}
return 0;
}
题目:给定两个数 \(a,b\),令 \(s\) 为 \(a^b\) 的所有约数之和,求 \(s\bmod 9901\)。\(0\le a,b\le 5\times 10^7\) 且 \(a,b\) 不同时为 \(0\)。
思路:
假设在算数基本定理中,\(a=\prod_{i=1}^m p_i^{r_i}\)(其中 \(p_i\) 为质数,\(r_i\in\mathbb{N}_+\)),则 \(a^b=\prod_{i=1}^m p_i^{r_ib}\)。那么有:
\[s=\prod_{i=1}^m\sum_{j=0}^{r_ib}p_i^j\tag{7.3} \]考虑如何快速计算后面的和式。不妨设 \(sum(p,k)=\sum_{i=0}^{k-1}p^i\),运用分治的思想,当 \(k\) 为偶数时,我们有:
\[\begin{aligned} sum(p,k)&=(1+p+p^2+\cdots+p^{k/2-1})+p^{k/2}(1+p+p^2+\cdots+p^{k/2-1})\\ &=sum(p,k/2)+p^{k/2}sum(p,k/2-1)\\ &=sum(p,k/2)(p^{k/2}+1) \end{aligned}\tag{7.4} \]当 \(k\) 为奇数时,显然有 \(sum(p,k)=sum(p,k-1)+p^{k-1}\),再代入 \((7.4)\) 计算即可。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int P = 9901;
int a, b, ans = 1;
unordered_map<int, int> primes;
int pow(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = (ll)ans * a % P;
a = (ll)a * a % P;
b >>= 1;
}
return ans;
}
int sum(int p, int k) {
if (k == 1) return 1;
if (k % 2) return (sum(p, k-1) + pow(p, k-1)) % P;
return sum(p, k/2)*(pow(p, k/2)+1) % P;
}
int main() {
scanf("%d%d", &a, &b);
if (!a) puts("0"), exit(0);
for (int i = 2; i <= a/i; ++i) {
while (a % i == 0) {
a /= i;
primes[i] ++;
}
}
if (a > 1) primes[a] ++;
for (auto p : primes) ans = ans * sum(p.first, p.second*b+1) % P;
printf("%d\n", ans);
return 0;
}
例题:AcWing 98. 分形之城
题目:为了更好地规划城市建设,一座城市的工作人员想出了如下图所示的一种方法:
现在,他们想求出编号为 \(A,B\) 的房屋在 \(N\) 级城市的距离,每个小方格的边长都为 \(10\text{m}\),结果四舍五入到整数。多测,有 \(n\) 组数据。
\(1\le N\le 31,1\le A,B\le 2^{2N},1\le n\le 10\)。
思路:
定义 \(pos(A,N)\) 表示编号为 \(A\) 的房屋在 \(N\) 级城市中的位置。由图 \(\texttt{7-1}\) 可知,等级为 \(N\) 的城市是由 \(4\) 个等级为 \(N-1\) 的城市组成,其中左上角的城市顺时针旋转了 \(90^{\circ}\) 再水平翻转,右上角的城市没有旋转,右下角的城市没有旋转,左下角的城市逆时针旋转了 \(90^{\circ}\) 再水平翻转。
在计算 \(pos(A,N)\) 时,由于 \(N-1\) 级城市有 \(2^{2N-2}\) 座房屋,所以我们先递归求解出 \(pos((A-1)\bmod 2^{2N-2}+1,N-1)\),递归出口为 \(pos(1,0)=(1,1)\)。假设求得的解为 \((x,y)\),再根据 \(A/2^{2N-2}\) 的大小即可判断出 \(A\) 属于哪一个部分:
-
若 \(A\) 在左上角:则 \(A\) 顺时针旋转 \(90^{\circ}\) 后为 \((y,2^{N-1}-x+1)\),再水平翻转后为 \((y,x)\);
-
若 \(A\) 在右上角:则 \(A\) 的 \(y\) 坐标增加了 \(2^{N-1}\),坐标变为 \((x,y+2^{N-1})\);
-
若 \(A\) 在右下角:则 \(A\) 的 \(x\) 坐标增加了 \(2^{N-1}\),\(y\) 坐标也增加了 \(2^{N-1}\),坐标变为 \((x+2^{N-1},y+2^{N-1})\);
-
若 \(A\) 在左下角:则 \(A\) 逆时针旋转 \(90^{\circ}\) 后为 \((2^{N-1}-y+1,x)\),再水平翻转后为 \((2^{N-1}-y+1,2^{N-1}-x+1)\),又因为 \(A\) 的 \(x\) 坐标增加了 \(2^{N-1}\),所以坐标变为 \((2^N-y+1,2^{N-1}-x+1)\)。
最后用两点之间距离公式计算出 \(pos(A,N)\) 和 \(pos(B,N)\) 之间的距离即可。
*代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define int long long
typedef pair<int, int> pii;
int t, n, a, b;
pii pos(int a, int n) {
if (!n) return make_pair(1, 1);
int t = pow(2, n*2-2);
pii a_ = pos((a-1)%t+1, n-1);
int part = (a-1)/t, x = a_.first, y = a_.second;
if (part == 0) return make_pair(y, x);
else if (part == 1) return make_pair(x, y+(int)pow(2, n-1));
else if (part == 2) return make_pair(x+(int)pow(2, n-1), y+(int)pow(2, n-1));
else return make_pair((int)pow(2, n)-y+1, (int)pow(2, n-1)-x+1);
}
int dist(pii a, pii b) {
return round(sqrt(pow(a.first*10-b.first*10, 2)+pow(a.second*10-b.second*10, 2)));
}
signed main() {
scanf("%lld", &t);
while (t -- ) {
scanf("%lld%lld%lld", &n, &a, &b);
printf("%lld\n", dist(pos(a, n), pos(b, n)));
}
return 0;
}
7.3 前缀和与差分
题目:地图上有 \(n\) 个目标,第 \(i\) 个目标位于 \((x_i,y_i)\),价值为 \(w_i\)(多个目标可能在同一位置)。现有一束激光炸弹,覆盖面积为一个 \(m\times m\) 的正方形,但正方形边上的点不会被轰炸,且正方形的边必须与 \(x\) 轴或 \(y\) 轴平行。求能轰炸的最大价值。\(0\le m\le 10^9,0<n\le 10000,0\le x_i,y_i\le 5000,0\le w_i\le 1000\)。
思路:
由于 \(0\le x_i,y_i\le 5000\),我们可以用二维前缀和完成此题。令 \(a_{i,j}\) 表示位置 \((i,j)\) 上的目标的价值之和,\(s_{i,j}=s_{i,j-1}+s_{i-1,j}-s_{i-1,j-1}+a_{i,j}\)。注意到在二维前缀和中,我们将 \((x_i,y_i)\) 作为一个格子来处理,而题目中的 \((x_i,y_i)\) 为格点,且正方形边上的点不会被轰炸。我们可以认为正方形左上角的点为 \((x_i-0.5,y_i-0.5)\),正方形右下角的点为 \((x_i+0.5, y_i+0.5)\),这个问题与原问题是等价的。
最后我们枚举正方形的右下角 \((i,j)\) 即可。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5005;
int n, m, ans;
int s[N][N];
int main() {
scanf("%d%d", &n, &m);
m = min(m, 5001);
for (int i = 1; i <= n; ++i) {
int x, y, w; scanf("%d%d%d", &x, &y, &w);
x ++, y ++;
s[x][y] += w;
}
for (int i = 1; i <= 5001; ++i) {
for (int j = 1; j <= 5001; ++j)
s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
}
for (int i = m; i <= 5001; ++i) {
for (int j = m; j <= 5001; ++j)
ans = max(ans, s[i][j]-s[i-m][j]-s[i][j-m]+s[i-m][j-m]);
}
printf("%d\n", ans);
return 0;
}
题目:有一个长度为 \(n\) 的序列 \(a\),每次可以选择一个区间 \([l,r]\), \(a_l\sim a_r\) 都加 \(1\) 或减 \(1\)。求至少需要几次操作才能使数列中的数全部相同,并计算在操作次数最少的情况下,最终得到的序列可能有多少种。\(1\le n\le 10^5,0\le a_i<2^{31}\)。
思路:
我们求出 \(a\) 的差分序列 \(b\),令 \(b_{n+1}=0\)。显然对于题目的一次操作,相当于 \(b_l\) 增加(或减少)\(1\),\(b_{r+1}\) 减少(或增加)\(1\)。我们的目标是将 \(b_2,b_3,\cdots,b_n\) 全部变为 \(0\)。那么最终得到的序列 \(a\) 就是由 \(n\) 个 \(b_1\) 组成的。我们可以分类讨论 \(l,r\) 的取值:
- \(2\le l\le r<n\):这样可以改变 \(b_l,b_{r+1}\) 两个值。我们应在保证 \(b_l,b_{r+1}\) 一正一负时,尽量多地采取这种操作。
- \(l=1,2\le r<n\):这样可以将 \(b_{r+1}\) 减少 \(1\)。
- \(2\le l\le n,r=n\):这样可以将 \(b_l\) 增加 \(1\)。
- \(l=1,r=n\):这样对 \(b_2,b_3,\cdots,b_n\) 没有影响,相当于浪费了一次操作。
设 \(b_2,b_3,\cdots,b_n\) 中正数之和为 \(p\),负数之和的绝对值为 \(q\)。则第一种操作最多可以进行 \(\min(p,q)\) 次,剩下的数的绝对值为 \(|p-q|\),每个数可以执行第二种操作或第三种操作,需要进行 \(|p-q|\) 次。这样,最少操作次数就为 \(\min(p,q)+|p-q|=\max(p,q)\),\(a\) 就有 \(|p-q|+1\) 种可能。
*代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int n; ll p, q;
int a[N], b[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
b[i] = a[i] - a[i-1];
}
for (int i = 2; i <= n; ++i) {
if (b[i] > 0) p += (ll)b[i];
else q += (ll)-b[i];
}
printf("%lld\n%lld\n", max(p, q), abs(p-q)+1);
return 0;
}
7.4 二分
题目:给定一个长度为 \(n\) 的正整数数列 \(a\),求一个平均数最大的、长度不小于 \(L\) 的连续子段。求出平均数最大值乘 \(1000\) 后向下取整的值。\(1\le L\le n\le 10^5,1\le a_i\le 2000\)。
思路:
这道题并没有明显的二分的特征。我们可以考虑二分答案,若最优解为 \(x\),则当 \(mid\le x\) 时,必然可以找到一段,使得其平均值大于等于 \(mid\);否则一定找不到。即答案满足单调性。
如果我们将子段中的每个数都减去二分的值,就转化为判断“是否存在一个长度不小于 \(L\) 的子段,字段和非负”。我们考虑以下两个子问题:
-
求一个子段,它的和最大:我们可以 \(O(n)\) 扫描原数列,初始时 \(sum=0\),每次 \(sum\) 增加 \(a_i\),若 \(sum<0\),则令 \(sum=0\)。该过程中 \(sum\) 的最大值即为所求。
-
求一个子段,它的和最大,子段的长度不小于 \(L\):子段和可以转化为前缀和相减的形式。令 \(s_i=\sum_{j=1}^i a_j\),则所求即为:
\[\max_{i-j\ge L}\{a_{j+1}+a_{j+2}+\cdots+a_i\}=\max_{L\le i\le n}\{s_i-\min_{0\le j\le i-L}\{s_j\}\}\tag{7.5} \]注意到,随着 \(i\) 的增长,\(j\) 的取值范围每次只会增加 \(1\)。所以我们可以用一个变量记录当前最小值,每次与新的取值取最小值即可。
解决了问题 2 之后,我们只需要判断最大字段和是不是非负数,就可以确定二分上下界了。
时间复杂度 \(O(n\log n)\)。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
const double eps = 1e-5;
int n, L;
double a[N], b[N], s[N];
int main() {
scanf("%d%d", &n, &L);
for (int i = 1; i <= n; ++i) scanf("%lf", &a[i]);
double l = -1e6, r = 1e6;
while (r - l > eps) {
double mid = (l + r) / 2;
for (int i = 1; i <= n; ++i) b[i] = a[i] - mid;
for (int i = 1; i <= n; ++i) s[i] = s[i-1] + b[i];
double ans = -1e10, minl = 1e10;
for (int i = L; i <= n; ++i) {
minl = min(minl, s[i-L]);
ans = max(ans, s[i]-minl);
}
if (ans >= 0) l = mid;
else r = mid;
}
printf("%d\n", (int)(r*1000));
return 0;
}
题目:有 \(n\) 个元素,每对元素之间的大小关系是确定的且没有相同的元素,关系不具有传递性,也就是说,元素之间的大小关系是 \(n\) 个点与 \(\dfrac{n(n-1)}{2}\) 条有向边构成的任意有向图。你需要通过不超过 \(10000\) 次询问来确定这些元素的大小关系,每次询问你需要调用 compare
函数并传入两个参数 \(i,j\;(1\le i,j\le n)\),若编号为 \(i\) 的元素小于编号为 \(j\) 的元素则 compare
函数返回 true
,否则返回 false
。\(1\le n\le 1000\)。
思路:假设前 \(k-1\) 个元素已经排好,我们就可以通过二分找到第 \(k\) 个元素的位置。那么将 \(n\) 个元素全部排好的询问次数不超过 \(n\log n\)。
代码:
// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.
class Solution {
public:
vector<int> specialSort(int N) {
vector<int> ans;
ans.push_back(1);
for (int i = 2; i <= N; ++i) {
int l = 0, r = ans.size()-1;
while (l <= r) {
int mid = l + r>> 1;
if (compare(ans[mid], i)) l = mid + 1;
else r = mid - 1;
}
ans.insert(ans.begin()+l, i);
}
return ans;
}
};
7.5 排序
题目:有一个 \(n\times m\) 的矩阵,其中有 \(t\) 个位置 \((x_i,y_i)\) 的值为 \(1\),其余位置的值为 \(0\)。你可以进行任意多次操作,每次可以将相邻两个位置的值交换,注意第一行与最后一行,第一列与最后一列也视作相邻。问最后能否使每一行、每一列的价值之和分别相等,如果可以,输出最小操作次数。\(1\le n,m\le 10^5,0\le t\le \min(nm,10^5)\)。
思路:
显然,交换相邻两列的值对所有行都不会产生影响,交换相邻两行的值对所有列也不会产生影响。所以我们可以将行和列分开计算。这样,原问题就可以转换为环形均分纸牌问题:有 \(n\) 个人围成一圈,第 \(i\) 个人初始时有 \(a_i\) 颗糖果,每次一个人可以给相邻的人一颗糖果,问最少需要几次操作才能使所有人的糖果数都相等。显然 \(n\) 不能整除糖果总数时无解,接下来我们来讨论有解的情况。
![](https://cdn.luogu.com.cn/upload/image_hosting/mty6v3sx.png)
如图 \(\texttt{7-2}\),假设第 \(n\) 个人给第 \(1\) 个人 \(x_1\) 颗糖果,第 \(1\) 个人给第 \(2\) 个人 \(x_2\) 颗糖果,……,第 \((n-1)\) 个人给第 \(n\) 个人 \(x_n\) 颗糖果,那么有:
\[\left\{\begin{aligned} &a_1+x_1-x_2=\bar a\\ &a_2+x_2-x_3=\bar a\\ &\cdots\\ &a_n+x_n-x_1=\bar a \end{aligned}\right.\tag{7.6} \]其中,\(\bar a=\dfrac{1}{n}\sum_{i=1}^n a_i\)。将所有 \(x_i\) 都用 \(x_1\) 表示出来,就有:
\[\left\{\begin{aligned} &x_1=x_1\\ &x_2=a_1-\bar a+x_1\\ &x_3=a_1+a_2-2\bar a+x_1\\ &\cdots \\ &x_n=a_1+a_2+\cdots +a_{n-1}-(n-1)\bar a+x_1 \end{aligned}\right.\tag{7.7} \]设 \(c_i=\sum_{k=1}^{i-1}a_i-(i-1)\bar a\),特别地,令 \(c_1=0\)。则 \((7.7)\) 可化为:
\[\left\{\begin{aligned} &x_1=x_1-c_1\\ &x_2=x_1-c_2\\ &x_3=x_1-x_3\\ &\cdots \\ &x_n=x_1-c_n \end{aligned}\right.\tag{7.8} \]那么所求的最小值即为 \(|x_1|+|x_2|+\cdots+|x_n|=|x_1-c_1|+|x_1-c_2|+\cdots+|x_1-c_n|\),根据绝对值不等式,可知将 \(c\) 数组从小到大排序后,该式在 \(x_1=c_{\lceil(n+1)/2\rceil}\) 时取得最小值。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
#define int long long
const int N = 1e5+10;
int n, m, t;
int row[N], col[N];
int c[N];
int check(int n, int a[]) {
if (t % n) return -1;
memset(c, 0, sizeof c);
int avr = t / n, sum = 0;
for (int i = 1; i <= n; ++i) c[i] = sum - (i-1) * avr, sum += a[i];
sort(c+1, c+n+1);
int ans = 0;
for (int i = 1; i <= n; ++i) ans += abs(c[i]-c[(n+1)/2]);
return ans;
}
signed main() {
scanf("%lld%lld%lld", &n, &m, &t);
for (int i = 1; i <= t; ++i) {
int x, y; scanf("%lld%lld", &x, &y);
row[x] ++, col[y] ++;
}
int ansr = check(n, row), ansc = check(m, col);
if (ansr != -1 && ansc != -1) printf("both %lld\n", ansr+ansc);
else if (ansr != -1) printf("row %lld\n", ansr);
else if (ansc != -1) printf("column %lld\n", ansc);
else puts("impossible");
return 0;
}
题目:给定 \(P\) 组数据,每组数据包含 \(m\) 个整数 \(a\),每当输入的整数个数为奇数时,输出当前输入的所有数的中位数。\(1\le P\le 1000,1\le m\le 99999\),且 \(\sum m\le 5\times 10^5\)。
思路:
![](https://cdn.luogu.com.cn/upload/image_hosting/xstx49v8.png)
如图 \(\texttt{7-3}\),我们可以维护一个小根堆 \(\texttt{up}\) 和一个大根堆 \(\texttt{down}\),其中 \(\texttt{down}\) 存储较小的部分,\(\texttt{up}\) 存储较大的部分。保证 \(\texttt{down.size()}=\texttt{up.size()}\) 或 \(\texttt{down.size()}=\texttt{up.size()}+1\)。中位数即为 \(\texttt{down.top()}\)。每次 \(a_i\) 入堆时,我们考虑 \(a_i\) 应该放在哪个堆中:
- 若 \(a_i\ge\texttt{down.top()}\):说明 \(a_i\) 大于等于当前中位数,要插入到 \(\texttt{up}\) 中;
- 若 \(a_i<\texttt{down.top()}\):说明 \(a_i\) 小于当前中位数,要插入到 \(\texttt{down}\) 中。
我们还需要维护两个堆的大小关系。若 \(\texttt{down.size()}>\texttt{up.size()}+1\),则将 \(\texttt{down.top()}\)(即 \(\texttt{down}\) 中最大的数)插入到 \(\texttt{up}\) 中;若 \(\texttt{up.size()}>\texttt{down.size()}\),则将 \(\texttt{up.top()}\)(即 \(\texttt{up}\) 中最小的数)插入到 \(\texttt{down}\) 中。
时间复杂度 \(O(Tm\log m)\)。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int p, s, m;
int main() {
scanf("%d", &p);
while (p -- ) {
scanf("%d%d", &s, &m);
printf("%d %d\n", s, (m+1)/2);
int cnt = 0;
priority_queue<int, vector<int>, less<int>> down;
priority_queue<int, vector<int>, greater<int>> up;
for (int i = 1; i <= m; ++i) {
int x; scanf("%d", &x);
if (down.size() && x >= down.top()) up.push(x);
else down.push(x);
if (down.size() > up.size()+1) up.push(down.top()), down.pop();
if (up.size() > down.size()) down.push(up.top()), up.pop();
if (i & 1) {
printf("%d ", down.top());
cnt ++;
if (cnt % 10 == 0) puts("");
}
}
if (cnt % 10) puts("");
}
return 0;
}
题目:有多组测试数据,每组数据包含 \(n\) 个整数 \(a_i\),每次操作可以选择两个整数 \(1\le i,j\le n\;(i\ne j)\) 并交换 \(a_i,a_j\)。问至少要几次操作才能将 \(a\) 数组升序排列。\(1\le n\le 5\times 10^5,1\le a_i<10^{10}\)。
思路:显然题目所求的即为 \(a\) 中逆序对的数量。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long
const int N = 5e5+10;
int n, a[N], tmp[N];
int merge_sort(int l, int r) {
if (l >= r) return 0;
int mid = l + r >> 1;
int ans = merge_sort(l, mid) + merge_sort(mid+1, r);
int i = l, j = mid+1, k = 1;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) tmp[k ++] = a[i ++];
else tmp[k ++] = a[j ++], ans += mid-i+1;
}
while (i <= mid) tmp[k ++] = a[i ++];
while (j <= r) tmp[k ++] = a[j ++];
for (int i = l, j = 1; i <= r; ++i, ++j) a[i] = tmp[j];
return ans;
}
signed main() {
scanf("%lld", &n);
while (n) {
for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
int ans = merge_sort(1, n);
printf("%lld\n", ans);
scanf("%lld", &n);
}
return 0;
}
7.6 RMQ
题目:给定 \(n\) 个整数 \(a_i\) 和 \(m\) 次询问,每次询问给定两个整数 \(l,r\;(1\le l\le r\le n)\),求出 \(\max_{i=l}^r a_i\)。\(1\le n\le 2\times 10^5,1\le m\le 10^4\)。
思路:
我们可以用 ST 表来完成这道题,其运用的是倍增的思想。令 \(f_{i,j}\) 表示以 \(i\) 为区间左端点,区间长度为 \(2^j\) 的区间中的最大值。初始转态为 \(f_{i,0}=a_i\)。考虑如何转移:由于 \(f_{i,j}\;(j>0)\) 表示区间 \([i,i+2^j-1]\) 中的最大值,我们可以将其分为两个区间 \([i,i+2^{j-1}-1]\) 和 \([i+2^{j-1},i+2^{j}-1]\),那么有:
\[f_{i,j}=\max\{f_{i,j-1},f_{i+2^{j-1},j-1}\}\tag{7.9} \]接下来考虑如何处理询问。令 \(k\lfloor\log_2(r-l+1)\rfloor\),显然有 \(ans=\max(f_{l,k},f_{r-2^{k}+1,k})\)。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 5e5+10, M = 20;
int n, m;
int a[N], f[N][M];
int query(int l, int r) {
int k = log2(r-l+1);
return max(f[l][k], f[r-(1<<k)+1][k]);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), f[i][0] = a[i];
for (int j = 1; (1<<j) <= n; ++j) {
for (int i = 1; i+(1<<j)-1 <= n; ++i)
f[i][j] = max(f[i][j-1], f[i+(1<<j-1)][j-1]);
}
int l, r;
scanf("%d", &m);
while (m --) {
scanf("%d%d", &l, &r);
printf("%d\n", query(l, r));
}
return 0;
}
标签:10,le,return,int,基础,times,II,算法,include
From: https://www.cnblogs.com/Jasper08/p/17461504.html