目录

P8665 [蓝桥杯 2018 省 A] 航班时间

思路：

代码：

P8681 [蓝桥杯 2019 省 AB] 完全二叉树的权值

P2347 [NOIP 1996 提高组] 砝码称重

bitset优化 ，主要根据前面的思路，通过bitset数据结构可以减少占用的空间，优化时间。

P8742 [蓝桥杯 2021 省 AB] 砝码称重

---

P8665 [蓝桥杯 2018 省 A] 航班时间

模拟题，经典输入题，能够代表一大类输入问题

思路：

代码：

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int f()
{
	int h1,m1,s1,h2,m2,s2;
	//按输入格式读入 
	scanf("%d:%d:%d %d:%d:%d",&h1,&m1,&s1,&h2,&m2,&s2);
	int day=0;
	if(getchar()==' ')//判断后面有没有+1，因为案例中(+1)前有一个空格 
	 	scanf("(+%d)",&day);//按照格式读入
	int sec=(day*24*3600+h2*3600+m2*60+s2)-(h1*3600+m1*60+s1);
	//将两个时间差转换为秒，可以避免更加复杂的计算
	//如当后面的时间小于前面的时间时直接相减需要考虑向前借位 
	return sec; 
}
int main()
{
	int T;
//	cin>>T;
	scanf("%d",&T);
	while(T--)
	{
		int sec=(f()+f())/2;//返回飞行时间（秒）
		//小技巧：直接调用空函数，一次性完成每个案例的多个数据计算 
		printf("%02d:%02d:%02d\n",sec/3600,sec%3600/60,sec%60);
				//小时，分钟(小于3600又大于60),秒(小于60)
			//按前补0形式输出 
	}
	return 0;
}

P8681 [蓝桥杯 2019 省 AB] 完全二叉树的权值

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=2e5+10;
int a[N];

int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	
	int depth=0,sum=0;
	int k=0;
	for(int i=0;i<n;)
	{
		int temp=0;
		int j=i;
		for(;j<i+(1<<k);j++)
			temp+=a[j];
    //2的倍数使用二进制左右移，如当1左移0个就是1，左移1个就是10=2^1,左移2个就是100=2^2
		if(temp>sum)
		{
			depth=k+1;
			sum=temp;
		}
		i=j;
		k++;
	}
	cout<<depth<<endl;
	return 0;
}

P2347 [NOIP 1996 提高组] 砝码称重

详解点击跳转

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=2e5+10;
int w[]={0,1,2,3,5,10,20};//每种砝码的重量 
int a[N];//每种砝码的个数 
int f[N];//N表示能称出的重量，f[i]=1时表示该重量能称出，即f[i]表示“重量成立” 

int main()
{
	for(int i=1;i<=6;i++)//输入 
		cin>>a[i];
	
	f[0]=1;//初始化，f[0]就是不使用任何砝码的情况 
	for(int i=1;i<=6;i++)//枚举6种砝码 
		for(int j=1;j<=a[i];j++)//枚举每个砝码 
		
			//不理解，为什么这里能实现枚举每个砝码，而不是枚举重量为w[i]的砝码
			 
			for(int k=1000;k>=0;k--)//寻找已成立的重量 
				if(f[k]==1)//若此重量k成立 
					f[k+w[i]]=1;//那么这个重量加上这个未使用的砝码总重量也成立 
			//不太理解为什么在这种情况下是重复????? 
	int ans=0;
	for(int i=1;i<=1000;i++)
	//一遍扫，统计成立的个数
	//一定是从1开始，因为不使用砝码的情况在这里不统计 
		if(f[i])
			ans++;
	cout<<"Total="<<ans<<endl; 
	return 0;	
}

bitset优化 ，主要根据前面的思路，通过bitset数据结构可以减少占用的空间，优化时间。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<bitset>

using namespace std;

const int N=2e5+10;
int w[]={0,1,2,3,5,10,20};

int main()
{
	bitset<1010> f;//设1010个为0的空间 ，f表示重量是否成立 
	f[0]=1;//初始化， 
	
	for(int i=1;i<=6;i++)
	{
		int cnt;
		cin>>cnt;
		for(int j=1;j<=cnt;j++)
		{
			f|=f<<w[i];
			//进行先左移后或的操作
			//如 假设f=0011(重量1和重量2成立）并且此时w[i]=2,左移后变成001100（即重量3和4成立（按位置从1开始）
			//此时0011与001100或，得结果001111，表示重量1，2，3，4都成立 
		}
	}
	cout<<"Total="<<f.count()-1<<endl;
	//f.count()输出bitset中1的数量，-1是减去f[0]的1 
	return 0;
}

P8742 [蓝桥杯 2021 省 AB] 砝码称重

本题中天平既可以放一边也可以放两边，只放一边的思如如上题通过左移并或来实现，但是当两边都放时，要用右移来实现并且要或（保证前面左移的数据不丢失）。

不能先右移再左移，因为右移会将全部变为0，后面的左移操作也无法实现。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<bitset>

using namespace std;

const int N=1e5+10;
int n;
int w[N];

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>w[i];
	
	bitset<100000+10> f;
	//f[i]表示重量为i的方案能够称出 
	f[0]=1;
	
	for(int i=1;i<=n;i++)
		f|=f<<w[i];
	for(int i=1;i<=n;i++)
		f|=f>>w[i];
		
	cout<<f.count()-1<<endl;
	return 0;
}