2021“MINIEYE杯”中国大学生算法设计超级联赛(6) 杭电多校6 题解
sdxjzsq
2021-08-06 11:16:50
## 目录
| 题号 | 题目 | 知识点 | 完成度 |
| ---- | ------------------------------------------------------------ | -------- | ------ |
| 1001 | HDU7025 [Yes, Prime Minister](https://acm.hdu.edu.cn/showproblem.php?pid=7025) | 线性筛，质数性质| √ |
| 1005 | HDU7029 [Median](https://acm.hdu.edu.cn/showproblem.php?pid=7029) | 思维 | √ |
| 1004 | HDU7028 [Decomposition](https://acm.hdu.edu.cn/showproblem.php?pid=7028) | - | - |
| 1008 | HDU7032 [Command and Conquer: Red Alert 2](https://acm.hdu.edu.cn/showproblem.php?pid=7032) | 计算几何 | √ |
| 1007 | HDU7031 [Power Station of Art](https://acm.hdu.edu.cn/showproblem.php?pid=7031) | - | - |
| 1003 | HDU7027 [0 tree](https://acm.hdu.edu.cn/showproblem.php?pid=7027) | - | - |
## 1001 HDU7025 [Yes, Prime Minister](https://acm.hdu.edu.cn/showproblem.php?pid=7025)
### 题意
寻找一个区间 $[l,r]$ ，满足 $x$ 在区间中，且 $\sum_{i=l}^{r}$ 是一个质数。
### 思路
经过分析发现，当 $l,r$ 均大于 $0$ 时，区间的长度不超过 $2$ ，可以证明所有长度超过 $2$ 的区间和一定不是质数，下面做出证明：
- 当区间长度为奇数时，
$$
\sum_{i=l}^{r} = {(l+r)\times(r-l+1)\over 2} = {(l+r)\over 2}\times(r-l+1)
$$
被 $(r-l+1)$ 也就是区间长度整除。
- 当区间长度为偶数时，
$$
\sum_{i=l}^{r} = {(l+r)\times(r-l+1)\over 2} = {(r-l+1)\over 2}\times(l+r)
$$
被 $(r-l+1)/2$ 或者 $(l+r)$ 整除。
综上，在区间长度大于 $2$ ，且 $l,r$ 都大于 $0$ 的情况下区间和一定不是质数，于是我们只要判断一下 $[x,x],[(x-1),x],[x,(x+1)]$ 这三个区间即可。
但是当有负数的情况下呢？首先如果 $x$ 为负数，那么区间长度至少为 $2(-x)+2$，也就是先从 $x$ 到 $-x$ 使得和大于 $0$ ，然后再加数。
那么会不会有无解的情况呢？理论上说是没有的，因为即使 $x$ 为正，我们依然可以通过 $[-x,x]$ 获得 $0$ ，然后再去对 $x+1$ 检查 $[x+1,x+2],[x+1,x+1]$ 这两个区间，不行的话就再加上 $\pm(x+1)$ 继续往后检查，一定能找到一个解。
根据质数分布，其实很快就可以找到解，最多 $\log x$ 次。
### code
``` cpp
#include <cmath>
#include <cstdio>
using namespace std;
int t;
long long n;
const int maxp = 10000001;
int pr[maxp], prime[maxp], top = 0;
int check(long long x)
{
if (x > 10000000)
{
for (int i = 1; 1ll * prime[i] * prime[i] <= x; ++i)
if (x % prime[i] == 0) return 0;
return 1;
}
return !pr[x];
}
inline void getPrime(int maxprime)
{
pr[1] = 1;
for (int i = 2; i <= maxprime; i++)
{
if (!pr[i]) prime[++top] = i;
for (int j = 1; j <= top && i * prime[j] <= maxprime; j++)
{
pr[i * prime[j]] = 1;
if (!(i % prime[j])) break;
}
}
}
int main()
{
getPrime(10000000);
for (scanf("%d", &t); t--;)
{
scanf("%lld", &n);
long long ans = 0;
int flag = 1;
if (n <= 0) flag = 0, ans = (-n * 2) + 1, n = -n + 1;
if (check(n))
ans += 1;
else if (check(2 * n + 1))
ans += 2;
else if (flag && check(n * 2 - 1))
ans += 2;
else
{
if (flag)
ans += n * 2 + 1, ++n;
else
ans += 2, ++n;
int orz = 1;
while (orz)
{
if (check(n))
ans += 1, orz = 0;
else if (check(n * 2 + 1))
ans += 2, orz = 0;
else
ans += 2, ++n;
}
}
printf("%lld\n", ans);
}
return 0;
}
```
## 1005 HDU7029 [Median](https://acm.hdu.edu.cn/showproblem.php?pid=7029)
### 题意
求解是否能将 $1,2,\cdots ,n$ 分成 $m$ 个区间，使得每个区间的中位数为 $x$ 。
### 思路
首先，肯定是把 $m$ 个数
### code
```cpp
```
## 1004 HDU7028 [Decomposition](https://acm.hdu.edu.cn/showproblem.php?pid=7028)
待补
## 1008 [Command and Conquer: Red Alert 2](https://acm.hdu.edu.cn/showproblem.php?pid=7032)
### 题意
已知三维坐标系下有 $n$ 个点，代表 $n$ 个敌方士兵，我方狙击手的狙击范围是 $k$ （指能够狙击到坐标满足 $max(|x_s−x_e|,|y_s−y_e|,|z_s−z_e|)\le k$ ），现在我方狙击手在 $(-10^{100},-10^{100},-10^{100})$ 的位置出发，每步只能向 $x,y,z$ 轴正方向中的一个方向移动一格，求能够狙击掉所有敌方士兵的最小的 $k$ 。
### 思路
首先进行一个题面的转化：我们发现狙击范围其实就是以狙击手为中心点、边长为 $2k$ 的正方体，那么我们不妨将狙击手的位置移动到正方体的角上，变成狙击手能够狙击到坐标满足 $max(x_e−x_s,y_e−y_s,z_e−z_s)\le 2k$ 的敌方士兵，转化之后问题便简单了一些。
现在我们考虑，狙击手每移动一步，都代表着在某个方向上的一层敌人都无法被狙击到（比如从 $x_0$ 移动到 $x_0+1$ ，满足 $x=x_0$ 的所有敌人都无法被狙击到了，所以必须提前消灭）
于是我们可以开三个优先队列（ $set$ 也可以）分别对每个坐标排序，于是我们就会发现，如果想要移动一格，要提前让准备移动的坐标上的所有点都被消灭。
但是根据坐标处理，范围是 $1e9$ 的，于是我们转化为对于点处理，即每次通过扩大 $k$ 使得能够将某个点消灭，当发现某个坐标上的点全部被消灭时，将坐标移动到下一个有点的位置。
进一步分析发现，狙击手的位置是不需要每次记录的（也不好维护），只要分别设置为敌人对应坐标的最小值即可。
到现在，我们得到了最终的思路：
贪心不断扩大 $k$ 来删掉下一个待删掉的点，每次将狙击手位置置于三个坐标分别的最小值的位置，一直这样做下去直到删掉所有点，最终答案为 $\lceil {ans\over 2}\rceil$。
### code
```cpp
#include <algorithm>
#include <cstdio>
#include <map>
#include <queue>
using namespace std;
const int maxn = 5e5 + 7;
int t, n, tot, ans;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q[3];
int p[maxn][4];
int main()
{
for (scanf("%d", &t); t--;)
{
for (int i = 0; i < 3; ++i)
while (Q[i].size()) Q[i].pop();
int o[3];
ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j < 3; ++j)
scanf("%d", &p[i][j]), Q[j].push({p[i][j], i}), o[j] = min(o[j], p[i][j]);
p[i][3] = 1;
}
while (Q[0].size())
{
int tmp[4] = {0, 0, 0, (int)3e9};
for (int i = 0; i < 3; ++i)
{
while (Q[i].size() && p[Q[i].top().second][3] == 0) Q[i].pop();
if (Q[i].size()) o[i] = Q[i].top().first;
}
if (!Q[0].size()) break;
for (int i = 0; i < 3; ++i)
{
int no = Q[i].top().second;
tmp[i] = max(p[no][(i + 1) % 3] - o[(i + 1) % 3], p[no][(i + 2) % 3] - o[(i + 2) % 3]);
tmp[3] = min(tmp[3], tmp[i]);
}
ans = max(ans, tmp[3]);
for (int i = 0; i < 3; ++i)
if (tmp[3] == tmp[i])
p[Q[i].top().second][3] = 0, Q[i].pop();
}
printf("%d\n", (ans + 1) >> 1);
}
}
```