牛客周赛 Round35

A 小红的字符串切割

小红拿到了一个长度为偶数的字符串，请你将其切割成长度相等的两部分并输出。

void solve() {
    string s;cin >> s;
    for (int i = 0;i < s.size() / 2;i++) {
        cout << s[i];
    }
    cout << '\n';
    for (int i = s.size() / 2;i < s.size();i++) {
        cout << s[i];
    }
}

B 小红的数组分配

小红拿到了一个长度为 $2 n$ 的数组，她希望你将其中所有元素分配到两个长度相等的数组 $a$ 和 $b$ ，满足对于 $1 \leq i \leq n$ 有 $a_{i}$ = $b_{i}$ 。你能帮帮她吗？

还可以直接用 map 看是否有不等于 2 的，有则无解

void solve() {
    int n;cin >> n;vector<int> a(2 * n + 1);for (int i = 1;i <= 2 * n;i++)cin >> a[i];
    sort(a.begin() + 1, a.begin() + 1 + 2 * n);
    vector<int> p1, p2;
    for (int i = 1;i <= 2 * n;i++) {
        if (i % 2) {
            p1.push_back(a[i]);
        } else {
            p2.push_back(a[i]);
        }
    }
    for (int i = 0;i < n;i++) {
        if (p1[i] != p2[i]) {
            cout << "-1\n";return;
        }
    }
    for (auto i : p1)cout << i << ' ';
    cout << '\n';
    for (auto i : p2)cout << i << ' ';
    cout << '\n';
}

C 小红关鸡

有 $n$ 个鸡窝排成一排，第 $i$ 个鸡窝在数轴上的坐标是 $x_{i}$ ，有一只小鸡会随机的在一个鸡窝中出现。小红准备在数轴上放置两个栅栏，如果小鸡出现在两个栅栏中间（包括端点），则将被小红关住。为了方便管理，两个栅栏之间的最大距离不能超过 $k$ 。现在小红希望最大化成功“关鸡”的概率，请你帮小红求出这个概率。

void solve() {
    int n, k;cin >> n >> k;vector<int> a(n);for (auto& i : a)cin >> i;
    sort(a.begin(), a.end());
    int ans = 0;
    for (int i = 0;i < n;i++) {
        int t = a[i] + k;
        int res = upper_bound(a.begin(), a.end(), t) - a.begin() - i;
        ans = max(ans, res);
    }
    cout << ans * 1.0 / n << '\n';
}

还可以双指针操作只需要 $O (n)$ 更好

sort(a);
int l = 0, r = 0, ans = 0;
while (r < n) {
    while (a[r] - a[l] > k)l++;
    ans = max(ans, r - l + 1);
    r++;
}
cout << ans * 1.0 / n << '\n';

D 小红的排列构造

小红得到了一个数组，她想尽量少地修改元素，使其成为一个排列。你能帮帮她吗？

void solve() {
    int n;cin >> n;vector<int> a(n + 1), b, c;
    map<int, int> m;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        m[a[i]]++;
    }
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        if (m[i] == 0) {
            ans++;c.push_back(i);
        }
        if (a[i] > n || (a[i] <= n && m[a[i]] > 1)) {
            b.push_back(i);m[a[i]]--;
        }
    }
    cout << ans << '\n';
    for (int i = 0;i < ans;i++) {
        cout << b[i] << " " << c[i] << '\n';
    }
}

E 小红的无向图构造

小红希望你构造一个无向连通图，满足共有 $n$ 个点， $m$ 条边，且 $i$ 号节点到 $1$ 号节点的最短路长度恰好为 $a_{i}$ 。你能帮帮她吗？

Sloution

构造

牛客周赛35直播讲题回放_哔哩哔哩_bilibili

先将必须连接的连接了，再连接不影响最短路长度的路径直到 $m$ 条边。(只有距离为 1 或者距离为 0 的节点加上边后最短路不会变化，可以加上边，其他的都不行)

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
void solve() {
    int n, m;cin >> n >> m;
    vector<int> a(n + 1), g[n + 1];
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        g[a[i]].push_back(i);
    }
    if (m < n - 1) {
        cout << "-1\n";return;
    }
    vector<pair<int, int>>ans;
    int maxa = *(max_element(a.begin() + 1, a.begin() + 1 + n));
    for (int i = 1;i <= maxa;i++) {
        if (g[i].empty()) {
            cout << "-1\n";return;
        }
        for (auto j : g[i])ans.push_back({g[i - 1][0], j});
    }
    if (ans.size() < m) {
        for (int i = 1;i <= maxa;i++) {
            for (int j = 0;j < g[i].size();j++) {
                for (int k = j + 1;k < g[i].size();k++) {
                    ans.push_back({g[i][j],g[i][k]});
                    if (ans.size() == m)goto next;
                }
            }
        }
        for (int i = 1;i <= maxa;i++) {
            for (int j = 1;j < g[i].size();j++) {
                for (auto k : g[i + 1]) {
                    ans.push_back({g[i][j], k});
                    if (ans.size() == m)goto next;
                }
            }
        }
    }
    if (ans.size() < m) {
        cout << "-1\n";return;
    }
next:
    for (auto [i, j] : ans) {
        cout << i << " " << j << '\n';
    }
}

(待更 $\dots$ )

F/G 小红的子序列权值和

小红定义一个数组的权值为：数组所有元素乘积的因子数量。例如， $[1, 2, 3]$ 的权值为 4。

现在小红拿到了一个数组，她想求出数组中所有非空子序列的权值之和。你能帮帮她吗？由于答案过大，请对 $10^{9} + 7$ 取模。

定义数组的子序列为：从左到右选择若干个元素（可以不连续）组成的数组，例如 $[1, 2, 3, 2]$ 的子序列有 $[2, 2]$ 等。因此，一个大小为 $n$ 的数组有恰好 $2^{n} - 1$ 个子序列。

$1 \leq a_{i} \leq 3$

$(1 \leq n \leq 1000)$
$(1 \leq n \leq 10^{5})$

Solution

杨辉三角求组合数/逆元/数论

$C (n, m) = \frac{n!}{(n - m)! \times m!}$

设 $n_{1}, n_{2}, n_{3}$ 分别为 $1, 2, 3$ 的个数，则：

$n_{1} = 2^{n_{1}}$
$n_{2} = \sum_{i = 0}^{n_{2}} (i + 1) \times C (n_{2}, i)$
$n_{3} = \sum_{i = 0}^{n_{3}} (i + 1) \times C (n_{3}, i)$

$ans= n_{1} \times n_{2} \times n_{3} - 1$

void solve() {
    int n;cin >> n;
    vector<vector<ll>> c(n + 1, vector<ll>(n + 1));
    for (int i = 0;i <= n;i++) {
        for (int j = 0;j <= i;j++) {
            if (j == 0 || j == i)c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        }
    }
    array<int, 4> num = {};
    ll t = 1;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;
        num[x]++;
    }
    ll ans = 0;
    for (int i = 1;i <= num[1];i++) {
        t = (2 * t) % mod;
    }
    for (int i = 0;i <= num[2];i++) {
        for (int j = 0;j <= num[3];j++) {
            ans += c[num[2]][i] * c[num[3]][j] % mod * (i + 1) % mod * (j + 1) % mod * t % mod;
            ans %= mod;
        }
    }
    cout << (ans + mod - 1) % mod << '\n';
}

const int mod = 1e9 + 7;
vector<ll> fact(1e5 + 1);
ll c(int n, int m) {
    return fact[n] * (qpow(fact[n - m], mod - 2)) % mod * (qpow(fact[m], mod - 2)) % mod;
}
void solve() {
    int n;cin >> n;
    fact[0] = 1;
    for (int i = 1;i <= n;i++)fact[i] = fact[i - 1] * i % mod;
    
    array<int, 4> num = {};
    for (int i = 0;i < n;i++) {
        int x;cin >> x;num[x]++;
    }
    ll t = qpow(2, num[1]);
    ll ans = 0, c2 = 0, c3 = 0;
    for (int i = 0;i <= num[2];i++) {
        c2 += c(num[2], i) * (i + 1) % mod;
        c2 %= mod;
    }
    for (int i = 0;i <= num[3];i++) {
        c3 += c(num[3], i) * (i + 1) % mod;
        c3 %= mod;
    }
    cout << (c2 % mod * c3 % mod * t % mod - 1 + mod) % mod << '\n';
}