CSP - S

*约定：$a/b$ 表示 $a$ 整除以 $b$，$\frac{a}{b}$ 表示 $a$ 除以 $b$，题目标题中带 ※ 表示有意义的难题。

0x01. 位运算

---

T1 - 1 a^b

link

题面

求 $a^b \bmod p$，其中 $1 \le a,p \le 10^9, 0 \le b \le 10^9$。

思路

因为可以对 $p$ 取模，根据同余定理（$(a \times b)\bmod d=[(a \bmod p) \times (b \bmod p)] \bmod p$），所以不用担心精度问题。

但是 $0 \le b \le 10^9$，直接遍历 $b$ 次求解不行，那么考虑 $\mathcal{O}(\log b)$ 的算法。

发现：$a^b=a^{\lfloor \frac{b}{2} \rfloor} \times a^{\lceil \frac{b}{2} \rceil}$，即对于奇数，$a^b=a^{b/2}\times a^{b/2+1}=a^{b/2}\times a^{b/2}\times a$，对于偶数，$a^b=a^{b/2}\times a^{b/2}$。

可以分治求解（快速幂）：用一个变量 res 记录最终答案，每次将 $a$ 设为 $a^2$，将 $b$ 设为 $b/2$，当 $b$ 为奇数时将 res 设为 res * a（记得所有乘法都要对 $p$ 取余），当 $b$ 为 $0$ 时 res 即为答案（当 $b$ 为 $1$ 时 res 会直接变成 $a$）。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, p;

ll qpow (ll a, ll b, ll p)
{
    ll res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int main ()
{
    cin >> a >> b >> p;
    cout << qpow (a, b, p);
    return 0;
}

---

T1 - 2 增加模数

link

题面

给定 $H$ 对非负整数数对 $(A_1,B_1)\dots(A_H,B_H)$ 和一个正整数 $M$。

请你计算并输出 $({A_1}^{B_1}+{A_2}^{B_2}+\dots+{A_H}^{B_H}) \bmod M$。

思路

快速幂模版题，将原式拆成 $({A_1}^{B_1}\bmod M+{A_2}^{B_2}\bmod M+\dots+{A_H}^{B_H}\bmod M)\bmod M$，对每个幂式分别求快速幂再一边取模一边求和输出即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 4.5e4 + 10;
typedef long long ll;
ll a[N], b[N], t;

ll qpow (ll a, ll b, ll p)
{
    ll res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int main ()
{
    cin >> t;
    while (t --)
    {
        ll h, m, sum = 0; cin >> m >> h;
        for (int i = 1; i <= h; i ++) cin >> a[i] >> b[i];
        for (int i = 1; i <= h; i ++)
            sum = (sum + qpow (a[i], b[i], m)) % m;
        cout << sum << '\n';
    }
    return 0;
}

---

T1 - 3 64位整数乘法

link

题面

求 $a \times b \bmod p$，其中 $1 \le a,b,p \le 10^{18}$。

思路

一眼高精度啊（但是老师不让用

考虑使用快速幂思想：

快速幂思想：$a^b=(a^2)^{\frac{b}{2}}$（$b$ 为偶数）

以此类推本题可以变为：$a \times b=(a \times 2)\times\frac{b}{2}$（$b$ 为偶数）

$b$ 为奇数时情况也类似快速幂，具体见代码。

代码

---

#include <bits/stdc++.h>
//push_back
#define int long long
using namespace std;
int a, b, p;

int qmul (int a, int b, int p)
{
	int res = 0;
	while (b)
	{
		if (b & 1) res = (res + a) % p; //和快速幂情况类似
		a = (a + a) % p;
		b >>= 1;
	}
	return res;
}

signed main ()
{
    cin >> a >> b >> p;
	cout << qmul (a, b, p);
	return 0;
}

---

T1 - 4 起床困难综合征

link

题面

给定两个数 $n,m$ 和 $n$ 组操作，每组操作由一个字符串 $\text{op} \in \{\tt{OR,AND,XOR}\}$ 和一个参数 $t$ 组成，第 $i$ 组操作就是由 $\text{op}_i$ 和 $t_i$ 组成，当一个数 $k$ 经过第 $i$ 个操作时，$k$ 会改变其值，具体值由 $\text{op}_i$ 决定：

• 当 $\text{op}_i=\tt{OR}$ 时，$k \gets k \ | \ t_i$。
• 当 $\text{op}_i=\tt AND$ 时，$k \gets k \ \& \ t_i$。
• 当 $\text{op}_i=\tt{XOR}$ 时，$k \gets k \oplus t_i$。

（其中 $|,\&,\oplus$ 分别表示按位或，按位与和按位异或）。

求一个数 $x \in [0,m]$，使得 $x$ 按 $1 \sim n$ 的顺序经过 $n$ 次操作后值最大，问在此前提下最后的值（最大）是多少。

题目中 $2 \le n \le 10^5,2 \le m \le 10^9,0\le t\le 10^9$。

思路

先考虑暴力做法，枚举 $x \in [0,m]$，对于每个 $x$ 都进行 $n$ 次操作，最后取最大值即可。但此种方法时间复杂度为 $\mathcal{O}(n \cdot m)$，不可通过 $\text{1s}$ 的时限。

发现在二进制下，位运算（按位与、或、异或）的每一位的结果是互不干扰的，即一个二进制位的运算不影响其他位。

那么为了使得最后的值尽可能大，则最后的值在二进制下的数位 $1$ 的数量要尽可能多，则我们可以通过某种策略使得最后的值在二进制下的数位 $1$ 的数量尽可能多。

具体来讲，我们先实现一个函数 $\text{calc}(i,d)$，可以返回 $x$（在二进制下）的第 $i$ 个数位的值若为 $d$，那么最终 $d$ 这个数位经过所有操作后的值为多少，其中 $d \in \{0,1\}$。用这种方法枚举 $x$ 在二进制下的（可能的）每一位，求出该位为 $0$ 和 $1$ 时最终的值变为多少，然后对每一位进行讨论（注意在这个过程中求的值始终不能超过 $m$）。

注意：要从 $x$ 的高位往低位枚举，尽量满足高位。

• 如果当前位最后可能变为 $1$：

  • 如果可以从 $0$ 变为 $1$，则一定这么做，因为不仅能变为 $1$，选 $0$ 还能使求的 $x$ 尽量小，使得可以给剩下的数位留出更多空间。
  • 如果只能从 $1$ 变为 $1$，则因为是从高往低枚举，所以如果选了 $1$，就判断选 $1$ 是否会让 $x$ 超出 $m$，若不会则可以选 $1$。

• 如果当前位最后只能变为 $0$：则当前位选 $0$ 就好，原因同「可以从 $0$ 变为 $1$」时的情况。

时间复杂度 $\mathcal{O}(n\log m)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, t[N];
string op[N];

bool calcbit (int num, int bit)
{
	for (int i = 1; i <= n; i ++)
	{
		int x = t[i] >> num & 1; //只要用第num位
		if (op[i] == "OR") bit |= x;
		else if (op[i] == "XOR") bit ^= x;
		else bit &= x;
	}
	return bit;
}

int main ()
{
    cin >> n >> m;
	for (int i = 1; i <= n; i ++) cin >> op[i] >> t[i];
	int now = 0, ans = 0;
	for (int sta = 30; sta >= 0; sta --)
	{
		bool t0 = calcbit (sta, 0), t1 = calcbit (sta, 1);
		if (now + (1 << sta) <= m && t0 < t1) now += (1 << sta), ans += (t1 << sta);
		else ans += (t0 << sta);
	}
	cout << ans;
	return 0;
}

---

T1 - 5 最短Hamilton路径

link

题面

给定一张 $n$ 个点的带权无向图，点从 $0 \sim n-1$ 标号，求起点 $0$ 到终点 $n-1$ 的最短 Hamilton 路径。

Hamilton 路径的定义是从起点到终点不重不漏地经过每个点恰好一次的路径。

$1 \le n \le 20$。

思路

考虑状态压缩 DP。

设 $f_{i,j}$ 表示「在前 $k$ 个点中刚好走到编号为 $j$ 的点的最短 Hamilton 路径长度」，$i$ 是一个 $k$ 位二进制数，表示编号的前 $k$ 个点走没走，用一个整数表示：整数在二进制下的第 $p$ 位（从右往左编号，从 $0$ 开始）若为 $1$，表示第 $p$ 个点走过了；否则就是没走过。

初始化：走到第 $0$ 个点时最短路径长度为 $1$，而此时前 $0$ 个点（即第 $0$ 号点）中第 $0$ 个点已经走过了，所以初始化 $f_{1,0}=0$，其余初始化为无穷大。

答案：即 $i$ 表示到第 $n-1$ 个点，且刚好走到第 $n-1$ 个点的最短 Hamilton 路径长度，即 $f_{2^n-1,n-1}$。

那么我们开始 DP：枚举 $i \in [0,2^n)$，即枚举 $f$ 的第一维（点集状态），共 $2^n$ 个状态。再枚举 $j \in [0,n)$，即 $f$ 的第二维。最后类似 Floyd，在第三层循环枚举 $k \in [0,n)$（此处 $k$ 与状态表示中的 $k$ 含义不同），表示走完 $i$ 表示的点集后走到 $j$ 的途中可以经过一个中间点（断点），此时还没有走到点 $j$，那么可以经过 $k$ 号点到达 $j$ 号点。状态方程为：

$$f_{i,j}=\min\{f_{i,j},f_{i-2^j,k}+w_{k,j}\}$$

其中 $w$ 是题目给的权值数组。

但是这样枚举出来的状态有错误，因为我们没有判一些不能进的循环：

• 当 $i$ 表示的点集在二进制下的第 $0$ 位为 $0$ 时，表示第 $0$ 个点没走，则直接跳过本次 $i$ 的循环，因为第 $0$ 个点是必须走的。
• 当 $i$ 表示的点集在二进制下的第 $j$ 位为 $0$ 时，表示第 $j$ 个点没走，则直接跳过本次 $j$ 的循环，因为第 $j$ 个点是必须走的（见状态表示中加粗字）。
• 当 $i-2^j$（在走到点 $j$ 前）表示的点集在二进制下的第 $k$ 位为 $0$ 时，表示第 $k$ 个点作为中间点没走，本来这里也应该跳过 $k$ 的循环，但也可以不用；因为当 $k$ 没走过时， $f_{i-2^j,k}$ 是未更新的（即为无穷大），所以也可以不用写这个条件。

时间复杂度 $\mathcal{O}(2^nn^2)$，有些极限，需要开 O2。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int n, w[N + 5][N + 5], f[(1 << N) + 5][N + 5];

int main ()
{
    cin >> n;
	for (int i = 0; i < n; i ++)
		for (int j = 0; j < n; j ++) cin >> w[i][j];
	memset (f, 0x3f, sizeof f);
	f[1][0] = 0;
	for (int i = 0; i < 1 << n; i ++)
		if (i & 1) //如果第1个点走了
			for (int j = 0; j < n; j ++)
				if (i >> j & 1) //如果第j个点要走
					for (int k = 0; k < n; k ++) //枚举断点
						f[i][j] = min (f[i][j], f[i ^ (1 << j)][k] + w[k][j]);
	cout << f[(1 << n) - 1][n - 1];
	return 0;
}

---

T1 - 6 飞行员兄弟 ※

link

题面

一个 $4 \times 4$ 的字符矩阵 $w$（下标从 $0$ 开始），$w_{i,j} \in \{+,-\}$（$i,j \in [0,3]$），$+$ 表示 $1$，$-$ 表示 $0$，有一种操作：

更改第 $i$ 行第 $j$ 列的值并同时改变所在行和所在列的所有值（$+$ 变 $-$，$-$ 变 $+$）。

求在最少多少次操作内能使 $w$ 全部变为 $-$。并在保证操作数最少，同行从上到下，同列从左到右优先的条件下输出每次操作的 $i$ 和 $j$。

思路

枚举，但是有方法。

定义函数 $\text{pos}(x,y)=4x+y$，下面有用。

首先将字符转化为题目给的数字，再将二维数组转化为一维数组：从 $w_{i,j}$ 变为 $w_{\text{pos}(i,j)}$ 即可。

用一个整数 $\text{sta}$ 压缩这个一维数组，接下来就可以对 $\text{sta}$ 的副本进行操作。为方便，下面的 $w_{i,j}$ 即为 $\text{sta}$ 在二进制下的第 $\text{pos}(i,j)$ 位

发现题目给的“操作”有点难以实现，那么考虑构造数组 $c_{i,j}$，使得只要让 $\text{sta} \oplus c_{i,j}$ 就能使 $w_{i,j\in[0,3]}$ 和 $w_{i\in[0,3],j}$ 全部改变。那么只要使 $c_{i,j}$ 在二进制下的这些数位都是 $1$ 即可：即遍历 $i\in[0,3]$，在内部再遍历 $j\in[0,3]$，再遍历断点 $k \in [0,3]$，使 $c_{i,j}\gets c_{i,j}+2^{\text{pos}(i,k)}+2^{\text{pos}(k,j)}$，最后将多加了一次的 $2^{\text{pos}(i,j)}$ 减去一次即可。

处理完 $c$ 后，枚举 $i \in [0,2^{16})$，即枚举每个数位操不操作（而不是枚举数位状态！），再枚举 $j \in[0,16)$，判断 $i$ 的第 $j$ 位（二进制下）是否为 $1$（注意 $c$ 使用的是二维下标，所以当使用 $j$ 作 $c$ 的下标时，应为 $c_{j/4,j\ \bmod \ 4}$），是则代表要操作。每次拷贝一份 $\text{sta}$，设其为 $t$ 并开一个 vector <pair <int, int> > 用来存答案。如果 $i$ 的第 $j$ 位为 $1$，则让 $t \gets t \oplus c_{j/4,j\ \bmod \ 4}$，并将 $j/4$ 和 $j \bmod 4$ 存入答案数组。

最后当 $t=0$ 时，更新最终答案（记得输出时的下标从 $1$ 开始哦）。

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> PII;
int sta, cov[7][7];

int get (int x, int y) { return x * 4 + y; }

int main ()
{
    for (int i = 0; i < 4; i ++)
		for (int j = 0; j < 4; j ++)
		{
			char c; cin >> c;
			if (c == '+') sta += 1 << get (i, j);
		}
	for (int i = 0; i < 4; i ++)
		for (int j = 0; j < 4; j ++)
		{
			for (int k = 0; k < 4; k ++) cov[i][j] += (1 << get (i, k)) + (1 << get (k, j));
			//断点行所在列和断点列所在行
			cov[i][j] -= 1 << get (i, j);
		}
	vector <PII> ans;
	for (int i = 0; i < 1 << 16; i ++)
	{
		int now = sta; vector <PII> path;
		for (int j = 0; j < 16; j ++)
			if (i >> j & 1)
			{
				int x = j / 4, y = j % 4;
				now ^= cov[x][y];
				path.push_back ({x, y});
			}
		if (!now && (ans.size () == 0 || ans.size () > path.size ())) ans = path;
	}
	cout << ans.size ();
	for (int i = 0; i < ans.size (); i ++) cout << '\n' << ans[i].first + 1 << ' ' << ans[i].second + 1;
	return 0;
}

---

0x02. 递推与递归

---

T2 - 1 递归实现指数型枚举

link

过于简单，不予讲解。

题面

思路

代码

---

T2 - 2 递归实现组合型枚举

link

过于简单，不予讲解。

题面

思路

代码

---

T2 - 3 递归实现排列型枚举

link

过于简单，不予讲解。

题面

思路

代码

---

T2 - 4 费解的开关

link

题面

给定 $5 \times 5$ 的整数矩阵 $a$（下标从 $0$ 开始），每个元素都是 $0/1$，现定义一个操作函数 $\text{change}(x,y)$ 表示将 $a_{i,j},a_{i+1,j},a_{i-1,j},a_{i,j+1},a_{i,j-1}$（即 $a_{i,j}$ 与其上下左右的共 $5$ 个格子）全部翻转（$0$ 变 $1$，$1$ 变 $0$）。

现给定 $T$ 组数据，对于每组数据，询问：能否在 $6$ 次调用操作函数内使得矩阵内所有元素变成 $1$。若能，输出最少要调用多少次操作函数；若不能，输出 $-1$。

思路

我感觉这题更适合放到位运算里去（虽然也能用搜索写）。

思考：只需要对于值为 $0$ 的元素，对其上 / 下 / 左 / 右 / 自己进行 $\text{change}$ 操作即可。

发现如果用本行的（左 / 右 / 自己）更改，则对于右 / 左 / 自己的值依然要进行操作，最终和没改一样。

所以我们这里规定用正下方的值来 $\text{change}$ 使得为 $0$ 的值变成 $1$。

但仅仅是这样枚举是枚举不到所有情况的，因为第 $0$ 行没有上一行，所以也可以随便按。

那么可以枚举 $i \in [0,2^5)$，$i$ 在二进制下的每一位就代表这个位置对应的数要不要进行 $\text{change}$ 操作：$0$ 代表不要，$1$ 代表要。然后可以得到一个新的第 $0$ 行，用第 $1$ 行填补第 $0$ 行的 $0$，再用第 $2$ 行的填补第 $1$ 行的……一直到第 $4$ 行。

此时判断第 $4$ 行是不是全为 $1$ 即可更新答案。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 8;
int dx[] = {0, 0, -1, 1, 0};
int dy[] = {-1, 1, 0, 0, 0};
bool a[N][N], x[N][N];
int t;

void change (int x, int y, bool u[N][N])
{
	for (int i = 0; i < 5; i ++)
	{
		int nx = x + dx[i], ny = y + dy[i];
		if (nx < 1 || ny < 1 || nx > 5 || ny > 5) continue;
		u[nx][ny] ^= 1;
	}
}

bool judge ()
{
	for (int i = 1; i <= 5; i ++)
		if (!x[5][i]) return false;
	return true;
}

int main ()
{
    cin >> t;
	while (t --)
	{
		int res = 0x3f3f3f3f;
		for (int i = 1; i <= 5; i ++)
			for (int j = 1; j <= 5; j ++)
			{ char c; cin >> c, a[i][j] = c - '0'; }
		for (int i = 0; i < 1 << 5; i ++) //枚举第一行每个按钮按或不按
		{
			memcpy (x, a, sizeof x);
			int step = 0;
			for (int j = 0; j < 5; j ++)
				if (i >> j & 1) change (1, j + 1, x), step ++;
			for (int r = 2; r <= 5; r ++)
				for (int c = 1; c <= 5; c ++)
					if (!x[r - 1][c]) change (r, c, x), step ++;
			if (judge ()) { if (step <= 6) res = min (res, step); }
		}
		cout << (res == 0x3f3f3f3f ? -1 : res) << '\n';
	}
	return 0;
}

---

T2 - 5 奇怪的汉诺塔

link

题面

跟普通汉诺塔相同，但是是给定四根柱子 A，B，C 和 D。

思路

根据三柱问题思路，可以思考：如果当前先放 $j$ 个盘子到一根柱子上，剩下三根柱子就可以根据三柱问题求解，最后把 $j$ 个盘子移回来，那么预处理三柱问题的答案数组，加一维枚举 $j$ 即可。

代码

#include <bits/stdc++.h>
using namespace std;
//奇怪的汉诺塔
const int N = 30;
int t[N], f[N];

int main ()
{
	memset (f, 0x3f, sizeof f); //要取min 
	t[1] = f[1] = 1; //初始化 
	for (int i = 2; i <= 12; i ++) t[i] = t[i - 1] * 2 + 1; //求三柱问题
	for (int i = 2; i <= 12; i ++)
		for (int j = 1; j < i; j ++) //枚举放多少个塔到一根空的柱子上
			f[i] = min (f[i], f[j] * 2 + t[i - j]); //空柱子上要移回来, 剩下的是三柱问题
	for (int i = 1; i <= 12; i ++) cout << f[i] << '\n'; 
	return 0;
}

---

T2 - 6 约数之和 ※

link

题面

假设现在有两个自然数 $A$ 和 $B$，$S$ 是 $A^B$ 的所有约数之和。

请你求出 $S\bmod9901$ 的值是多少。

思路

直接求也可以，但是需要卡亿点常，所以可以用递归优化：

发现时间瓶颈在于求 $p^0+p^1+p^2+\dots+p^k$，那么可以设 $\text{sum}(p,k)=\sum\limits_{i=0}^kp^i$，则：

• 当 $k$ 为奇数时：

$$\begin{aligned} 1+p^1+p^2+p^3+\dots+p^k &= \ ?\\ &=(1+p^1+p^2+\dots+p^{\frac{k-1}{2}})+(p^{\frac{k+1}{2}}+p^{\frac{k+1}{2}+1}+\dots+p^k) \\ &=(1+p^1+p^2+\dots+p^{\frac{k-1}{2}})+(p^{\frac{k+1}{2}} \times 1+p^{\frac{k+1}{2}} \times p+\dots+p^{k-1} \times p) \\ &=(1+p^1+p^2+\dots+p^{\frac{k-1}{2}})+p^{\frac{k+1}{2}} \times (1+p+p^2+\dots+p^{\frac{k-1}{2}}) \\ &=(1+p^1+p^2+\dots+p^{\frac{k-1}{2}}) \times (1+p^{\frac{k+1}{2}}) \end{aligned}$$

发现 $1+p^1+p^2+\dots+p^{\frac{k-1}{2}}$ 可以递归，剩下可以快速幂，即 $\text{sum}(p,k)=\text{sum}(p,\frac{k-1}{2}) \times (1+p^{\frac{k+1}{2}})$。

• 当 $k$ 为偶数时：

  也可以像上面那样推，但也可以直接写成 $\text{sum}(p,k-1) \times p^k$（因为偶数 $-1=$ 奇数），我选择后者。

那么就可以解了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 9901;
vector <pair <ll, ll> > prm;
ll a, b, ans = 1;

void get_divor (ll x)
{
	for (ll i = 2; i <= x; i ++)
		if (x % i == 0)
		{
			int cnt = 0;
			while (x % i == 0) cnt ++, x /= i;
			prm.push_back ({i, cnt});
		}
}

ll qpow (ll b, ll ex)
{
	ll res = 1;
	while (ex)
	{
		if (ex & 1) res = res * b % MOD;
		b = b * b % MOD;
		ex >>= 1;
	}
	return res % MOD;
}

ll sum (ll p, ll ex)
{
	if (!p) return 0;
	if (!ex) return 1;
	if (ex & 1) return ((sum (p, (ex - 1) / 2) % MOD) * (qpow (p, (ex + 1) / 2) + 1) % MOD) % MOD;
	return (sum (p, ex - 1) % MOD + qpow (p, ex)) % MOD;
}

int main ()
{
	cin >> a >> b;
	if (!a) { cout << 0; return 0; }
	get_divor (a);
	for (auto i : prm)
	{
		ll p = i.first, ex = i.second * b;
		ans = (ans * sum (p, ex) % MOD) % MOD;
		//sum (p, ex) 表示 p^0+p^1+...+p^ex
	}
	cout << ans % MOD;
	return 0;
}

---

T2 - 7 分形之城 ※

题面

link

给定两街区编号 $a,b$，求等级 $n$ 的城市里 $a$ 和 $b$ 的直线距离（每个小正方形的边长为 $10$）。

思路

发现是找规律，如果已知等级 $n$ 的城市图，那么 $n+1$ 等级的城市图为：

等级 $n$ 顺时针旋转 $90^\circ$（编号 $1$)	等级 $n$ 平移至此处（编号 $2$）
等级 $n$ 逆时针旋转 $90^\circ$（编号 $4$）	等级 $n$ 平移至此处（编号 $3$）

则以编号为 $1$ 的左上角为原点，画图得：

那么思考 $n$ 与各种值的数量关系：

我们知道边长为 $2^n$，总的 $1$ 阶城区数为 $2^n \times 2^n=4^n$，而分成 $4$ 等分（上一阶）的边长为 $2^{n-1}$。

所以设一个点 $P(x,y)$，将它放在 $1\sim4$ 号格里，依次探寻规律。

设 $l=2^{n-1}$。

注意我只写了 $1,2,3$，因为 $4$ 很特殊：

将其转移至第 $1$ 编号（象限），得到如上（因为转移了，所以 $x$ 坐标实际上是 $2\times l-y-1$）。

具体见代码。

代码

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define sq(a) (a) * (a)
using namespace std;
int t;

int calc_dist (int x1, int y1, int x2, int y2)
{
	#define epd(x) x = x * 10 - 5
	epd (x1), epd (x2), epd (y1), epd (y2);
	#undef epd
	int xs = abs (x2 - x1), ys = abs (y2 - y1);
	return (int) round (sqrt (xs * xs + ys * ys));
}

pair <int, int> id2pos (int id, int n) //id为街区编号, n为等级 
{
	if (!n) return {0, 0};
	int len = 1ll << n - 1, cnt = 1ll << 2 * (n - 1);
	auto nowp = id2pos (id % cnt, n - 1); int x = nowp.x, y = nowp.y;
	int op = id / cnt; //当前区块数
	if (op == 0) return {y, x}; //顺时针90°
	else if (op == 1) return {x, y + len}; //y平移，x不变
	else if (op == 2) return {x + len, y + len}; //整个平移
	else return {2 * len - 1 - y, len - x - 1}; //注意!!! 1.转移象限 2.整体继续移动
}

signed main ()
{
    cin >> t;
	while (t --)
	{
		int n, a, b; cin >> n >> a >> b;
		auto pa = id2pos (a - 1, n), pb = id2pos (b - 1, n);
		double pos = sqrt (sq (abs (pa.x - pb.x)) + sq (abs (pa.y - pb.y))) * 10;
		cout << (int)round (pos) << '\n';
	}
	return 0;
}

---

T2 - 8 分形

题面

link

设 $B(n)$为第 $n$ 阶“盒子分形”，则 $B(1)=\tt{X}$，

B(n)=
  B(n - 1)        B(n - 1)

          B(n - 1)

  B(n - 1)        B(n - 1)

现在求 $B(n),n\leq7$。

思路

是一道非常简单的规律题，有了上一题的经验，我们知道 $B(n)$ 的边长为 $l(n)=3^{n-1}$。

那么可以枚举 $B(n-1)$ 里的每个点，算它扩充到 $B(n)$ 时的坐标变换。

具体见代码。

代码

#include <bits/stdc++.h>
using namespace std;
vector <vector <char> > ot[8];
int n, p[10] = {1, 3, 9, 27, 81, 243, 729, 2187};

void Box (int n)
{
	if (n == 0)
	{
		ot[0].push_back ({'X'});
		return;
	}
	ot[n] = vector <vector <char> > (p[n], vector <char> (p[n], ' '));
	for (int i = 0; i < p[n - 1]; i ++)
		for (int j = 0; j < p[n - 1]; j ++)
		{
			ot[n][i][j] = ot[n][i][j + p[n] - p[n - 1]] =
			ot[n][i + p[n - 1]][j + p[n - 1]] =
			ot[n][i + p[n] - p[n - 1]][j] =
			ot[n][i + p[n] - p[n - 1]][j + p[n] - p[n - 1]] = ot[n - 1][i][j];
		}
}

int main ()
{
	for (int i = 0; i < 7; i ++) Box (i);
    while (cin >> n && n != -1)
    {
    	n --;
    	for (int i = 0; i < p[n]; i ++)
		{
			for (int j = 0; j < p[n]; j ++) cout << ot[n][i][j];
			cout << '\n';
		}
		cout << "-\n";
	}
	return 0;
}

---

0x03. 前缀和和差分

---

T3 - 1 激光炸弹

link

题面

地图上有 $N$ 个目标，用整数对 $(X_i,Y_i)$ 表示目标在地图上的位置，每个目标都有一个价值 $W_i$。

注意：不同目标可能在同一位置。

现在有一种新型的激光炸弹，可以摧毁一个包含 $R\times R$ 个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即正方形的边必须和 $x,y$ 轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

思路

二维前缀和模版（模版应该都能现场推），即 $s_{i,j}=s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}+a_{i,j}$。

枚举正方形的左上角即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10, BR = 5e3 + 1;
int n, r, prs[N][N], ans;

int main ()
{
    cin >> n >> r;
	for (int i = 1; i <= n; i ++) { int x, y, w; cin >> x >> y >> w, prs[x + 1][y + 1] += w; }
	for (int i = 1; i <= BR; i ++)
		for (int j = 1; j <= BR; j ++)
			prs[i][j] += prs[i - 1][j] + prs[i][j - 1] - prs[i - 1][j - 1];
	if (r >= BR) r = BR;
	for (int i = r; i <= BR; i ++)
		for (int j = r; j <= BR; j ++)
		{
			int x1 = i, y1 = j, x2 = i - r, y2 = j - r;
//			cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n';
			ans = max (ans, prs[x1][y1] - prs[x2][y1] - prs[x1][y2] + prs[x2][y2]);
		}
	cout << ans;
	return 0;
}

---

T3 - 2 增减序列 ※

link

题面

给定一个长度为 $n$ 的数列 $a_1,a_2,\dots,a_n$，每次可以选择一个区间 $[l,r]$，使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

思路

因为是区间加减，所以很自然的想到差分，构造序列 $b$，使 $b_1=a_1,b_i=a_i-a_{i-1}(n\ge i>1),b_{n+1}=0$。

问题转化为每次选两个数 $b_i,b_j$ 令其中一个加 $1$，另一个减 $1$。

最后要求转化为 $b_{2\sim n}=0$，即从第 $2$ 项到第 $n$ 项全部为 $0$（这样原数组就全部一样）。

那么选出 $b_i$ 和 $b_j$ 的情况有 $4$ 种：

1. $1<i,j<n+1$，这样能够使得 $b_{2\sim n}$ 中的两个数分别加一和减一，当 $b_{2\sim n}$ 中至少存在一对 $(i,j)$ 使得 $b_i$ 和 $b_j$ 一正一负时尽量采取此种操作（令正数减一，负数加一，使得这两个数都更接近 $0$，一定是最优选择）。
2. $i=1,1<j<n+1$，这样相当于只改变了 $b_{2\sim n}$ 中的一个值（$b_1$ 对结果无影响）。
3. $1<i<n+1,j=n+1$，和上种情况一样（$b_{n+1}$ 对结果无影响）。
4. $i=1,j=n+1$，无意义，即将原数组 $a_{1\sim n}$ 全部加上 $1$ 或减去 $1$，一定不优。

所以，要尽量选取操作 1，在 $b_{2\sim n}$ 中没有一正一负时就可以任意选取操作 2 或 3。

设 $b_{2\sim n}$ 中正数总和为 $p$，负数总和的绝对值为 $q$。

那么操作 1 的执行次数为 $b$ 中“正数总和”与“负数总和的绝对值”的较小值，即 $\min\{p,q\}$，剩了 $|p-q|$ 个正或负数未解决，那么任意执行操作 2 或 3 的次数即为 $|p-q|$，最终操作次数为 $\min\{p,q\}+|p-q|=\max\{p,q\}$。

最终得到的序列由于在执行完 $\min\{p,q\}$ 次操作后有 $|p-q|$ 次的操作数可以修改 $b_1$ 或 $b_{n+1}$，那么最终能得到 $|p-q|+1$ 中不同的 $b_1$，即有 $|p-q|+1$ 种不同的序列。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
long long s1, s2;
int n, a[N];

int main ()
{
    cin >> n;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	for (int i = 2; i <= n; i ++)
	{
		int x = a[i] - a[i - 1];
		if (x > 0) s1 += x;
		else s2 += -x;
	}
	cout << max (s1, s2) << '\n' << abs (s1 - s2) + 1;
	return 0;
}

---

T3 - 3 最高的牛

link

题面

有 $N$ 头牛站成一行，被编队为 $1,2,3,\dots,N$，每头牛的身高都为整数。

当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。

现在，我们只知道其中最高的牛是第 $P$ 头，它的身高是 $H$ ，剩余牛的身高未知。

但是，我们还知道这群牛之中存在着 $H$ 对关系，每对关系都指明了某两头牛 $A$ 和 $B$ 可以相互看见。

求每头牛的身高的最大可能值是多少。

思路

既然是 $A$ 和 $B$ 可以互相看见，那么可以用差分数组 $b_i$ 来确定身高。

初始设置 $b_1=H,b_{2\sim n}=0$，即所有牛都是最大身高。

然后如果给定 $A,B$，说明 $A+1\sim B-1$ 的牛都没有 $A$ 和 $B$ 高，那么根据差分经典公式，得 $b_{A+1}\gets b_{A+1}+1,b_{B}\gets b_{B}-1$。

然后由于我们说的是 $A+1\sim B-1$，即代表 $A\le B$，所以当 $A>B$ 时，交换即可；另外可能重复给出关系，所以用 map 记录每对关系即可（不用 unordered_map 是因为它的下标不能为 pair，但 map 的下标只要定义了 operator< 即可）。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10;
map <pair <int, int>, bool> sta;
int n, p, h, m, hei[N];

int main ()
{
    cin >> n >> p >> h >> m;
    hei[1] = h;
	while (m --)
	{
		int a, b; cin >> a >> b;
		if (a > b) swap (a, b);
		if (a == b) continue;
		if (sta[{a, b}] == true) continue;
		sta[{a, b}] = true;
		hei[a + 1] --, hei[b] ++;
	}
	for (int i = 1; i <= n; i ++) hei[i] += hei[i - 1], cout << hei[i] << '\n';
	return 0;
}

---

0x04. 二分

---

T4 - 1 防线

link

题面

有一条无限长的数轴；给定 $N$ 个三元组 $(S,E,D)$ 表示从数轴的下标 $S$，每隔 $D$ 个单位长度就有一个障碍，直到超过了 $E$ 的前一次为止，即在下标为 $S,S+D,S+2D,\dots,S+kD(k\in\Z,S+kD\le E,S+(k+1)D>E)$ 的地方都有障碍。

不同组的障碍可能会重叠，所以一个坐标上可能有多个障碍。

现在要求求一个下标，满足这个下标上的障碍数为奇数，保证只有一个这样的位置。

题面中的所有数与下标均为正整数。

思路

由于只有一个有奇数个障碍的位置，所以可以求出障碍数的前缀和数组 $s_i$，表示数轴上下标为 $1\sim i$ 的元素之和。由于偶数 $+$ 偶数 $=$ 偶数，而偶数 $+$ 奇数 $=$ 奇数，所以求出前缀和后，$s$ 一定会以某个下标为分界点，满足这个下标左边的元素都是偶数，并且这个下标对应的元素及它右边所有的元素都是奇数，所以这个下标就是要求的元素。

那么可以用二分求，尽量往左找，找到第一个前缀和为奇数的值，判断并输出。

但是这是一条无限长的数轴，下标最多 $10^9$，那么求前缀和肯定会超时，怎么办呢？

发现 $N \le 2\times10^5$，所以可以定义 $s'(i)=s_i$，每次要用前缀和时就改为 $s'(i)$；而 $s'(i)$ 也很好求，直接遍历所有三元组，加上所有三元组障碍的下标在 $1\sim i$ 之内的值就好了。具体见代码。

时间复杂度 $\mathcal{O}(n \log n)$。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
ll t, s[N], e[N], d[N];

ll sum (int x, int n)
{
	ll res = 0;
	for (int i = 1; i <= n; i ++)
	{
		if (s[i] > x) continue; //当这组障碍物的开头也不在范围内时跳过
		res += min ((x - s[i]) / d[i], (e[i] - s[i]) / d[i]) + 1;
        //由于到最多 e[i] 停止，所以要用 x 和 e[i] 取 min
        //+1是s[i]
	}
	return res;
}

signed main ()
{
    cin >> t;
	while (t --)
	{
		int n; cin >> n;
		for (int i = 1; i <= n; i ++) cin >> s[i] >> e[i] >> d[i];
		ll l = 1, r = (1ll << 31) - 1ll;
		while (l < r) //二分
		{
			ll mid = l + r >> 1ll;
			if (sum (mid, n) & 1) r = mid;
			else l = mid + 1;
		}
		if (l == (1ll << 31) - 1ll) cout << "There's no weakness.\n";
		else cout << l << ' ' << sum (l, n) - sum (l - 1, n) << '\n';
	}
	return 0;
}

---

T4 - 2 最佳牛围栏

link

题面

农夫约翰的农场由 $N$ 块田地组成，每块地里都有一定数量的牛，其数量不会少于 $0$ 头，也不会超过 $2000$ 头。

约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。

围起区域内至少需要包含 $F$ 块地，其中 $F$ 会在输入中给出。

在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。

思路

先思考：给定一个序列 $a$ 和两个数 $x,f$，如何判断 $a$ 的最大“任意长度大于等于 $f$ 的子序列的平均数”是否大于 $x$。

首先发现“任意长度大于等于 $f$ 的子序列的平均数”要枚举所有长度大于等于 $f$ 的子序列，还要求平均值，时间复杂度 $\mathcal{O}(n^2)$，对于本题的序列长度来说不可过。

那么可以求 $a$ 的前缀和 $s$，这样求一个子序列 $a_{[l,r]}$ 的平均值转为 $(s_r-s_{l-1})/(r-l+1)$。

但是要求的是“大于等于 $f$ 的子序列”，所以可以令 $s_i \gets s_i-i\times x$，即将 $a_{1\sim i}$ 的每个减去 $x$ 再求和，这样可以使得求平均值是否 $>x$，转为求和是否 $>0$，那么可以记录 $m=\min\limits_{j=1}^{i-f} s_j$，即当前值“$f$ 个数前的最小前缀和”，用 $\text{res}=\max\limits_{i=f}^n s_i-m$，就可以保证枚举的子序列长度 $\ge f$。

最后二分答案，每次判断该平均值是否能够被原序列满足，判断方法用上面的即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const double eps = 1e-5;
double l, r, prs[N];
int n, f, a[N];

bool check (double ave)
{
	//求1~n中，长度不小于F，平均值最大的连续子序列
	//减去平均值
	for (int i = 1; i <= n; i ++) prs[i] = prs[i - 1] + a[i] - ave;
	double min_ave = 1e9, res = -1; //min_ave为前面sum的最小值 
	for (int i = f; i <= n; i ++)
	{
		min_ave = min (min_ave, (double)prs[i - f]); //保证前面一定有至少F个元素且最小
		res = max (res, prs[i] - min_ave);
	}
	return res >= 0;
}

int main ()
{
    cin >> n >> f;
	for (int i = 1; i <= n; i ++)
		cin >> a[i], r = max (r, (double)a[i]);
	while (r - l > eps)
	{
		double mid = (l + r) / 2;
		if (check (mid)) l = mid;
		else r = mid;
	}
	cout << int (r * 1000);
	return 0;
}

---

T4 - 3 赶牛入圈 ※

link

题面

农夫约翰希望为他的奶牛们建立一个畜栏。

这些挑剔的畜生要求畜栏必须是正方形的，而且至少要包含 $C$ 单位的三叶草，来当做它们的下午茶。

畜栏的边缘必须与 $X,Y$ 轴平行。

约翰的土地里一共包含 $N$ 单位的三叶草，每单位三叶草位于一个 $1\times 1$ 的土地区域内，区域位置由其左下角坐标表示，并且区域左下角的 $(x,y)$ 坐标都为整数，范围在 $1$ 到 $1000$ 以内。

多个单位的三叶草可能会位于同一个 $1\times 1$ 的区域内，因为这个原因，在接下来的输入中，同一个区域坐标可能出现多次。

只有一个区域完全位于修好的畜栏之中，才认为这个区域内的三叶草在畜栏之中。

请你帮约翰计算一下，能包含至少 $C$ 单位面积三叶草的情况下，畜栏的最小边长是多少。

思路

本题的最大难处在于二分的 check，check 最难的是边界问题。

首先可以看出用离散化，将坐标从 $1\sim 10^9$ 改为 $1\sim 10^4$，然后求前缀和；

又因为是求“能包含至少 $C$ 单位的三叶草的最小边长”，那二分畜栏的边长即可。

问题是如何判断一个边长为 $p$ 的正方形能否最多包含至少 $C$ 单位的三叶草？

由于是有前缀和，二维前缀和的公式里有 $x_1,x_2,y_1,y_2$ 这 $4$ 个变量，即正方形的左上角与右下角，那么可以枚举这四个量，并且如果 $x_1(y_1)$ 与 $x_2(y_2)$ 的差 $>p$，那么令 $x_1(y_1)$ 自增，时间复杂度 $\mathcal{O}(n^2)$。

但是又有一个边界问题：由于在边界上的三叶草并不算，所以求前缀和时 $x_1,y_1$ 不用减 $1$，并且在判断 $x_1(y_1)$ 与 $x_2(y_2)$ 的差时，需要将离散化数组里的 $x_1(y_1)$ 加上 $1$ 再判断。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int c, n, prs[N][N];
pair <int, int> ori[N];
vector <int> dcz;

int find (int fe)
{
	int l = 0, r = dcz.size () - 1;
	while (l < r)
	{
		int mid = l + r >> 1;
		if (dcz[mid] >= fe) r = mid;
		else l = mid + 1;
	}
	return l;
}

bool check (int len) //※
{
	for (int x1 = 0, x2 = 1; x2 < dcz.size (); x2 ++)
	{
		while (dcz[x2] - dcz[x1 + 1] + 1 > len) x1 ++;
		for (int y1 = 0, y2 = 1; y2 < dcz.size (); y2 ++)
		{
			while (dcz[y2] - dcz[y1 + 1] + 1 > len) y1 ++;
//			cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n';
			if (prs[x2][y2] - prs[x1][y2] - prs[x2][y1] + prs[x1][y1] >= c) return true;
		}
	}
	return false;
}

int main ()
{
    cin >> c >> n;
	dcz.push_back (0);
	for (int i = 1; i <= n; i ++)
	{
		int x, y; cin >> x >> y;
		ori[i] = {x, y}, dcz.push_back (x), dcz.push_back (y);
	}
	sort (dcz.begin (), dcz.end ());
	dcz.erase (unique (dcz.begin (), dcz.end ()), dcz.end ());
	for (int i = 1; i <= n; i ++)
	{
		int x = find (ori[i].first), y = find (ori[i].second);
		prs[x][y] ++;
	}
	for (int i = 1; i < dcz.size (); i ++)
		for (int j = 1; j < dcz.size (); j ++)
			prs[i][j] += prs[i - 1][j] + prs[i][j - 1] - prs[i - 1][j - 1];
	int l = 1, r = 1e4;
	while (l < r)
	{
		int mid = l + r >> 1;
		if (check (mid)) r = mid;
		else l = mid + 1;
	}
	cout << l;
	return 0;
}

---

0x05. 排序

---

T5 - 1 电影

link

题面

有一个长度为 $n$ 的序列 $a$，每个 $a_i$ 都是一个 $1\sim 10^9$ 的整数，同时又有两个长度为 $m$ 的序列 $b_1,b_2$，每个 $b_{1,i},b_{2,i}$ 也都是一个 $1\sim 10^9$ 的整数，现在定义长度为 $n$ 的序列 $c_{[1,3]}$ 如下：

枚举 $j=1\sim n$，

• 当 $a_j=b_{1,i}$ 时，$c_{1,i}$ 加 $1$。
• 否则，当 $a_j=b_{2,i}$ 时，$c_{2,i}$ 加 $1$。
• 如果都不满足，则 $c_{3,i}$ 加 $1$。

求一个 $i \in [1,m]$，使得 $c_{1,i}$ 最大；若有多个，则选其中 $c_{2,i}$ 最大的那个。

思路

离散化模版，可以将所有 $a_i,b_{1,i},b_{2,i}$ 离散化，因为 $n,m\le 2\times10^5$，所以时间开支减小，然后用桶数组记录离散化后的所有数出现次数，比较即可。

注： 本题中的题面与变量名经过抽象，若想进一步了解，请看原题。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 10;
int n, m, a[N / 3], b[N / 3], c[N / 3], t[N], dcz[N], idx;

int find (int fe)
{
	int l = 1, r = idx;
	while (l < r)
	{
		int mid = l + r >> 1;
		if (dcz[mid] >= fe) r = mid;
		else l = mid + 1;
	}
	return l;
}

int main ()
{
	scanf ("%d", &n);
	for (int i = 1; i <= n; i ++) scanf ("%d", a + i), dcz[++ idx] = a[i];
	scanf ("%d", &m);
	for (int i = 1; i <= m; i ++) scanf ("%d", b + i), dcz[++ idx] = b[i];
	for (int i = 1; i <= m; i ++) scanf ("%d", c + i), dcz[++ idx] = c[i];
	sort (dcz + 1, dcz + 1 + idx);
	idx = unique (dcz + 1, dcz + 1 + idx) - dcz - 1;
	for (int i = 1; i <= n; i ++) t[find (a[i])] ++;
	int mx = 1;
	for (int i = 2; i <= m; i ++)
	{
		if (t[find (b[i])] > t[find (b[mx])] ||
		(t[find (b[i])] == t[find (b[mx])] &&
		t[find (c[i])] > t[find (c[mx])])) mx = i;
	}
	printf ("%d", mx);
	return 0;
}

---

T5 - 2 货仓选址

link

题面

在一条数轴上有 $N$ 家商店，它们的坐标分别为 $A_1,A_2,\dots,A_N$。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

思路

一道非常经典的模版题。根据初中知识，对于数轴上的两个坐标分别为 $a_1,a_2(a_1\le a_2)$ 的点，如果要求取一点 $P$（坐标为 $p$）使得 $P$ 到这两点之间的距离之和最小，那么有两种情况：

1. $a_1 \le p \le a_2$，这种情况下不论如何取，最小值都是 $a_2-a_1$。
2. $p<a_1$ 或 $p>a_2$，这种情况下会发现有额外开支，一定不优，所以一定选择第 1 种。

那么可以由上结论推广至有 $N$ 个点的情况（即本题），发现将货仓建在 $A$ 这个数列的中位数坐标上最优，即：

• 当 $N$ 为奇数时，货仓位于 $A_{N/2+1}$ 处。
• 当 $N$ 为偶数时，货仓可以位于 $A_{N/2}\sim A_{N/2+1}$ 的任意位置，我们约定就取 $A_{N/2}$。

建在中位数上，能使第 $1$ 个与第 $N$ 个配对，第 $2$ 个与第 $N-1$ 个配对……对于每一对，都可以使我们的 $P$ 在这一对的两个点之间，所以路程最短。

那么路程就是 $A$ 的中位数到 $A$ 的所有元素的距离，即 $\sum\limits_{i=1}^{N}\big|A_{\lceil \frac{N}{2} \rceil}-A_i\big|$（记住这个式子，它告诉我们当你有一个序列 $a$ 时如果要你求一个 $k$ 使得 $\sum\limits_{i=1}^{\text{size}(a)}|a_k-a_i|$ 最小，那么很显然 $k$ 应该取 $a$ 中元素的中位数）。

（当然也可以枚举首尾元素，两两相加，即 $\sum\limits_{i=1}^{\lceil \frac{N}{2} \rceil} A_i+A_{N-i+1}$）。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], sum;

int main ()
{
    cin >> n;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	sort (a + 1, a + n + 1);
	int pos = a[n / 2 + (n & 1)];
	for (int i = 1; i <= n; i ++) sum += abs (pos - a[i]);
	cout << sum;
	return 0;
}

---

T5 - 3 七夕祭 ※

link

题面

七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。

于是 TYVJ 今年举办了一次线下七夕祭。

Vani 同学今年成功邀请到了 cl 同学陪他来共度七夕，于是他们决定去 TYVJ 七夕祭游玩。

TYVJ 七夕祭和 11 区的夏祭的形式很像。

矩形的祭典会场由 $N$ 排 $M$ 列共计 $N \times M$ 个摊点组成。

虽然摊点种类繁多，不过 cl 只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。

Vani 预先联系了七夕祭的负责人 zhq，希望能够通过恰当地布置会场，使得各行中 cl 感兴趣的摊点数一样多，并且各列中 cl 感兴趣的摊点数也一样多。

不过 zhq 告诉 Vani，摊点已经随意布置完毕了，如果想满足 cl 的要求，唯一的调整方式就是交换两个相邻的摊点。

两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。

由于 zhq 率领的 TYVJ 开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。

现在 Vani 想知道他的两个要求最多能满足多少个。

在此前提下，至少需要交换多少次摊点。

思路

由于行与列互不影响，所以可以分开处理，下面以行为例。

看到题目想起「均分纸牌」，即让所有行的“喜欢个数”（即 cl 喜欢的摊点个数）相等（先统计出第 $i(i\in[1,n])$ 行原本的“喜欢个数” $a_i$）。

思考：首先发现如果所有的摊点个数 $T$ 并不是 $N$ 的倍数（列就是 $M$），那么当然不可行；否则每行的摊点数就是 $c=T/N$。

然后讨论如何达到最小操作次数：

拿 $a_1$ 举例：

• 当 $a_1<c$ 时，$a_1$ 应从 $a_2$ 处拿 $c-a_1$ 个摊点；
• 当 $a_1>c$ 时，$a_2$ 应从 $a_1$ 处拿 $a_1-c$ 个摊点。

所以第一行的操作次数为 $|c-a_1|$。

而对于第二行，由于我们不知道 $a_2$ 到底是加还是减，所以我们干脆把前两个算做一个，那么现在 $a_1+a_2$ 的目标之和就应该是 $2c$，所以操作数 $|2c-(a_1+a_2)|$。

所以可以预处理 $a$ 的前缀和 $p$，那么总操作数就为 $\sum\limits_{i=1}^n |i\times c - p_i|$。

也可以令 $p_i$ 变为 $p_i-i\times c$（即 $p_i=p_{i-1}+a_i-c$），这样就让所有人的目标变为 $0$，总操作数为 $\sum\limits_{i=1}^n |p_i|$，下面以这个为例。

（即“均分纸牌”问题）。

但是本题中的“纸牌”相当于是一个环，怎么办呢？

环的情况无非就是需要找一个断点 $k$，使得原序列变为 $a_{k+1},a_{k+2},\dots,a_n,a_1,a_2,\dots,a_{k-1},a_k$。

那么从这个新序列的第一项开始（即原序列第 $k$ 项），前缀和 $p$ 变为：

编号（原序列）	前缀和
$k$	$p_k-p_k$
$k+1$	$p_{k+1}-p_k$
$k+2$	$p_{k+2}-p_k$
$1$	$p_1+(p_n-p_{k})$
$2$	$p_2+(p_n-p_{k})$
$k-1$	$p_{k-1}+(p_n-p_{k})$

发现因为最后的目标为 $0$，所以 $p_n=0$，即 $p_x=p_x-p_k$，总次数即为 $\sum\limits_{i=1}^n p_i-p_k$。

那现在问题来了，选哪个 $k$ 能使得 $\sum\limits_{i=1}^n p_i-p_k$ 最小呢？这不就是货仓选址！所以选 $p_k$ 为 $p$ 的中位数。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
ll n, m, t, row[N], col[N];
ll c[N];

ll get_ave (ll n, ll a[])
{
	if (t % n) return -1;
	ll ave = t / n, res = 0;
	for (int i = 2; i <= n; i ++) c[i] = c[i - 1] + a[i] - ave;
	sort (c + 1, c + 1 + n); int pos = n / 2 + (n & 1);
	for (int i = 1; i <= n; i ++) res += abs (c[pos] - c[i]);
	return res;
}

int main ()
{
    cin >> n >> m >> t;
	for (int i = 1; i <= t; i ++)
	{
		ll x, y; cin >> x >> y;
		row[x] ++, col[y] ++;
	}
	ll r = get_ave (n, row), c = get_ave (m, col);
	if (r != -1 && c != -1) cout << "both " << r + c;
	else if (r != -1) cout << "row " << r;
	else if (c != -1) cout << "column " << c;
	else cout << "impossible";
	return 0;
}

---

T5 - 4 动态中位数

link

题面

依次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数。

思路

用两个堆，一个大根一个小根，两个堆在意义上可以理解为大根堆在下，小根堆在上，两个堆的堆顶相对；而我们要做的就是让读入的序列中一半较小的元素位于大根堆中，另一半较大的元素位于小根堆中，并且使大根堆的元素数永远比小根堆多一，这样大根堆的堆顶就是中位数，每次维护即可。

代码

#include <bits/stdc++.h>
using namespace std;
int t;

int main ()
{
	cin >> t;
	while (t --)
	{
		int id, m, cnt = 0; cin >> id >> m;
		cout << id << ' ' << (m + 1) / 2 << '\n';
		priority_queue <int> down; //大根堆
		priority_queue <int, vector <int>, greater <int> > up; //小根堆
		for (int i = 1; i <= m; i ++)
		{
			int x; cin >> x;
			if (down.empty () || down.top () >= x) down.push (x);
			else up.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)
			{
				cnt ++;
				cout << down.top () << ' ';
				if (cnt == 10) cnt = 0, cout << '\n';
			}
		}
		if (cnt) cout << '\n';
	}
	return 0;
}

---

T5 - 5 超快速排序

link

题面

在这个问题中，您必须分析特定的排序算法——超快速排序。

该算法通过交换两个相邻的序列元素来处理 $n$ 个不同整数的序列，直到序列按升序排序。

对于输入序列 9 1 0 5 4，超快速排序生成输出 0 1 4 5 9。

您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。

思路

假设两数 $i,j \ (i<j)$ 作为序列下标，那么如果 $a_i > a_j$，则这两个数最终一定要交换，所以答案就是这样的 $(i,j)$ 对数，而 $a_i>a_j$ 这个形式有点熟悉：就是逆序对。

所以用归并排序求逆序对个数即可。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10;
int n, a[N], t[N], ans;

void merge_sort (int l, int r)
{
	if (l == r) return;
	int mid = l + r >> 1;
	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]) t[k ++] = a[i ++];
		else t[k ++] = a[j ++], ans += mid - i + 1;
	}
	while (i <= mid) t[k ++] = a[i ++];
	while (j <= r) t[k ++] = a[j ++];
	for (int i = 1, j = l; j <= r; i ++, j ++) a[j] = t[i];
}

signed main ()
{
    while (cin >> n && n)
	{
		for (int i = 1; i <= n; i ++) cin >> a[i];
		ans = 0;
		merge_sort (1, n);
		cout << ans << '\n';
	}
	return 0;
}

---

T5 - 6 奇数码问题

link

题面

你一定玩过八数码游戏，它实际上是在一个 $3\times3$ 的网格中进行的，$1$ 个空格和 $1\sim 8$ 这 $8$ 个数字恰好不重不漏地分布在这 $3\times 3$ 的网格中。

例如：

5 2 8
1 3 _
4 6 7

在游戏过程中，可以把空格与其上、下、左、右四个方向之一的数字交换（如果存在）。

例如在上例中，空格可与左、上、下面的数字交换，分别变成：

5 2 8       5 2 _      5 2 8
1 _ 3       1 3 8      1 3 7
4 6 7       4 6 7      4 6 _

奇数码游戏是它的一个扩展，在一个 $n\times n$ 的网格中进行，其中 $n$ 为奇数，$1$ 个空格和 $1\sim n^2-1$ 这 $n^2-1$ 个数恰好不重不漏地分布在 $n\times n$ 的网格中。

空格移动的规则与八数码游戏相同，实际上，八数码就是一个 $n=3$ 的奇数码游戏。

现在给定两个奇数码游戏的局面，请判断是否存在一种移动空格的方式，使得其中一个局面可以变化到另一个局面。

思路

这题吧……先直接说结论：将一个局面的非空格数依次塞进一个数组（另一个也照办），统计两个数组的逆序对个数，若两个逆序对个数奇偶性相同，则可达，否则不可达。

证明非常详细，想看自己去查。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2.5e5 + 10;
int n, f[N], t[N], idx;
long long cnt[3];

void invpar (int l, int r, int md) //求逆序对数
{
	if (l == r) return;
	int mid = l + r >> 1;
	invpar (l, mid, md), invpar (mid + 1, r, md);
	int i = l, j = mid + 1, k = 0;
	while (i <= mid && j <= r)
	{
		if (f[i] <= f[j]) t[++ k] = f[i ++];
		else t[++ k] = f[j ++], cnt[md] += mid - i + 1;
	}
	while (i <= mid) t[++ k] = f[i ++];
	while (j <= r) t[++ k] = f[j ++];
	for (int i = 1, j = l; j <= r; j ++, i ++) f[j] = t[i];
}

int main ()
{
	while (cin >> n)
	{
		if (n == 1)
		{
			int x; cin >> x >> x;
			cout << "TAK\n";
		}
		cnt[0] = cnt[1] = idx = 0;
		for (int i = 1; i <= n * n; i ++)
		{
			int x; cin >> x;
			if (x) f[++ idx] = x;
		}
		invpar (1, idx, 0), idx = 0;
		for (int i = 1; i <= n * n; i ++)
		{
			int x; cin >> x;
			if (x) f[++ idx] = x;
		}
		invpar (1, idx, 1);
		if (cnt[0] % 2 == cnt[1] % 2) cout << "TAK\n";
		else cout << "NIE\n";
	}
	return 0;
}

---

T5 - 7 糖果传递

link

题面

有 $n$ 个小朋友坐成一圈，第 $i$ 人有 $a_i$ 个糖果。

每人只能给左右两人传递糖果。

每人每次传递一个糖果代价为 $i$。

求使所有人获得均等糖果的最小代价。

思路

就是只算一遍的「七夕祭」，思路已讲。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
ll a[N], prs[N], c[N], res;
int n;

int main ()
{
    cin >> n;
	for (int i = 1; i <= n; i ++) cin >> a[i], prs[i] = prs[i - 1] + a[i];
	ll ave = prs[n] / n;
	for (int i = 2; i <= n; i ++) c[i] = c[i - 1] + a[i] - ave;
	sort (c + 1, c + 1 + n);
	for (int i = 1; i <= n / 2; i ++) res += c[n - i + 1] - c[i];
	cout << res;
	return 0;
}

---

T5 - 8 士兵

link

题面

格格兰郡的 $N$ 名士兵随机散落在全郡各地。

格格兰郡中的位置由一对 $(x,y)$ 整数坐标表示。

士兵可以进行移动，每次移动，一名士兵可以向上，向下，向左或向右移动一个单位（因此，他的 $x$ 或 $y$ 坐标也将加 $1$ 或减 $1$），第 $i$ 个士兵的坐标为 $(x_i,y_i)$。

现在希望通过移动士兵，使得所有士兵彼此相邻的处于同一条水平线内，即所有士兵的 $y$ 坐标相同并且 $x$ 坐标相邻。

请你计算满足要求的情况下，所有士兵的总移动次数最少是多少。

需注意，两个或多个士兵不能占据同一个位置。

思路

由于 $x$ 与 $y$ 互不干扰，所以分开处理。

首先我们发现 $y$ 坐标都要以某个士兵为基准，所以就是「货仓选址」。

而 $x$ 坐标呢？首先按 $x_i$ 从小到大排序，那么设排序后 $x_1$ 位于位置 $a$，则 $x_2=a+1,x_3=a+2,\dots,x_n=a+n-1$。

那么将设 $x'_i \ (i \in[1,n])$ 为 $x_i-(i-1)$，则变化后 $x'_1=a,x'_2=a,\dots,x'_n=a$，则操作次数为 $\sum\limits_{i=1}^n |a-x'_i|$，那么要求 $a$ 的话，不还是「货仓选址」吗？

那么问题得解。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n, x[N], y[N];
long long ans;

int main ()
{
    cin >> n;
	for (int i = 1; i <= n; i ++) cin >> x[i] >> y[i];
	sort (x + 1, x + n + 1);
	for (int i = 1; i <= n; i ++) x[i] -= i - 1;
	sort (x + 1, x + n + 1);
	int pos = x[n / 2 + 1];
	if ((n + 1) & 1) pos = (pos + x[n / 2]) / 2;
	for (int i = 1; i <= n; i ++) ans += abs (pos - x[i]);
	sort (y + 1, y + n + 1);
	for (int i = 1; i <= n; i ++) ans += abs (y[n / 2 + (n & 1)] - y[i]);
	cout << ans;
	return 0;
}

---

0x06. 倍增

---

T6 - 1 Genius ACM

link

题面

每天，CPU 公司 ACM 生产 $n$ 台 CPU 并销售到世界各地。

ACM 公司的质检部门会对生产出的 CPU 进行成组测试，对一组（若干个）CPU 进行测试的方法如下：

1. 随机从该组 CPU 中选取 $m$ 对（即 $2m$ 台），若总数不足 $2m$ 台，则选取尽量多对。

2. 对于每一对 CPU，测量它们之间的 Relative Performance Difference (RPD)，并把第 $i$ 对的 RPD 记为 $D_i$。RPD 的计算方法在后面给出。

3. 该组 CPU 的 Sqared Performance Difference (SPD） 由以下公式给出：$\text{SPD}=\sum\limits_{i=1}^m (D_i)^2$。

4. 该组 CPU 通过质检，当且仅当 $\text{SPD}\le k$，其中 $k$ 是给定常数。

ACM 公司生产的 CPU 性能很好，而质检部门制定的标准更是过于严格。通常他们把 $n$ 台 CPU 作为一整组进行测试，这导致一些性能良好的 CPU 无法通过测试，生产部门对此颇有微词。作为质检部门的领导，小 S 在不更改质检测试流程的前提下，想出了这样一个主意：如果能够把 $n$ 台 CPU 恰当地分成连续的若干段，使得每段 CPU 都能够通过成组测试，就可以解决当下的问题。

现在，小 S 已经知道了 $n$ 台各自的性能表现 $P_1,P_2,\dots,P_n$，两台 CPU 的 RPD 被定义为它们性能表现的差的绝对值。请你帮忙计算一下，至少把这些 CPU 分成多少段，才能使得每一段都能通过成组测试。

思路

Part 1. 贪心

第一眼我们知道测试用的 CPU 既然是随机抽，那么我们要使得最大的 SPD 都不超过 $k$，SPD 的最大值当然不能枚举，所以考虑贪心策略。

设有四数 $a,b,c,d$，且它们满足 $a<b<c<d$。

则有两种取数方式：

• $a$ 与 $d$ 一组，剩下的另一组。
• $a$ 与 $c$ 一组，剩下的另一组。

则第一种方式的 SPD 为 $(d-a)^2+(c-b)^2$，第二种方式的 SPD 为 $(c-a)^2+(d-b)^2$。

两式相减，得：

$$\begin{aligned} (d-a)^2+(c-b)^2-(c-a)^2-(d-b)^2 &= (d-a)(d-a)+(c-b)(c-b)-(c-a)(c-a)-(d-b)(d-b) \\ &=(d^2-2ad-a^2)+(c^2-2bc-b^2)-(c^2-2ac-a^2)-(d^2-2bd-b^2) \\ &=2ac+2bd-2ad-2bc \\ &=2(d-c)(b-a) \end{aligned}$$

由于 $d>c,b>a$，所以 $d-c$ 和 $b-a$ 均大于 $0$。

即我们要使题目中最大的 $D_i$ 与最小的 $D_i$ 配对，使第二大的 $D_i$ 与第二小的 $D_i$ 配对，以此类推。

Part 2. 倍增

根据题目数据，肯定是不能二分的，因为最坏情况下需要进行 $n$ 次二分，会使时间复杂度变为 $\mathcal{O}(n^2 \log^2 n)$。

那么可以用倍增平替掉。朴素思想就是倍增模版，用变量 $\text{stt}$ 记录当前的位置，$\text{add}$ 记录平移的元素数，当排序后求出来的 SPD 小于等于 $k$ 时 并将 $\text{add}$ 乘上 $2$，否则 $\text{add}$ 除以 $2$，注意一般采用左闭右开区间。

时间复杂度 $\mathcal{O}(n \log^2n)$。

Part 3. 归并思想优化

归并立大功。

发现在求 SPD 的函数中，每次都要将当前数组排一遍序，时间开销较大，所以考虑使用归并排序的思想。

增加一个变量 $\text{end}$ 记录上次结束时的位置作为中心点，我们既然在上次倍增时已经对 $[\text{stt},\text{end})$ 这个区间排了序，那么这次只要排序 $[\text{end},\text{end}+\text{add})$，并用归并排序的思想将这两个数组合并再求 SPD 即可。

记得在符合条件后更新用来排序的数组并且不管怎样都要更新 $\text{stt}$ 为 $\text{end}$。

时间复杂度 $\mathcal{O}(n \log n)$，可以通过。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10;
int n, m, k, t, p[N], m1[N], m2[N];

int RPD (int a, int b) { return a - b; }

void pArr (int p[], int f, int t)
{
	for (int i = f; i < t; i ++) cout << p[i] << ' ';
	cout << '\n';
}

bool check (int s, int mid, int e)
{
	for (int i = mid; i < e; i ++) m1[i] = p[i];
	sort (m1 + mid, m1 + e);
	
	int lp = s, rp = mid, idx = 0, res = 0;
	while (lp < mid && rp < e)
	{
		if (m1[lp] <= m1[rp]) m2[idx ++] = m1[lp ++];
		else m2[idx ++] = m1[rp ++];
	}
	while (lp < mid) m2[idx ++] = m1[lp ++];
	while (rp < e) m2[idx ++] = m1[rp ++];
	
	for (int i = 0; i < m && i < idx; i ++, idx --)
		res += pow (RPD (m2[i], m2[idx - 1]), 2);
	return res <= k;
}

signed main ()
{
    scanf ("%lld", &t);
	while (t --)
	{
		scanf ("%lld%lld%lld", &n, &m, &k);
		for (int i = 0; i < n; i ++) scanf ("%lld", p + i);
		int stt = 0, end = 0, cnt = 0;
		while (end < n)
		{
			int add = 1;
			while (add > 0)
			{
				if (end + add <= n && check (stt, end, end + add))
				{
					end += add, add <<= 1;
					if (end >= n) break;
					for (int i = stt; i < end + add; i ++)
						m1[i] = m2[i - stt];
				}
				else add >>= 1;
			}
			cnt ++, stt = end;
		}
		printf ("%lld\n", cnt);
	}
	return 0;
}

---

0x07. 贪心

---

T7 - 1 股票买卖 II

link

题面

给定一个长度为 $n$ 的数组，数组中的第 $i$ 个数字表示一个给定股票在第 $i$ 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路

由于我们可以在最便宜的时候买一支股票，而在最贵的时候卖出，所以可以将原数组分成若干个最长不降子序列（连续），取每个序列的尾项减去首项加进答案中，这样一定最优。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], lst, stt, ans;

/*
将数组分为若干个最长不降连续子序列，取每个序列的(结尾值-开头值)之和作为答案
*/

int main ()
{
    cin >> n;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	stt = 1;
	for (int i = 2; i <= n + 1; i ++)
		if (a[i] < a[i - 1]) ans += a[i - 1] - a[stt], stt = i;
	cout << ans;
	return 0;
}

---

T7 - 2 防晒

link

题面

有 $C$ 头奶牛进行日光浴，第 $i$ 头奶牛需要 $\text{minSPF}_i$ 到 $\text{maxSPF}_i$ 单位强度之间的阳光。

每头奶牛在日光浴前必须涂防晒霜，防晒霜有 $L$ 种，涂上第 $i$ 种之后，身体接收到的阳光强度就会稳定为 $\text{SPF}_i$，第 $i$ 种防晒霜有 $\text{cover}_i$ 瓶。

求最多可以满足多少头奶牛进行日光浴。

思路

贪心策略：将奶牛按下限（即 $\text{minSPF}_i$）排序，同时将防晒霜按 $\text{SPF}_i$ 排序，使得下限较高的牛可以用阳光强度较高的防晒霜，这样的话：

• 如果后面下限较低的牛能用阳光强度较低的，就用。如果按相反的贪心策略，则下限较低的可能可以用阳光强度较高的，而下限较高的可能用不了阳光强度较低的，一定不优。
• 否则哪怕用了相反的贪心策略，也只能满足一头牛，与此贪心策略相同。

所以该贪心策略正确。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2.5e3 + 10, INF = 0x3f3f3f3f;
int c, l, cnt;
struct sr1 { int mins, maxs; }; sr1 cow[N];
struct sr2 { int SPF, cvr; }; sr2 ssc[N];

bool ccmp (sr1 a, sr1 b) { return (a.mins == b.mins) ? (a.maxs > b.maxs) : (a.mins > b.mins); }
bool scmp (sr2 a, sr2 b) { return a.SPF > b.SPF; }

int main ()
{
    cin >> c >> l;
	for (int i = 1; i <= c; i ++) cin >> cow[i].mins >> cow[i].maxs;
	for (int i = 1; i <= l; i ++) cin >> ssc[i].SPF >> ssc[i].cvr;
	sort (cow + 1, cow + 1 + c, ccmp), sort (ssc + 1, ssc + 1 + l, scmp);
	for (int i = 1; i <= c; i ++)
	{
		int wre = INF;
		for (int j = 1; j <= l; j ++)
		{
			if (ssc[j].SPF >= cow[i].mins && ssc[j].SPF <= cow[i].maxs && ssc[j].cvr)
			{ wre = j; break; }
		}
		if (wre == INF) continue;
		else ssc[wre].cvr --, cnt ++;
	}
	cout << cnt;
	return 0;
}

---

T7 - 3 畜栏预定

link

题面

有 $N$ 头牛在畜栏中吃草。

每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。

给定 $N$ 头牛和每头牛开始吃草的时间（第 $i$ 头为 $A_i$）以及结束吃草的时间（第 $i$ 头为 $B_i$），每头牛在 $[A,B]$ 这一时间段内都会一直吃草。

当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。

求需要的最小畜栏数目和每头牛对应的畜栏方案。

思路

思路非常简单，就是将所有牛按吃草的开始时间排序，并用一个堆记录已经分配畜栏的牛中结束时间最早的牛与其对应的畜栏编号，若当前牛的开始时间严格大于堆顶牛的结束时间，则弹出堆顶并压入当前牛；否则新建畜栏并压入。

贪心正确性证明：

• 当当前牛能压入最早的畜栏时，哪怕后面有结束时间更早且符合条件的牛，也要将其压进去，因为除非后面的牛的结束时间都比当前牛的开始时间早，否则后面的牛和当前的牛之间只能放一头进去，而由于我们已经按开始时间排了序，所以不会有这个问题。
• 否则，当然没有问题。

代码

#include <bits/stdc++.h>
#define s first
#define e second
using namespace std;
typedef pair <int, int> PII;
const int N = 5e4 + 10;
priority_queue <PII, vector <PII>, greater <PII> > sq; //结束时间&编号
int n, cnt, t[N];

struct P { int s, e, id, ans; }; P cow[N];

bool cmp (P a, P b) { return a.s < b.s; }
bool cmp2 (P a, P b) { return a.id < b.id; }

int main ()
{
    cin >> n;
	for (int i = 1; i <= n; i ++)
		cin >> cow[i].s >> cow[i].e, cow[i].id = i;
	sort (cow + 1, cow + 1 + n, cmp);
	sq.push ({cow[1].e, ++ cnt}), cow[1].ans = 1;
	for (int i = 2; i <= n; i ++)
	{
		auto now = sq.top ();
		if (cow[i].s <= now.s) sq.push ({cow[i].e, ++ cnt}), cow[i].ans = cnt;
		else sq.pop (), sq.push ({cow[i].e, now.e}), cow[i].ans = now.e;
	}
	cout << cnt;
	sort (cow + 1, cow + 1 + n, cmp2);
	for (int i = 1; i <= n; i ++) cout << '\n' << cow[i].ans;
	return 0;
}

---

T7 - 4 雷达设备

link

题面

假设海岸是一条无限长的直线，陆地位于海岸的一侧，海洋位于另外一侧。

每个小岛都位于海洋一侧的某个点上。

雷达装置均位于海岸线上，且雷达的监测范围为 $d$，当小岛与某雷达的距离不超过 $d$ 时，该小岛可以被雷达覆盖。

我们使用笛卡尔坐标系，定义海岸线为 $x$ 轴，海的一侧在 $x$ 轴上方，陆地一侧在 $x$ 轴下方。

现在给出每个小岛的具体坐标以及雷达的检测范围，请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目。

思路

首先如果有一个小岛的 $y$ 坐标超过了 $d$，

首先我们可以预处理在 $[l_i,r_i]$ 范围内放雷达就能检测到第 $i$ 个雷达，我们就是要求出 $l_i,r_i$。可以用欧几里得距离：

其中的 $\text{len}$ 就等于 $\sqrt{d^2+(y_i)^2}$。

所以 $l_i=x_i-\text{len},r_i=x_i+\text{len}$。

那么可以将所有小岛按可以检测的 $r_i$（右端点）排序，同时用一个 $\text{last}$ 记录上一个安放的雷达的位置，那么当遍历到一个小岛使得 $l_i>\text{last}$ 说明这个小岛不能被上一个雷达覆盖，所以新建一个雷达并将 $\text{last}$ 设为 $r_i$（这样既能覆盖当前小岛，又能尽量覆盖后面的小岛，一定不劣）。

代码

#include <bits/stdc++.h>
#define rt first
#define lf second
using namespace std;
typedef double db;
const db eps = 1e-6;
const int N = 1e3 + 10;
pair <db, db> a[N];
db last = -1e9; //上一个雷达的最大位置
int n, d, cnt;

int main ()
{
    cin >> n >> d;
	for (int i = 1; i <= n; i ++)
	{
		int x, y; cin >> x >> y;
		if (y > d) { cout << "-1"; return 0; } //不能达到最大能检测的范围
		db len = sqrt (d * d - y * y); //左右距离最大限制
		a[i] = {x + len, x - len}; //x + len是右区间
	}
	sort (a + 1, a + 1 + n); //按右区间排序
	for (int i = 1; i <= n; i ++)
		if (a[i].lf > last) cnt ++, last = a[i].rt; //不能达到从上一个雷达的最大右端点
	cout << cnt;
	return 0;
}

---