[C++知识库]牛客oi普及组第一场A-C （D在下一篇）

A：学习除法

?

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

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

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

输入描述:

输入仅一行一个整数 n。

输出描述:

输出一行一个答案。

示例1

输入

8

输出

1

说明

选择 8 的因子 4，将 8 除以 4，得到 2，2 是质数，共用了一次操作。

示例2

输入

5

输出

0

说明

5 已经是质数了，所以不需要进行任何操作就可以将其变为质数，输出 0。

备注:

对于 80% 的数据，有 2≤n≤10^6

对于 100% 的数据，有 2≤n≤10^10

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int solve(int x)
{
    for(int i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            return 1;
        }
    }
    return 0;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    cout<<solve(n);
    return 0;
}

B:拆分

?

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

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

?

输入描述:

第一行输入一行一个正整数 n，接下来一行包含 n 个非负整数，表示集合中的元素 ai?

输出描述:

输出一行一个整数表示答案。

示例1

输入

5
0 0 1 1 2

输出

5

说明

分成两个集合 {0, 1}, {0, 1, 2}, 第一个集合的 mex 为 2，第二个集合的 mex 为 3，两个集合的 mex 之和为 5，这样分集合是最大的。当然也可以分成 {0}, {0}, {1}, {1}, {2}，但是这样五个集合的 mex 之和为1+1+0+0+0=2

示例2

输入

5
1 2 3 4 5

输出

0

说明

因为原集合没有 0，所以无论怎么分集合，每一个新集合都不会有 0，所以每一个集合的 mex 都为 0，答案一定为 0.

备注:

本题共有 10 个测试点

第一个测试点有 0<ai?

第二个测试点有 ai=0

第 3-4 个测试点有 0≤ai?≤1

对于所有测试点，有 1≤n≤10^5,0≤ai≤1000

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
const int M=1010;
int n;
int a[N];
int dui[M];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("T2simple.in","r",stdin);
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        dui[a[i]]++;
    }
   if(dui[0]==0)
   {
       cout<<0<<"\n";
       return 0;
   }
   int sum=0;
   for(int i=0;i<=1000;i++)
   {
       if(dui[i]==0)
       {
           break;
       }
       if(dui[i]<=dui[i+1])
       {
           dui[i+1]=dui[i];
       }
       else
       {
           sum+=(i+1)*(dui[i]-dui[i+1]);
       }
   }
   cout<<sum<<"\n";
    return 0;
}

?

C:部落

一个原题原题！！！！！！！！！

但是我没有处理边界情况哎，这次更懂一点了。

?

题目描述

在一个山峰中住着许多部落，其中一些部落住在山脚，一些部落住在山腰，一些部落住在山顶。我们假设共有n 个部落，编号分别为 1,2,3,...,n?1,n，且第 pos\mathit pospos 个部落的位置在山顶。那么编号为 1～pos1的部落海拔依次上升，从 pos～n的部落海拔依次降低。第 i 个部落和第 i+1,i?1个部落相邻 (2≤i≤n?1)。

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

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

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

输入描述:

输入第一行包含两个正整数 n,pos(1≤n,pos≤10^5)，分别表示部落的数量以及住在山顶的部落的编号。

输入第二行包含  n 个正整数 ai(1≤ai≤10^9)，分别表示每个部落的战斗力。

输出描述:

输出一行一个正整数表示答案。

示例1

输入

5 3
1 5 4 2 1

输出

复制1

1

说明

pos 为 3，所以 3 应该是战斗力最高的位置。可以考虑将第三个位置改为 5 或更大的数字（改成 5 时，位置 2 和位置 3 的战斗力相等，不会发动战争，只有位置 2 严格大于位置 3，才会发动战争）。

示例2

输入

5 2
1 4 4 2 1

输出

0

说明

无需修改战斗力即可保持和平

备注:

对于 20% 的数据，有 n≤6

对于 60% 的数据，有n≤1000

对于 100% 的数据，有 n<=10^5

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],l[N],r[N];
int f[N],d[N];
int n,m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        l[i]=1;
        r[i]=1;
    }
    if(n==1)
    {
        cout<<0<<"\n";
        return 0;
    }
    //1
    f[1]=a[1];
    l[1]=1;
    int len=1;
    for(int i=2; i<=m-1; i++)
    {
        if(f[len]<=a[i])f[++len]=a[i];
        else f[lower_bound(f+1,f+len+1,a[i])-f]=a[i];
        l[i]=len;
    }
    int lens=1;
    d[1]=a[n];
    for(int i=n-1; i>=m+1; i--)
    {
        if(d[lens]<=a[i])d[++lens]=a[i];
        else d[lower_bound(d+1,d+1+lens,a[i])-d]=a[i];
        r[i]=lens;
    }
    int ans=n-1-l[m-1]-r[m+1];
    if(m==1&&d[lens]>a[1])
    {
        ans++;
    }
    else if(m==n&&f[len]>a[n])
    {
        ans++;
    }
    else
    {
        if(a[m]<f[len]||a[m]<d[lens])
            ans++;
    }
    cout<<ans<<"\n";

    return 0;
}