二进制--状态压缩_dart 二进制流压缩-CSDN博客

本文介绍了一种算法问题：给定N种包含两种食物的营养套餐，如何选择每种套餐中的一种食物，使得所有选中食物的营养价值通过异或运算得到的最大值。文章提供了完整的代码实现，并通过示例说明了算法的工作原理。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Description

现推出了N(N <= 20)种营养套餐，每一种套餐包含两种食物，
这两种食物各自包含有自己的营养价值x（0 <= x <= 1e6）,
怎样从在这N种套餐中，每种套餐中选择一种食物，
使得最后这些食物的营养价值异或和sum最大
(N个数的异或和是指N个数相异或的结果，一个数的异或和为自身)。

Input
第一行一个整数T（T <= 5）代表测试数据组数
接下来每组测试数据第一行为一个整数N（N <= 20）代表套餐的种类数
接下来N行，每行为两个整数x, y(0 <= x, y <= 1e6),代表一种套餐的两种食物的营养价值
Output
对于每组测试数据，输出一个整数,代表题意中的sum
Sample Input
2
2
3 4
4 5
2
9 6
2 2
Sample Output
7
11
HINT
第一组样例中第一种套餐选择3，
第二种选择4,此时异或和3xor4 = 7最大，故输出7.

include


tdc++.h>
using namespace std;
int T;
int n;
const  int maxn = 20;
int x[maxn], y[maxn];
int up;
int Max = -1;

int main()
{
    freopen("debug.txt", "r", stdin);
    freopen("test.txt", "w", stdout);
    scanf("%d", &T);
    while(T--)
    {
        int Max = -1;
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
            scanf("%d%d", &x[i], &y[i]);
        up = 1<<n;
        for(int j = 0; j < up; j++)
        {
            int now = 0;
            for(int k = 0; k < n; k++)
            {
                int num = (j>>k)&1;
                if(num) now ^= x[k];
                else now ^= y[k];
            }
        Max = max(Max, now);
        }
        printf("%d\n", Max);
    }
    return 0;
}