比赛链接

牛客小白月赛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;
}