HDU 5536 Chip Factory（暴力+优化）

偏执的太偏执、 2022-06-08 09:57 134阅读 0赞

John is a manager of a CPU chip factory, the factory produces lots of chips everyday. To manage large amounts of products, every processor has a serial number. More specifically, the factory produces n n chips today, the i i\-th chip produced this day has a serial number si si.  
  
At the end of the day, he packages all the chips produced this day, and send it to wholesalers. More specially, he writes a checksum number on the package, this checksum is defined as below:

maxi,j,k(si\+sj)⊕sk maxi,j,k(si+sj)⊕sk

which i,j,k i,j,k are three **different** integers between 1 1 and n n. And ⊕ ⊕ is symbol of bitwise XOR.  
  
Can you help John calculate the checksum number of today?

Input

The first line of input contains an integer T T indicating the total number of test cases.  
  
The first line of each test case is an integer n n, indicating the number of chips produced today. The next line has n n integers s1,s2,..,sn s1,s2,..,sn, separated with single space, indicating serial number of each chip.  
  
1≤T≤1000 1≤T≤1000  
3≤n≤1000 3≤n≤1000  
0≤si≤109 0≤si≤109  
There are at most 10 10 testcases with n>100 n>100

Output

For each test case, please output an integer indicating the checksum number in a line.

Sample Input

2
    3
    1 2 3
    3
    100 200 300

Sample Output

6
    400

题解：

题意：

给你一个序列，找出三个不同的i，j，k，使得(a\[i\]+a\[j\])^a\[k\]最大

思路：

暴力+一些剪枝可以过

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    #define ll long long
    #define INF 100861111
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    using namespace std;
    int a[1005];
    int main()
    {
        int i,j,k,d,test,maxx,n;
        scanf("%d",&test);
        while(test--)
        {
            scanf("%d",&n);
            maxx=0;
            for(i=0;i<n;i++)
                scanf("%d",&a[i]);
            for(i=0;i<n;i++)
            {
                for(j=i+1;j<n;j++)
                {
                    for(k=j+1;k<n;k++)
                    {
                        maxx=max(maxx,(a[i]+a[j])^a[k]);
                        maxx=max(maxx,(a[j]+a[k])^a[i]);
                        maxx=max(maxx,(a[i]+a[k])^a[j]);
                    }
                }
            }
            printf("%d\n",maxx);
        }
    
    }