T1: 学习除法

鸡尾酒的学生丹丹学不会除法，有一天他遇到了这样的一个问题：给定一个整数 $nn$，你可以任选一个 $nn$ 的因子 $xx$，然后将 $nn$ 除以 $xx$。你可以进行任意次这样的操作，直到 $nn$ 是一个质数为止。请问至少几次操作可以让 $nn$ 变成一个质数。

由于丹丹不会除法，更不知道因子是什么意思，所以他将这个问题交给你了，请你帮他解决这个问题。

例如：原数字 $n=8n=8$，选择 $88$ 的因子 $22$，将 $88$ 除以 $22$，此时 $n=4n=4$。然后再选择 $44$ 的因子 $22$，将 $44$ 除以 $22$，得到 $n=2n=2$。此时 $nn$ 是一个质数。（这样的操作方案不一定是最优的，因为本题在求最少的操作次数）

大致思路，容易发现，如果 $nn$ 是质数，不需要操作。如果 $nn$ 是合数，总可以除一个数变成质数，所以只需要操作一次。

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
int n;
 
bool check(int x) {
    for (int i = 2; i <= x / i; i++) {
        if (x % i == 0) return 0;
    }
    return 1;
}
 
signed main() {
    cin >> n;
    if (check(n)) puts("0");
    else puts("1");
}

T2: 拆分

鸡尾酒又带着大家学习新定义啦！今天要学习的内容是集合的 $mexmex$，集合的 $mexmex$ 指的是一个集合没有出现过的最小自然数。例如，$mex(1,2)=0mex(\{1,2\})\; =\; 0$，$mex(0,1,2,3)=4mex(\{0,1,2,3\})\; =\; 4$。

现在你有一个包含 $nn$ 个元素的集合，你可以将它分成任意个数量的新集合，使得所有新集合的 $mexmex$ 值之和最大，求这个最大值是多少。

如果说划分的一个子集不包含 $00$，则其 $mexmex$ 为 $00$，也就是毫无贡献。只需要对所有 $00$ 往上慢慢叠加计算贡献即可。只有 $00$ 存在才有贡献！由于数据范围 $\le 1000\backslash leq\; 1000$，可以开桶！

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e5 + 5;
int n, a[N], cnt[N], t, res;

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == 0) t++;    // 计算0的数量
        else cnt[a[i]]++;  // 开个桶
    }
    while (t--) {   // 来t次就可以了
        int j = 1;
        for (j = 1; j <= 1001; j++) {     // 找到第一个数不存在
            if (cnt[j]) cnt[j]--;   // 如果有，在桶里面减
            else break;
        }
        res += j;   // 加贡献
    }
    cout << res << endl;
}

T3: 部落

在一个山峰中住着许多部落，其中一些部落住在山脚，一些部落住在山腰，一些部落住在山顶。我们假设共有 $n\backslash mathit\; n$ 个部落，编号分别为 $1,2,3,\mathrm{.}\mathrm{.}\mathrm{.},n-1,n1,2,3,...,n-1,n$，且第 $pos\backslash mathit\; pos$ 个部落的位置在山顶。那么编号为 $1\sim pos1\; \backslash sim\; pos$ 的部落海拔依次上升，从 $pos\sim npos\; \backslash sim\; n$ 的部落海拔依次降低。第 $i\backslash mathit\; i$ 个部落和第 $i+1,i-1\backslash mathit\; i+1,\; i-1$ 个部落相邻 $(2\le i\le n-1)(2\; \backslash leq\; i\; \backslash leq\; n-1)$。

由于山中常年缺水，主要的水资源是山间的流水，具体来说，水资源都聚集在山顶，海拔较低的部落只能使用海拔较高的部落用剩下的水资源。由于分配不均，相邻的部落之间可能会发生战争，其中第 $ii$ 个部落的战斗力为 $a_{i}a\_i$。

当某一个部落的海拔比另一个相邻部落的海拔低，且战斗力比这个部落高，则会对这个部落发动战争。

现在为了避免相邻部落之间发生战争，你可以修改一些部落的战斗力，使得每一对相邻的部落之间都不会有战争。请问最少可以修改几个部落的战斗力才可以满足要求？

可以知道这道题是一个 LIS 问题。从 $11$ 到 $pospos$ 求一遍 LIS，再从 $pospos$ 到 $nn$ 求一遍下降子序列。但是由于双方有重复部分 $pospos$，所以考虑最上面那一个点是否需要修改高度！否则都算一遍会多答案。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int n, pos, a[N], g[N], cnt, res;

int main() {
    cin >> n >> pos;
    for (int i = 1; i <= n; i++) cin >> a[i];
    g[++cnt] = a[1];
    for (int i = 2; i < pos; i++) {
        if (a[i] >= g[cnt]) g[++cnt] = a[i];
        else g[lower_bound(g + 1, g + cnt + 1, a[i]) - g] = a[i];
    }
    if (a[pos] >= g[cnt]) cnt++;  // 不需要修改
    else a[pos] = 1e9;  // 需要修改就厉害点，正无穷
    res += pos - cnt;
  
    cnt = 0;   // pos~n求一遍
    g[++cnt] = a[n];
    for (int i = n - 1; i >= pos; i--) {
        if (a[i] >= g[cnt]) g[++cnt] = a[i];
        else g[lower_bound(g + 1, g + cnt + 1, a[i]) - g] = a[i];
    }
    res += (n - pos + 1) - cnt;
    cout << res << endl;
}