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

简单题：字符串分隔

可以考虑一个字符一个字符地输出，，每输出8个字符就输出一个回车。这一点可以用一个累加器来实现，累加器是8的倍数的时候就输出回车。

最后累加器如果不是8的倍数，就输出0，直到变为8的倍数。

#include <iostream>
using namespace std;

int main() {
    string s;
    cin >> s;
    int tot = 0;
    for(char c: s) {
        cout << c;
        tot ++;
        if(tot % 8 == 0) {
            cout << endl;
        }
    }
    while(tot % 8 != 0) {
        cout << 0;
        tot ++;
    }
    return 0;
}

中等题：质数因子

分解质因数的模板，准备春招的uu们可以记一下。

复杂度是O(√N)

#include <iostream>
#include <vector>
using namespace std;
vector<pair<int, int>> div(int n)
{
	vector<pair<int, int>> res;
	for(int i=2; i<=n/i; i++)
	if(n%i == 0) {
		int cnt = 0;
		while(n%i == 0) n/=i, cnt++;
		res.emplace_back(i, cnt);
	}
	if(n > 1) res.emplace_back(n, 1);
	return res;
}
int main() {
    int n;
    cin >>n;
    auto d = div(n);
    for(auto [x, y]: d)
        for(int i=1; i<=y; i++)
            cout << x << " ";
  	return 0;
}

困难题：合唱队

最长上升子序列DP模型

要使得出列的同学最少，就要找一个最长的^形序列。

我们用 up[i] 记录以 a[i] 结尾的最长上升子序列，down[i] 记录以 a[i] 开头的最长下降子序列。

最后打一遍擂台，求出max{up[i] + down[i]}就是答案。

然后查看题目n的范围是 [1, 3000]，用N^2复杂度的求法求最长上升子序列即可。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n+1);
    for(int i=1; i<=n; i++)
        cin >> a[i];
    vector<int> up(n+1, 1), down(n+1, 1);
    for(int i=1; i<=n; i++) {
        for(int j=1; j<i; j++) {
            if(a[j] < a[i]) {
                up[i] = max(up[i], up[j]+1);
            }
        }
    }
    for(int i=n; i>=1; i--) {
        for(int j=i+1; j<=n; j++) {
            if(a[j] < a[i]) {
                down[i] = max(down[i], down[j]+1);
            }
        }
    }
    int res = 0;
    for(int i=1; i<=n; i++) {
        res = max(res, up[i]+down[i]-1);
    }
    cout << n - res << endl;
    return 0;
}