牛客小白月赛30题解

比赛传送门

没有参加正式赛,创了场重现赛来玩玩,AC8题

做最后俩题只剩15分钟,感觉没时间了就没写qwq

补题的时候发现并没有比前面的题目难多少呜呜呜

感觉小白赛的题目和以往相比变得简单了很多

考查了简单的数据结构以及它的应用,重点应该还是对思维的考察


A 黑白边

题目描述:

n个点,m条边,每条边分为黑边和白边,现在需要挑一些边出来,使得n个点可以两两联通。

由于牛牛特别讨厌白边,所以在挑中的边中,让白边最少,输出白边的条数,如果不能两两联通,输出−1.

输入描述:

第一行两个整数 n , m n,m n,m ( 1 ≤ n , m ≤ 2 e 5 ) (1≤n,m≤2e5) (1n,m2e5)

接下来 m 行, 每行三个整数 x,y,z 代表xy之间有一条边。z的值为0或1,0 代表黑边,1代表白边

输出描述:

一行一个整数, 表示最少的白边数量。如果不能满足题目条件,输出 -1

样例输入:

4  4
1 2 0
2 3 0
3 4 1
1 4 0

样例输出:

0

思路:

明显的并查集

先将黑边都连上,再对白边逐一判断

如果某条白边连接的俩个点已经连通,则不连,反之则连上

最后再判断连通分量是否为1

代码:

#include
using namespace std;

const int MAXN = 2e5+5;
struct node{int u,v;}arr[MAXN];
int fa[MAXN];
int N,M,cnt,ans,ttt;
void merge(int x,int y);
int find(int x);

int main()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++) fa[i]=i;
    for(int i=1;i<=M;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if(z==0) merge(x,y);
        else arr[++cnt]=node{x,y};
    }
    for(int i=1;i<=cnt;i++){
        if(find(arr[i].u)!=find(arr[i].v)){
            merge(arr[i].u,arr[i].v);
            ans++;
        }
    }
    for(int i=1;i<=N;i++){
        if(i==fa[i])
            ttt++;
    }
    if(ttt==1) printf("%d",ans);
    else printf("-1");
    return 0;
}

void merge(int x,int y)
{
    fa[find(x)]=find(y);
}


int find(int x)
{
    if(x==fa[x]) return x;
    else return fa[x]=find(fa[x]);
}


B 最好的宝石

题目描述:

牛牛有n个宝石,第i个宝石的价值是 w [ i ] w[i] w[i].

有m个操作,操作分为两种类型

  • Change x y 把第x个宝石的价值改成 y

  • Ask l r 询问区间[l,r]内宝石的最大价值,和最大价值的宝石有多少个。

输入描述:

第一行两个整数 n , m (1 ≤ n,m ≤ 2e5)

第二行有n个整数 w[i] (0 ≤ w[i] ≤ 1e9)

接下来m行,每行代表一个操作。具体见题目描述。

输出描述:

每次询问输出一行,每行两个整数 val cnt

val代表所有宝石中的最大价值,cnt代表价值最大的宝石有多少个。

样例输入:

5 3
2 4 3 6 8
Ask 1 5
Change 2 10
Ask 1 3

样例输出:

8 1
10 1

思路:

线段树上支持单点修改,查询区间最值,区间最值个数的操作

单点修改和区间最值都是老操作了,这个最值个数倒是少见qwq

那就在原线段树的基础上,加上一个区间最值的个数的变量

本题没有下推,而在上推的过程中

若左儿子的区间最值等于右儿子,那父亲节点的最值个数就是左右俩个最值的和

若左儿子的最值大于右儿子,父亲节点的最值个数等于左儿子,右儿子同理

那就做完了。

代码:

#include
using namespace std;

const int MAXN = 2e5+5;
int N,M;
struct node{
    int l,r;
    int cnt,val;
    node(){cnt=-1;val=-1;}
}T[MAXN<<2];
int arr[MAXN];
int x,y;
string op;
void build(int pos,int l,int r);
node query(int pos,int x,int y);
void update(int pos,int x,int k);
void upush(int pos);

int main()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++) scanf("%d",&arr[i]);
    build(1,1,N);
    while(M--){
        cin>>op;
        scanf("%d%d",&x,&y);
        if(op=="Ask"){
            node tmp = query(1,x,y);
            printf("%d %d\n",tmp.val,tmp.cnt);
        } else update(1,x,y);
    }
    return 0;
}


void build(int pos,int l,int r)
{
    T[pos].l=l; T[pos].r=r;
    if(l==r){
        T[pos].val=arr[l];
        T[pos].cnt=1;
        return;
    }
    int mid = (l+r)>>1;
    build(pos<<1,l,mid);
    build(pos<<1|1,mid+1,r);
    upush(pos);
    return;
}


void update(int pos,int x,int k)
{
    int l=T[pos].l,r=T[pos].r;
    if(l==r){ T[pos].val=k; return;}
    int mid = (l+r)>>1;
    if(x<=mid) update(pos<<1,x,k);
    if(x>mid) update(pos<<1|1,x,k);
    upush(pos);
    return;
}


void upush(int pos)
{
    if(T[pos<<1].val==T[pos<<1|1].val){
        T[pos].val=T[pos<<1].val;
        T[pos].cnt=T[pos<<1].cnt+T[pos<<1|1].cnt;
    } else if(T[pos<<1].val>T[pos<<1|1].val){
        T[pos].val=T[pos<<1].val;
        T[pos].cnt=T[pos<<1].cnt;
    } else {
        T[pos].val=T[pos<<1|1].val;
        T[pos].cnt=T[pos<<1|1].cnt;
    }
}

node query(int pos,int x,int y)
{
    int l=T[pos].l,r=T[pos].r;
    if(l>=x&&r<=y) return T[pos];
    node rres,lres,res;
    int mid = (l+r)>>1;
    if(x<=mid) rres=query(pos<<1,x,y);
    if(y>mid) lres=query(pos<<1|1,x,y);
    if(lres.val==rres.val) {res.val=rres.val; res.cnt=lres.cnt+rres.cnt;}
    else if(lres.val>rres.val) {res=lres;}
    else res=rres;
    return res;
}

C 滑板上楼梯

题目描述:

牛牛喜欢玩滑板, 其中最喜欢的一项就是用滑板跳上楼梯。

现在有一个 n 阶楼梯, 牛牛想每次跳上去一阶或者三阶,

由于跳三阶特别累,所以他不能连续跳三阶,牛牛想知道他最少多少次能恰好跳到第 n 阶。

输入描述:

一个数字 n ( 0 ≤ n ≤ 1 e 12 ) ( 0 ≤ n ≤ 1e12) (0n1e12)

输出描述:

输出一个整数,代表最少多少次能恰好跳到第 n 阶。

样例输入:

5

样例输出:

3

思路:

思维+贪心题

第一眼看以为是道DP,但仔细一瞧,是求最少多少步到达,而不是方案数

既然不能连续走三阶台阶,那么就是三阶和一阶间隔着走

那么就是每四个台阶一组,每组走俩步

最后讨论剩余的几种情况

  • N%4==0,这种情况就是直接走完,输出 N ÷ 4 × 2 N\div4\times2 N÷4×2即可
  • N%4==1,最后一步走一阶,输出 N ÷ 4 × 2 + 1 N\div4\times2+1 N÷4×2+1
  • N%4==2,最后两步没办法,走两次,输出 N ÷ 4 × 2 + 2 N\div4\times2+2 N÷4×2+2
  • N%4==2,最后一步走三阶,输出 N ÷ 4 × 2 + 1 N\div4\times2+1 N÷4×2+1

代码:

#include
using namespace std;
long long N;
int main()
{
    scanf("%lld",&N);
    if(N%4==0) printf("%lld",N/4*2);
    else if(N%4==3||N%4==1) printf("%lld",N/4*2+1);
    else printf("%lld",N/4*2+2);
    return 0;
}

D GCD

题目描述:

牛牛有一个集合 S 包含 1 至 n 所有的数, 现在他想让你找一个最小的数 k

使得在 S 中任意找一个子集 T , T 集合中的元素个数为 k

T 中都存在两个数 x,y ,且 gcd(x , y) > 1

如果找不到满足题目条件的 k ,就输出 -1 ,否则输出 k .

输入描述:

一个数字 n ( 1 ≤ n ≤ 1 e 5 ) ( 1 ≤ n ≤ 1e5 ) (1n1e5)

输出描述:

如果找不到满足题目条件的 k ,就输出 -1 ,否则输出 k .

样例输入:

6

样例输出:

5

思路:

先说结论,输出1~N内所有质数个数+2

这题就相当于,在1~N个数里删除尽量多个数,使得剩余的数存在一组数字不互质

这题在手动打表找规律的时候,发现当N为8的时候,只要不删除8,那么2、4、6中若存在一个数,那就满足条件

同理当公约数为3的时候,保留15,则3、6、9、12任意有一个就满足条件

那么我只需保留所有的质数,那么它们之间就相互互质了,再加入任意一个不为1的数,就满足了题目要求

同时1必须得保留,因为1与任意数都互质,如果我留给其他数的位置被1占了,那就不满足条件了

所以答案就是1~N所有质数个数+1+任意一个不为1的数

同时要特判N=1,2,3的时候,直接输出-1

#include
using namespace std;

const long long MAXN = 1e5+5;
long long N,cnt;
bool arr[MAXN];

int main()
{
    scanf("%lld",&N);
    if(N==1||N==2||N==3){
        printf("-1");
        return 0;
    }
    for(long long i=2;i<=N;i++){
        if(arr[i]) continue;
        cnt++;
        for(long long j=i*i;j<=N;j+=i)
            arr[j]=true;
    }
    printf("%lld",cnt+2);
    return 0;
}

E 牛牛的加法

题目描述:

牛牛经常在数学课上睡觉,所以他的数学非常烂。

别人的数学都是进位加法, 但是他的却是非进位加法,比如 7+7 = 4, 22+84 = 6

现在牛牛想考验你一下, 给你两个非常大的数,计算他们的和。

输入描述:

第一行一个整数 a ( a ≥ 0 and |a| ≤ 2e5)

第二行一个整数 b ( b ≥ 0 and |b| ≤ 2e5)

输出描述:

输出一个数 c ,c = a + b

样例输入:

80
34

样例输出:

14

思路:

模拟题

高精度不进位加法

按照题目要求模拟即可,注意不要输出前导0

#include
using namespace std;

const int MAXN = 2e5+5;
string num1,num2;
char ans[MAXN];

int main()
{
    cin>>num1>>num2;
    if(num1.length()>num2.length()) swap(num1,num2);
    while(num1.length()<num2.length()) num1="0"+num1;
    
    int len = (int)num1.length();
    int flag=0;
    for(int i=0;i<len;i++){
        ans[i]=(num1[i]-'0'+num2[i]-'0')%10+'0';
        if(!flag&&ans[i]!='0'){
            flag=1;
            printf("%c",ans[i]);
        }
        else if(flag) printf("%c",ans[i]);
    }
    if(!flag) printf("0");
    return 0;
}

F 石子合并

题目描述:

牛牛有 n 堆石子, 每堆石子有 a[i] 个, 牛牛每次可以选择相邻的两堆石子,然后拿走少的那一堆

得到的价值是两堆石子个数之和, 直到只剩下一堆石子。

如果拿走了第 i 堆石子, 那么第 i-1 堆和第 i+1 堆 就会相邻。

牛牛想知道该怎么拿,才能使得到的价值最多。

输入描述:

第一行一个整数 n, 1 ≤ n ≤ 2e5

第二行 n 个整数 a[i],0 ≤ a[i] ≤ 1e9

输出描述:

输出得到的最大价值

样例输入:

5
2 5 3 5 1

样例输出:

31

思路:

贪心题

既然要总价值最大,那么我每次选取都选取最大的那一堆石头

那最大的那一堆就参与了每次的合并,就可以使得价值最大

那么答案就是:最大值 × ( N − 2 ) \times(N-2) ×(N2)+石头堆总和

#include
using namespace std;

const int MAXN = 2e5+5;
long long N,mx=-1;
long long arr[MAXN],ans;

int main()
{
    scanf("%lld",&N);
    for(int i=1;i<=N;i++){
        scanf("%lld",&arr[i]);
        mx=max(mx,arr[i]);
        ans+=arr[i];
    }
    printf("%lld",ans+mx*(N-2));
    return 0;
}

G 滑板比赛

题目描述:

牛牛喜欢玩滑板,牛妹也喜欢玩滑板。

牛牛会n个动作,每个动作的华丽值为 a[i],牛妹会m个动作,每个动作的华丽值为b[i],m ≤ n.

现在他们进行 m 次比赛,每一次比赛两人选择一个动作,且每个动作只能用一次,华丽值大的获胜。

牛牛已经悄悄的打探过,所以知道牛妹参加m次比赛所用动作的顺序。

牛牛想知道怎么安排动作的顺序,使得他可以尽可能多的赢得比赛次数。

输入描述:

第一行两个整数 n,m。1 ≤ m ≤ n ≤ 2e5

第二行包含 n 个整数 a[i], 代表牛牛所有会的动作的华丽值。0 ≤ a[i] ≤ 1e9

第三行包含 m 个整数b[i],代表牛妹所有会的动作的华丽值。给出的顺序就是牛妹参加比赛所用动作的顺序。0≤b[i]≤1e9

输出描述:

一个整数,代表牛牛最多可能赢的比赛次数。

样例输入:

5 5
3 4 6 2 7
4 4 3 2 6

样例输出:

4

思路:

贪心+模拟

将俩个序列分别排个序,然后从后向前遍历

若牛牛的华丽值大于牛妹的,那么答案+1,俩个指针都向前走

若牛牛的华丽值小于等于牛妹的,那么牛妹的指针往前走

直到任意一个指针走出序列

这样就保证了牛牛的华丽值都被充分应用

代码:

#include
using namespace std;

const int MAXN = 2e5+5;
int N,M,ans;
int arr[MAXN],brr[MAXN];

int main()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++) scanf("%d",&arr[i]);
    for(int j=1;j<=M;j++) scanf("%d",&brr[j]);
    sort(arr+1,arr+1+N);
    sort(brr+1,brr+1+M);
    
    int now=M,i=N;
    while(i>=1&&now>=1){
        if(arr[i]>brr[now]){
            ans++;
            now--;
            i--;
        }
        else now--;
    }
    printf("%d",ans);
    return 0;
}

H 第 k 小

题目描述:

有一个长度为n的数组,值为 a[i], 牛牛想找到数组中第 k 小的数。比如 1 2 2 3 4 6 中,第 3 小的数就是2.

牛牛觉得这个游戏太简单了,想加一点难度,现在牛牛有 m 个操作,每个操作有两种类型。

  • 1 代表操作一,给数组中加一个元素 x 。(0 ≤ x ≤ 1e9)

  • 2 代表操作二,查询第 k 小的数。如果没有 k 个数就输出−1

输入描述:

第一行有三个整数,n m k,(1≤n,m,k≤2e5)

第二行包含 n 个整数 a[i] ( 0 ≤ a[i] ≤ 1e9)

接下来m行,每行代表一个操作。具体见题目描述

输出描述:

每次查询输出一个第 k 小的数。

样例输入:

5 4 3
1 2 3 4 5
2
1 1
1 3
2

样例输出:

3
2

思路:

本以为是道很难的题目

但是第K小的数,这个K确实固定的

那直接维护一个长度为K的优先队列即可

因为比当前第K大的数更大的数,对答案并没有影响

只用考虑比它小的数加入即可,每次队头元素就是第K大的数

代码:

#include
using namespace std;

int N,M,K,op,x;
priority_queue<int>Q;

int main()
{
    scanf("%d%d%d",&N,&M,&K);
    for(int i=1;i<=N;i++){
        scanf("%d",&x);
        Q.push(x);
    }
    while(Q.size()>K) Q.pop();
    while(M--){
        scanf("%d",&op);
        if(op==1){
            scanf("%d",&x);
            Q.push(x);
            if(Q.size()>K)
                Q.pop();
        }
        else {
            if(Q.size()<K) printf("-1\n");
            else printf("%d\n",Q.top());
        }
    }
    return 0;
}

I 区间异或

题目描述:

有一个长度为 n 的数组 a[i] , 有 m 次询问, 每次询问给一个值 x ,

找出一个最短的区间, 使得这个区间的异或和 ≥ x , 输出区间长度。如果找不到输出 -1

输入描述:

第一行两个整数 n , m (1 ≤ n ≤ 3000 and 0 ≤ m ≤ 2e5)

第二行 n 个整数 a[i] . (0≤ a[i] ≤ 1e9)

接下来 m 行, 每行一个整数 x , 代表一次询问。 (0 ≤ x ≤ 1e9)

输出描述:

每次询问输出满足条件的最短区间,如果找不到输出 -1

样例输入:

5 3
16 5 2 8 32
4 
48
33

样例输出:

1
5
2

思路:

观察到题目给的N范围很小

完全可以在 N 2 N^2 N2预处理一下,找出所有的区间异或和

然后排序后,就可以通过二分查找,找到满足条件的位置

但是找到的位置的后面都满足题目,要找到长度最小的那个区间

那就再用一个后缀预处理,从后到前找到当前位置及后面所有的最小值

然后就可以O(logN)查询了

代码:

#include
using namespace std;

const int MAXN = 3e3+5;
struct node{
    int len,val;
    bool operator < (const node x)const{
        if(val!=x.val) return val<x.val;
        else return len<x.len;
    }
};
int arr[MAXN];
node ans[MAXN*MAXN];
int tmp[MAXN*MAXN];
int N,M,cnt,x;
void init(){
    for(int i=1;i<=N;i++){
        int res=0;
        for(int j=i;j<=N;j++){
            node tmp;
            tmp.len=j-i+1;
            res^=arr[j];
            tmp.val=res;
            ans[++cnt]=tmp;
        }
    }
    sort(ans+1,ans+1+cnt);
    tmp[cnt+1]=1e9+7;
    for(int i=cnt;i>=1;i--)
        tmp[i]=min(tmp[i+1],ans[i].len);
    return;
}

int main()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++) scanf("%d",&arr[i]);
    init();
    while(M--){
        scanf("%d",&x);
        long pos = lower_bound(ans+1,ans+cnt+1,node{0,x})-ans;
        if(pos>cnt) printf("-1");
        else printf("%d\n",tmp[pos]);
    }
    return 0;
}

J 小游戏

题目描述:

有一个长度为 n 的数组 a[i] , 每一步能拿走一个数

比如拿第 i 个数, a[i] = x ,得到相应的分数 x ,但拿掉这个 x 后, x+1 和 x-1 (如果有 a[j] = x+1 或 a[j] = x-1 存在) 就会变得不可拿(但是有 a[j] = x 的话可以继续拿这个 x )。

求最大分数。

输入描述:

第一行一个整数 n. ( 1 ≤ n ≤ 2e5)

第二行 n 个整数 a[i]. (0 ≤ a[i] ≤ 2e5)

输出描述:

输出能得到的最大分数。

样例输入:

5
1 2 2 2 3

样例输出:

6

思路:

读题可知,每个数字的位置没有影响,只有它的大小会产生影响

看到每个数范围2e5,容易想到把数的值加入到对应的桶里

然后再用DP,分别记录当前数是否拿取

  • Dp1[i]:一定拿当前数,那就是前一个数不拿加上当前数,即Dp2[i-1]+arr[i]
  • Dp2[i]:一定不拿当前数,那就是前一个数拿和不拿的最大值,即max(Dp1[i-1],Dp2[i-1])

然后递推即可

代码:

#include
using namespace std;

const int MAXN = 2e5+5;
int N,x;
long long num[MAXN];
long long dp1[MAXN],dp2[MAXN];

int main()
{
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        scanf("%d",&x);
        num[x]+=x;
    }
    for(int i=1;i<MAXN;i++){
        dp1[i]=dp2[i-1]+num[i];
        dp2[i]=max(dp1[i-1],dp2[i-1]);
    }
    printf("%lld",max(dp1[MAXN-1],dp2[MAXN-1]));
    return 0;
}

你可能感兴趣的