2021“MINIEYE杯”中国大学生算法设计超级联赛(6) 杭电多校6 题解

2021-08-06 11:16:50


目录

题号 题目 知识点 完成度
1001 HDU7025 Yes, Prime Minister 线性筛,质数性质
1005 HDU7029 Median 思维
1004 HDU7028 Decomposition - -
1008 HDU7032 Command and Conquer: Red Alert 2 计算几何
1007 HDU7031 Power Station of Art - -
1003 HDU7027 0 tree - -

1001 HDU7025 Yes, Prime Minister

题意

寻找一个区间 $[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

#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

题意

求解是否能将 $1,2,\cdots ,n$ 分成 $m$ 个区间,使得每个区间的中位数为 $x$ 。

思路

首先,肯定是把 $m$ 个数

code

1004 HDU7028 Decomposition

待补

1008 Command and Conquer: Red Alert 2

题意

已知三维坐标系下有 $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

#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);
    }
}