牛客春招刷题训练营3月11日题解

活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 字符串分隔

记 为字符串的长度。
当 不为 的倍数时在字符串后面补 。
利用 substr() 对字符串切片输出。
字符串的 substr(i, n) 成员函数会返回 中下标为 的子串。

#include <iostream>
using namespace std;
int main() {
    string s;
    cin >> s;
    while (s.length() % 8 != 0)
        s += "0";
    for (int i = 0; i < s.length(); i += 8)
        cout << s.substr(i, 8) << '\n';
    return 0;
}

中等题 质数因子

质因数分解模板题。
从 开始遍历到 ，逐个检查每个数是否为给定数字的因数。
当发现一个因数就把 一直除以这个因数，并将这个因数加入答案中，直到不存在这个因数。
如果最后 不为 ，直接将 加入答案。

#include <bits/stdc++.h>
using namespace std;
int main() {
    vector<int> primes;
    int n;
    cin >> n;
    int maxn = n;
    for (int i = 2; i <= sqrtl(maxn); i++) {
        if (n % i == 0) {
            while (n % i == 0) {
                primes.push_back(i);
                n /= i;
            }
        }
        if (n == 1)break;
    }
    if (n > 1)
        primes.push_back(n);
    for (auto x : primes)
        cout << x << ' ';
    return 0;
}

困难题 合唱队

最长上升/下降子序列问题。

记 为 区间内最长上升子序列的长度，即 左侧最长上升子序列的长度。
记 为 区间内最长下降子序列的长度，即 右侧最长下降子序列的长度。

从 到 遍历 ，对每个 再从 到 遍历 ，如果 ，则 可以加在以 结尾的最长上升子序列后面，转移方程为 。
从 到 遍历 ，对每个 再从 到 遍历 ，如果 ，则 可以加在以 开头的最长下降子序列前面，转移方程为 。

以 为顶峰的最长合唱队长度为左侧的最长上升子序列长度加右侧的最长下降子序列长度再减去自己，即为 。

因为求的是最少的出列同学个数，所以答案是 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    vector<int> l(n, 1), r(n, 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (a[j] < a[i])
                l[i] = max(l[i], l[j] + 1);
    for (int i = n - 1; i >= 0; i--)
        for (int j = n - 1; j > i; j--)
            if (a[j] < a[i])
                r[i] = max(r[i], r[j] + 1);
    int ans = 0;
    for (int i = 0; i < n; i++)
        ans = max(ans, l[i] + r[i] - 1);
    cout << n - ans << '\n';
    return 0;
}