P7071 [CSP-J2020] 优秀的拆分

题意

对于正整数 $n$ 的一种特定拆分，我们称它为“优秀的”，当且仅当在这种拆分下， $n$ 被分解为了若干个不同的 $2$ 的正整数次幂。给定正整数 $n$ ，你需要判断这个数的所有拆分中，是否存在优秀的拆分。若存在，请你给出具体的拆分方案。 $1\le n\le10^7$ 。

点击查看题解

题解

显然，奇数不存在优秀的拆分。之后，我们只需按顺序输出 $n$ 的 $\tt{lowbit}$ 即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[1000];
int main()
{
	scanf("%d",&n);
	if(n%2) {printf("-1");return 0;}
	while(n)
	{
		int lowbit=n&-n;
		a[++a[0]]=lowbit;
		n-=lowbit;
	}
	for(int i=a[0];i>=1;i--) printf("%d ",a[i]);
	return 0;
}

P2114 [NOI2014]起床困难综合症

本题已有题解：link。

P1582 倒水

题意

共 $n$ 个容量无限大的瓶子，开始时每个瓶子里有 $1$ 升水。为了保留不超过 $k$ 个瓶子，每次选择两个当前含水量相同的瓶子，把一个瓶子的水全部倒进另一个里，然后把空瓶丢弃。

显然在某些情况下无法达到目标。此时可以添加一些新的瓶子（新瓶子容量无限，开始时有 $1$ 升水），以到达目标。求最少需要添加多少新瓶子才能达到目标。 $1\le n\le 2\times 10^9$ ， $k\le 1000$ 。

点击查看题解

题解

因为所有的水都是由两份相同的水合并而成的，因此每瓶水的体积一定是 $2^x$ 升。

那么最后总升数的二进制表示中， $1$ 的个数一定小于等于 $k$ 。

暴力代码 part（可以过）：

scanf("%d%d",&n,&k);
for(int i=0;;i++)
{
	int now=i+n;
	while(now)
	{
		now-=(now&-now),cnt++;
		if(cnt>k) {break;}
	}
	if(cnt<=k) {printf("%d\n",i);return 0;}
	cnt=0;
}

如何提高效率？

抛却 $n$ 的从高位数的 $k$ 个为 $1$ 的位，只需要让剩下的位都为 $0$ 就可以了。

n(2) = 110011001 , k = 3
1 1 0 0 1 | 1 0 0 1
ans = 10000(2)-1001(2)

代码

#include<bits/stdc++.h>
using namespace std;
int n,k,cnt=0,tmp,ans=0;
int main()
{
	scanf("%d%d",&n,&k);tmp=n;
	while(tmp) {cnt+=(tmp%2);tmp/=2;}
	if(cnt<=k) {printf("0");return 0;}
	for(int i=1,tmp=n;i<=cnt-k;i++)
		tmp-=(tmp&-tmp),ans=(tmp&-tmp);
	printf("%d",ans-(n&(ans-1)));
	return 0;
}

P7076 [CSP-S2020] 动物园

题意

题面过长，故放链接。

点击查看题解

题解

所有的 $q_i$ 互不相同。所以 $q$ 数组没有必要读入。 $c$ 也没有用。

先计算出所有已有的动物编号中，哪些位至少存在一次。对于每个要求，如果第 $p_i$ 位是存在的，那这种饲料就肯定有了。反之这种饲料是一定没有的，也就是说这一位一定不能为 $1$ 。

除去一定不能为 $1$ 的位，剩下 $t$ 个位可能为 $1$ ，那总动物数就能达到 $2^t$ ，减去已经有的 $n$ 个动物，所以答案是 $2^t-n$ 。

代码

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1000000+10;
ull a[N];__int128 ans=0;
int n,m,c,k,p[N],q[N],b[N],buy[N],tal=0,o[N];
int main()
{
	int tmp;
	scanf("%d%d%d%d",&n,&m,&c,&k);
	for(int i=1;i<=n;i++) scanf("%llu",a+i);
	for(int i=1;i<=m;i++) scanf("%d%d",&tmp,q+i),p[tmp]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;a[i];j++)
			b[j]=(b[j]|a[i]%2),a[i]/=2;
	for(int i=0;i<=k;i++)
		buy[i]=(b[i])&(p[i]);
	for(int i=0;i<=k;i++)
		if(buy[i]==0 && p[i]==1) tal++;
	ans=((__int128)1<<(k-tal))-n;
	while(ans) o[++o[0]]=ans%10,ans/=10;
	while(o[0]) printf("%d",o[o[0]--]);
	return 0;
}