牛客周赛 Round 42

A. 小红叕战小紫

思路：

• 一个字符串，每次可以删除前缀或者后缀，把它删的只剩一个字符
• 如果只有一个字符，就是 yukari 的必胜态，否则就是 kou 的必胜态

时间复杂度：

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::string s;
    std::cin >> s;

    if (s.size() == 1) {
        std::cout << "yukari\n";
    } else {
        std::cout << "kou\n";
    }

    return 0;
}

B. 小红的数组移动

思路：

• 按照指令模拟即可

时间复杂度：

constexpr int P = 1E9 + 7;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }

    std::string s;
    std::cin >> s;

    int p = 1;
    i64 ans = 0;
    for (auto op : s) {
        if (op == 'R') {
            if (p != n) {
                ans += a[++p];
            } else {
                ans += a[p];
            }
        } else {
            if (p != 1) {
                ans += a[--p];
            } else {
                ans += a[p];
            }
        }
        ans %= P;
    }
    std::cout << ans << "\n";

    return 0;
}

C. 小红的素数合并

思路：

• 由于每一个元素都是素数，所以根据算数基本定理，一个正整数可以由任意个素数相乘得到，然后我们贪心的考虑，要使得最后两个数的差值最小，那么一定要使得最后两个数更加接近。
• 然后，我们分奇偶性考虑，将整个序列按照最小值与最大值相乘，然后使得最后的数更加平均即可，然后这个序列的最大值减去最小值就是最终序列的最大值减去最小值。

时间复杂度：

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }

    std::sort(a.begin() + 1, a.end());

    std::vector<i64> b;
    if (n & 1) {
        b.push_back(a[n]);
    }
    for (int l = 1, r = (n & 1 ? n - 1 : n); l <= r; l++, r--) {
        if (l != r) {
            b.push_back(1LL * a[l] * a[r]);
        } else {
            b.push_back(a[l]);
        }
    }
    std::sort(b.begin(), b.end());

    std::cout << b.back() - b.front() << "\n";

    return 0;
}

D. 小红的树上删边

思路：

• 我们维护每个子树的点数大小，然后当找到一个子树的大小为偶数，就

时间复杂度：

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<std::vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int ans = 0;
    std::vector<int> cnt(n);
    auto dfs = [&](auto self, int x, int fa = -1) -> void {
        cnt[x] += 1;
        for (int v : adj[x]) {
            if (v == fa) continue ;
            self(self, v, x);
            cnt[x] += cnt[v];
        }
        if (fa != -1 && cnt[x] % 2 == 0) ans++;
    };

    dfs(dfs, 0);

    std::cout << (n & 1 ? -1 : ans) << "\n";

    return 0;
}

E. 小红的子序列求和

思路：

• 组合计数，我们首先初始化 位中作为第 位的权值，然后预处理组合数
• 然后我们从 枚举，对于第 位，由这个数作为第 位的数有 种方案，这个作为当前第 位对于答案的贡献

时间复杂度：

constexpr int P = 1E9 + 7;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k;
    std::cin >> n >> k;

    std::string s;
    std::cin >> s;

    std::vector<i64> bit(1010, 1);
    for (int i = 1; i <= 1000; i++) {
        bit[i] = bit[i - 1] * 10 % P;
    }

    std::vector<std::vector<i64>> C(1010, std::vector<i64>(1010));
    for (int i = 0; i <= 1000; i++) {
        for (int j = 0; j <= i; j++) {
            if (i == j || j == 0) {
                C[i][j] = 1;
            } else {
                C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
            }
            C[i][j] %= P;
        }
    }

    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            ans += (s[i] - '0') * bit[k - j - 1] % P * C[n - i - 1][k - j - 1] % P * C[i][j] % P;
            ans %= P;
        }
    }
    std::cout << ans << "\n";

    return 0;
}