牛客小白赛40题解

A题

题意：一个数字x，问最少操作多少次变成0，操作如下：

二进制下1的个数是奇数，最低位取反，否则最高位取反

解：按照题意模拟一下就可以。

因为2次操作都至少会去掉一个最高位，所以次数一定不会很多

每次统计一下二进制下1出现的次数，奇数就异或1（最低位），偶数就异或最高位即可啦～～

ps：懒得写快读也过了

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll x;
int t,ans;

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>t;
	while(t--)
	{
		ans = 0;
		while(x)
		{
			ans++;
			ll k = x;
			int s = 0,r = 0;
			while(k)
			{
				r++;
				if(k & 1) s++;
				k /= 2;
			}
			if(s & 1) x ^= 1;
			else x ^= (1ll << (r - 1));
		}
		cout<<ans<<'\n';
	}
	return 0;
}

B题

题意：

解：

C题

D题

题意：通过插入字符使得给出的串的相邻字母不相同，问最后串的长度最小是多少

解：如果原串中两相邻字母相同，就势必要插入一个字母，从前往后扫描一遍，统计有多少对这样的相邻字母即可。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n,t;
char a[N];

int main()
{
	scanf("%d",&t);
	while(t--)
	{
		int ans;
		scanf("%s",a);
		n = strlen(a);
		ans = n;
		for(int i = 1;i < n; ++i)
			if(a[i] == a[i - 1]) ans++;
		printf("%d\n",ans);
	}
	return 0;
}

E题

题意：给出n个数，要求分成m组，每一组必须包含相同的数字，问人数最多的组最少多少人？

解：最大值最小化，很明显的二分答案求解。

二分人数最多的组有x人，暴力check，

求所有组都不超过x人，能够分成多少组，如果<=m组，那么答案可行，否则不可行

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int t,ans,l,r,n,m,x;
map<int,int>q;

bool check(int x)
{
	int s = 0;
	for(auto k: q)
		s += k.second / x + (k.second % x != 0);
	return s <= m;
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i = 1;i <= n; ++i) cin>>x,q[x]++;
	int l = 1,r = n;
	int ans = n + 1;
	while(l <= r)
	{
		int mid = (l + r) / 2;
		if(check(mid)) ans = min(ans,mid),r = mid - 1;
		else l = mid + 1;
	}
	if(ans == n + 1) cout<<"-1\n";
    else cout<<ans<<'\n';
	return 0;
}

F题

G题

题意：有n个人，每个人都有一个期望温度，当室内温度与期望温度差的绝对值不超过p，他就会很舒服，最多能有多少人感到舒服。

解：这题比较基础，支持区间修改和最大值查询的数据结构都可以做

我是差分做的，每个人感到舒服的都是一个区间，我们统计所有区间，在某个温度下，有多少线段覆盖就表示有多少人感到舒服。

#include <bits/stdc++.h>
using namespace std;

const int N = 3e6 + 10;
int n,t,p;
int a[N];
int s,ans;

int main()
{
	cin>>n>>p;
	for(int i = 1;i <= n; ++i)
	{
		int x;
		cin>>x;
		a[x]++,a[x + 2 * p + 1]--,s = max(s,x);
	}
	for(int i = 1;i <= s + 2 * p; ++i)
		a[i] += a[i - 1],ans = max(ans,a[i]);
	cout<<ans<<'\n';
	return 0;
}

I题

题意：需要给n个人排队，每个人有一个a[i],代表第i个人希望排在a[i]前面，问有多少种排队方式满足所有人。

解：一定一定要注意数据范围，n<=10,直接全排列判断是否符合条件即可。

10！=362800

#include<bits/stdc++.h>
using namespace std;

int a[12],b[12];
int ans,n;

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i = 1;i <= n; ++i) cin>>a[i];
	for(int i = 1;i <= n; ++i) b[i] = i;
	int ans = 0;
	do{
		int flag = 1;
		for(int i = 1;i <= n; ++i)
			for(int j = 1;j <= n; ++j)
			{
				if(b[j] == a[i]) break;
				if(b[j] == i) flag = 0;
			}
		if(flag) ans++;
	}while(next_permutation(b + 1,b + n + 1));
	cout<<ans<<'\n';
	return 0;
}