首页 > 代码库 > BZOJ 4269: 再见Xor

BZOJ 4269: 再见Xor

2024-09-02 21:11:57   217人阅读

4269: 再见Xor

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 265  Solved: 159
[Submit][Status][Discuss]

Description

给定N个数，你可以在这些数中任意选一些数出来，每个数可以选任意多次，试求出你能选出的数的异或和的最大值和严格次大值。

 

Input

第一行一个正整数N。
接下来一行N个非负整数。

 

Output

一行，包含两个数，最大值和次大值。

 

Sample Input

3
3 5 6

Sample Output

6 5

HINT

 

100% ： N <= 100000, 保证N个数不全是0，而且在int范围内

 

Source

 
[Submit][Status][Discuss]

 

又是一道线性基，先求出一组线性基，这组线性基的异或和就是最大值，再异或一下其中最小的，就是最小值了。

 

 1 #include <cstdio> 2  3 template <class T> 4 __inline void swap(T &a, T &b) 5 { 6     static T c; 7     c = a; 8     a = b; 9     b = c;10 }11 12 const int mxn = 100005;13 14 int n, a[mxn], b[mxn], c;15 16 signed main(void)17 {18     scanf("%d", &n);19     20     for (int i = 1; i <= n; ++i)21         scanf("%d", a + i);22     23     for (int i = 1; i <= n; ++i)24     {25         for (int j = n; j > i; --j)26             if (a[i] < a[j])27                 swap(a[i], a[j]);28         29         if (a[i])30             ++c;31         else32             break;33         34         for (int j = 31; ~j; --j)35             if ((a[i] >> j) & 1)36             {37                 b[i] = j;38                 39                 for (int k = 1; k <= n; ++k)40                     if (k != i && (a[k] >> j) & 1)41                         a[k] ^= a[i];42                 43                 break;44             }45     }46     47     int ans = 0;48     49     for (int i = 1; i <= c; ++i)50         ans ^= a[i];51     52     printf("%d %d\n", ans, ans ^ a[c]);53 }

 

@Author: YouSiki

 

BZOJ 4269: 再见Xor


联系
我们