试题 算法训练 无聊的逗 - 蓝桥杯

状态间的比较 （暴力检索） ： 选出在两根一样长的情况下长度最长的， 实际就是2^n 种组合比较，在状态检索中， 找到 不同状态（无重复的木棍）的组合 并且 木棍总长度相等的 最大值 。 举个栗子（以题中 n = 4, 木棍长度分别为 1 2 3 1 为例）： 我们以二进制 1 和 0 代表 不同的状态组合 ， 那么就会有 0000， 0001， 0010， 0011，……1111 ， 2^4 = 16种组合 。 （注意01值并不代表木棍的出现与否，状态与木棍的匹配是通过 按位与运算 实现的！！！）

通过 按位与运算 将木棍长度加到不同的状态，在循环中我们会发现 ， 0010 与 0011 的木棍总长度相等，长度为3（长度值不断更新， 直至跳出循环， 此时长度为最大值） 。

在下面的代码中 ，一些小细节在注释中体现 （比如按位与运算）

/*
    状态间的比较 ：  
    选出在两根一样长的情况下长度最长的，
    实际就是2^n 种组合比较，在状态检索中，
    找到 不同状态（无重复的木棍）的组合 并且 木棍总长度相等的 最大值 。
	此题需要弄清 按位与运算 与 解题 的逻辑，具有一定难度。 
							2022/2/13  fevergo 明鹊。。。										
	希望对你有帮助 		  
*/
#include<iostream> // 无聊的逗o((⊙﹏⊙))o. 这个题要细心 
using namespace std;
int a[20] = {0}, b[40000] = {0}; 
//a数组 内容放置 初始木棍长度 
//b数组 坐标 代表 状态数 ，内容放置 此状态下的木棍总长度 
int main()
{
	int n;
	cin>>n;
	for(int i = 0;i<n;i++)
	cin>>a[i]; // 输入 
	
	for(int i = 0;i<(1<<n);i++) // 将木棍的长度加到 b 数组中 ， 1<<n  = 2^n
	for(int j = 0;j<n;j++)
		if(i&(1<<j)) { b[i] += a[j];} 
		
		/*
		这个条件语句要在二进制的角度思考 
		逻辑为 若下表为 j 的木棍 属于 下表 为 i 的状态 ，
		就将该木棍的长度加到 b 数组中
			
		(& 这里是 按位与符号。 
		比如二进制数 1000 & 1001 结果就是 1 ，1000 & 0110 结果为 0
		强烈建议大家搜一下 按位与运算 ，这里不再赘述。)
		
		围绕这个条件语句举个例子，
		 i = 3 时 二进制为 0011,  
		 
		在 	for(int j = 0;j<n;j++) 中 1<<j 的值如下： 
		1<<0 = 2^0  = 1 化为 0001,……1<<3 = 8 化为 1000。。
		（不难发现， j 的每个取值都有不同位置的 “1”与之对应 ，
		 因此实现了不同的状态组合） 
		 
	 	按位与运算中，当j = 0 和 1 的时候符合，那么b[3] = a[0]+a[1]	;
		 	  
		*/
		
	 /*找到 不同状态（无重复的木棍）的组合 
	 并且 木棍总长度相等的 最大值 */
	int result = 0;
	for(int i = 0;i<(1<<n);i++)
	for(int j = 0;j<(1<<n);j++)
		if(!(i&j)&&b[i] == b[j]) // 同样应用了按位与运算 
		{
			result = result>=b[i] ? result : b[i]; //  ? ：表达式 ，不再赘述。 
		}
	
	cout<<result;
	
	return 0;
}

下面是不加注释的代码。

#include<iostream> 
using namespace std;
int a[20] = {0}, b[40000] = {0}; 
int main()
{
	int n;
	cin>>n;
	for(int i = 0;i<n;i++)
	cin>>a[i];
	
	for(int i = 0;i<(1<<n);i++)
	for(int j = 0;j<n;j++)
		if(i&(1<<j)) { b[i] += a[j];} 

	int result = 0;
	for(int i = 0;i<(1<<n);i++)
	for(int j = 0;j<(1<<n);j++)
		if(!(i&j)&&b[i] == b[j]) 
		{
			result = result>=b[i] ? result : b[i];
		}
	
	cout<<result;
	
	return 0;
}