牛客小白月赛40

比赛链接

牛客小白月赛40

A.数字游戏

题目描述

\(dd\) 在玩数字游戏,首先他拿到一个 \(x\)
当 \(x\) 不为零时进行如下操作
如果二进制 \(x\) 中有奇数个 \(1\),则 \(x\) 二进制形式下最低位取反(即 \(0\) 变成 \(1\),\(1\)变成 \(0\))
如果二进制 \(x\) 中有偶数个 \(1\),则 \(x\) 二进制形式下非前导零最高位取反
询问对于一个 \(x\),操作几次后变为零

输入描述:

第一行一个正整数\((1≤T≤1000000)\),表示询问组数
接下来 \(T\) 行,每行一个数 \(x(0≤x≤1000000000)\) 表示询问的数字
由于本题数据量比较大,请选择较快的读入方式

输出描述:

输出 \(T\) 行,每行是对应的答案

输入

3
0
1
5

输出

0
1
2

解题思路

模拟

分类讨论:
\(f1[i]\) 表示为奇数,且二进制表示下 \(1\) 的个数为 \(i\) 的操作数
\(f2[i]\) 表示为偶数,且二进制表示下 \(1\) 的个数为 \(i\) 的操作数
初始化:\(f1[1]=1,f1[2]=2,f2[1]=3\)

\(i\) 为奇数时,\(f1[i]=f2[i-1]+1,f2[i]=f1[i+1]+1\)
\(i\) 为偶数时,\(f1[i]=f1[i-1]+1,f2[i]=f2[i-1]+1\);

  • 时间复杂度:\(O(T)\)

代码

#include<bits/stdc++.h>
using namespace std;
int t,x;
int f1[35],f2[35],cnt;
int main()
{
    f1[1]=1,f1[2]=2,f2[1]=3;
    for(int i=2;i<=33;i++)
    {
        if(i&1)
        {
            f1[i]=f2[i-1]+1;
            f1[i+1]=f1[i]+1;
            f2[i]=f1[i+1]+1;
        }
        else
            f2[i]=f2[i-1]+1;
    }
    for(scanf("%d",&t);t;t--)
    {
        scanf("%d",&x);
        cnt=__builtin_popcount(x);
        printf("%d\n",(x%2)?f1[cnt]:f2[cnt]);

    }
    return 0;
}

E.分组

题目描述

\(dd\)当上了宣传委员,开始组织迎新晚会,已知班里有\(n\)个同学,每个同学有且仅有一个擅长的声部,把同学们分成恰好\(m\)组,为了不搞砸节目,每一组里的同学都必须擅长同一个声部,当然,不同组同学擅长同一个声部的情况是可以出现的,毕竟一个声部也可以分成好几个part进行表演,但是他不希望出现任何一组的人过多,否则可能会导致场地分配不协调,也就是说,她希望人数最多的小组的人尽可能少,除此之外,对组内人员分配没有其他要求,她希望你告诉她,这个值是多少,如果无法顺利安排,请输出-1

输入描述:

第一行两个数个数\(n,m(1≤m≤n≤100000)\)表示人数
接下来一行\(n\)个数,\(a[i](1≤a[i]≤n)\)表示第i个学生的擅长声部

输出描述:

输出一个数,表示人数最多的小组的人数

输入

5 3
2 2 3 3 3

输出

2

解题思路

二分

统计共有多少组及每个组有多少人,再二分答案,求出最少能分出多少组判断即可~

  • 时间复杂度:\(O(nlogn)\)

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],cnt;
unordered_map<int,int> mp;
bool ck(int x)
{
    int res=0;
    for(int i=0;i<cnt;i++)
    {
        res+=a[i]/x;
        res+=(a[i]%x>0);
    }
    return res<=m;
}
int main()
{
    scanf("%d%d",&n,&m);
    int x,mx=0,mn=0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        mp[x]++;
        mx=max(mx,x);
        mn=min(mn,x);
    }
    for(int i=mn;i<=mx;i++)
        if(mp[i])a[cnt++]=mp[i];
    if(cnt>m)puts("-1");
    else
    {
        int l=1,r=n;
        while(l<r)
        {
            int mid=l+r>>1;
            if(ck(mid))r=mid;
            else
                l=mid+1;
        }
        printf("%d",l);
    }
    return 0;
}
上一篇:1032 Sharing (25 分)(链表)


下一篇:2021-2022-1 20211427 《信息安全专业导论》第七周学习总结