2024牛客寒假算法基础集训营5

A mutsumi 的质数合数

数组中质数和合数共有几个。

void solve() {
    int cnt = n;
    for (int i = 0;i < n;i++) {
        if (a[i] == 1)cnt--;
    }
    cout << cnt << '\n';
}

L anon 的星星

anon 在玩一个游戏，她胜利一局会获得一颗星星，失败一局会失去一颗星星，没有平局。

anon 忘记了自己胜利和失败的局数，只记得自己玩了 $n$ 局游戏，共获得了 $x$ 颗星星。

anon 想知道她胜利了几局，失败了几局？

假设赢了 $a$ 局, 输了 $b$ 局，则：

$a-b=x$
$a+b=n$

$\to a=\frac{n+x}{2},b=\frac{n-x}{2}$

void solve() {
    int n, x;cin >> n >> x;
    if ((n + x) % 2 == 0 && (n - x) % 2 == 0)
        cout << (n + x) / 2 << " " << (n - x) / 2 << '\n';
    else cout << -1 << '\n';
}

I rikki 的最短路

rikki 在数轴上的坐标为 0，T 在数轴上的坐标为 $t$，A 在数轴上的坐标为 $a$。初始时 rikki 只知道 T 的坐标，而不知道 A 的坐标，因此 rikki 会先前往 T 的坐标。而当 rikki 到达 T 的坐标时，就可以知道 A 的坐标。

rikki 的视野为 k，若 rikki 当前坐标为 u，则她可以看到 [u-k, u+k] 区间内的东西，即 rikki 可能可以在移动到 T 所在坐标的过程中直接看到 A，去找到 A，省略先去找 T 的过程。

rikki 想知道她将 A 带回 T 的坐标最少需要移动多少距离。

分类讨论

void solve() {
    int t, a, k;cin >> t >> a >> k;
    int ans = 0;
    if (abs(t) >= abs(a)) {
        if (abs(k) >= abs(a)) {
            if (t * a >= 0) {
                ans = abs(t);
            } else {
                ans = abs(t - 2 * a);
            }
        } else {
            if (t * a >= 0) {
                ans = abs(t);
            } else {
                ans = abs(3 * t - 2 * a);
            }
        }
    } else {
        if (abs(k) >= abs(a)) {
            ans = abs(a) + abs(a - t);
        } else {
            if (t * a >= 0) {
                ans = abs(a) + abs(a - t);
            } else {
                ans = abs(3 * t - 2 * a);
            }
        }
    }
    cout << ans << '\n';
}

C anon 的私货

anon 可以在一个全是正数的数组中夹带一些 0，要求所有连续子数组中(全部为 0 的除外)平均数 $\ge 1$

求最多可以夹带多少个 0。

贪心

void solve() {
    int n;cin >> n;vector<int> a(n + 1), num(n + 1);for (int i = 1;i <= n;i++)cin >> a[i];

    int ans = a[1] - 1;
    a[1] = 1;
    for (int i = 2;i <= n;i++) {
        ans += min(a[i], a[i - 1]) - 1;
        a[i] -= min(a[i], a[i - 1]) - 1;
    }
    ans += a[n] - 1;
    cout << ans << '\n';
}

M mutsumi 的排列连通

给出两个长度为 $n$ 的排列

mutsumi 想删除尽可能少的数字，使得矩形至少被分成两个连通块（不一定是矩形），请输出最小的删除次数。若无法通过删除使得矩形被分成至少两个连通块，则输出 -1。

Solution

最多删除 2 个数字，因为直接找到一个下标 $i(i\ne 1,n)$ 必然有两个数字 $a_i,b_i$，如果 $a_i=b_i$，则删除一个数字即可，若 $a_i\ne b_i$，在这两个排列中删除 $a_i,b_i$ 也一定可以达到要求

先对 $n=1,2$ 特判：$n=1:-1$，$n=2:$ 两个排列相等则 $-1$ 否则 $1$

对于更加一般的情况：
$n=0:$ 如果这时 $a_i,b_i$ 的下标 $i\ne 1,n$,则 $1$
$n=1:$ 这时一定是 $1$
其他：输出 $2$

void solve() {
    int n;cin >> n;map<int, int> a, b;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;
        a[x] = i;
    }
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;
        b[x] = i;
    }
    if (n == 1) {
        cout << "-1\n";return;
    }
    if (n == 2) {
        if (a[1] == b[1]) {
            cout << "-1\n";return;
        } else {
            cout << "1\n";return;
        }
    }
    for (int i = 1;i <= n;i++) {
        int m = abs(a[i] - b[i]);
        if (m == 0 && a[i] != 1 && a[i] != n) {
            cout << "1\n";return;
        }
        if (m == 1) {
            cout << "1\n";return;
        }
    }
    cout << "2\n";
}

G/H sakiko 的排列构造

sakiko 想要构造一个长度为 $n$ 的排列 $p$，使得每一个 $p_i+i(1\le i\le n)(1\le n\le {10}^6)$ 都是质数。

Solution

网络流/找规律

发现：如果 $n=4:$ $p:4,3,2,1$,则 $p_i+i$ 是 $5,5,5,5$ 每一项都是 $n+1$

对于 $n$ ，若 $\text{isPrime(n+1)}$,则 $p:\{n,n-1,\dots ,2,1\}$ $p_i+i:\{n+1(n)\}$

若对于 $n$，如果 $\text{isPrime(n+2)}$,则 $p:\{1,n,n-1,\dots ,3,2\}$ $p_i+i:\{2,n+2(n-1)\}$

发现：如果 $n=8:$ $11-3=8$ $p:\{2,1,8,7,6,5,4,3\}$ $p_i+i=\{3,3,11(6)\}$

如果 $n=7:11-(5-1)=7p:\{1,3,2,7,6,5,4\}$ $p_i+i:\{2,5,5,11(4)\}$

对于偶数 $n:$ $(n+m)-(m)=n$ 若能保证 $(n+m)(m)$ 均为质数，则能构造出 $p:\{m-1,m-2,\dots 1,n,n-1,\dots ,m\}$ $p_i+i:\{m(m-1),(n+m)(n-m+1)\}$

对于奇数 $n:$ $(n+m)-(m-1)=n$ 若能保证 $(n+m)(m)$ 均为质数，则能构造出 $p:\{1,m-2,m-3,\dots ,2,n,n-1,\dots n-m+1\}$ $p_i+i:\{2,(m)(m-2),(n+m)(n-m+1)\}$

void solve() {
    int n;cin >> n;
    auto check = [&](int x) {
        for (int i = 2;i * i <= x;i++)
            if (x % i == 0)
                return 0;
        return 1;
    };
    int a = 1;
    if (n % 2) {
        cout << "1 ";a++;
    }
    for (int i = a;i <= n;i++) {
        if (check(i + a) && check(i + 1 + n)) {
            for (int j = i;j >= a;j--)
                cout << j << " ";
            for (int j = n;j > i;j--)
                cout << j << " ";
            cout << '\n';
            return;
        }
    }
    for (int i = n;i >= 1;i--)cout << i << " \n"[i == 1];
}

E/Fsoyorin 的数组操作

给定一个长度为 $n(1\le n\le {10}^6)$ 的数组 $a(1\le a_i\le {10}^{12})$,每次可以选择一个不超过 $n$ 的偶数 $k$，使得 $a_i=a_i+i(1\le i\le k)$

问是否可以通过任意次操作使得数组非降序。若能，输出最小次数，不能输出 -1

Solution

在有解的情况下答案是 $max(\text{a[i]-a[i+1]})$

add += (a[i + 1] + add - a[i]) / (i + 1); $?$ add 取当前能取到的最大值，如果这个值与之比较都不行的话就肯定不能了

void solve() {
    int n;cin >> n;
    vector<ll> a(n);for (auto& i : a)cin >> i;
    if (n % 2 == 0) {
        cout << "YES\n";return;
    }
    ll add = 0;
    for (int i = n - 2;i >= 0;i--) {
        if (a[i + 1] + add < a[i]) {
            cout << "NO\n";return;
        } else {
            if ((i + 1) % 2 == 0) {
                add += (a[i + 1] + add - a[i]) / (i + 1);
            }
        }
    }
    cout << "YES\n";
}

void solve() {
    int n;cin >> n;
    vector<ll> a(n);for (auto& i : a)cin >> i;
    ll add = 0, ans = 0;
    for (int i = n - 2;i >= 0;i--) {
        if (n % 2) {
            if (a[i + 1] + add < a[i]) {
                cout << "-1\n";return;
            } else {
                if (i % 2) {
                    add += (a[i + 1] + add - a[i]) / (i + 1);
                }
            }
        }
        ans = max(ans, a[i] - a[i + 1]);
    }
    cout << ans << "\n";
}

B tomorin 的字符串迷茫值

(待更 $\dots$)

J rikki 的数组陡峭值

K soyorin 的通知

B soyorin 的树上剪切