当前位置: 首页 > news >正文

牛客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;
}

相关文章:

  • paddle,图像转tensor 两种方法的不同
  • [MySQL]聚合函数与分组
  • Linux Shell - echo 命令输出格式
  • Nginx反向代理和负载均衡实战
  • huawei euleros - 本地安装和远程安装的区别
  • 自然语言处理学习笔记——文本预处理
  • Hadoop 3.x(HDFS)----【HDFS 的 API 操作】
  • [MySQL]流程控制函数加密与解密函数MySQL信息函数其他函数
  • 数据仓库-数据分层理论详解
  • 【JDBC实战】水果库存系统 [代码优化]
  • python+selenium 爬虫
  • JDBC.
  • 推荐系统实战
  • 【opencv-c++】cv::mixChannels通道混合
  • 机器学习笔记(四)
  • 1480_人月神话阅读笔记_开篇
  • 《测绘综合能力》——测绘航空摄影
  • AB变换
  • 【Shell编程】Shell中Bash变量-位置参数变量
  • 安卓环境配置