CF1163E Magical Permutation

亦凉 2021-12-22 16:45 151阅读 0赞

题意：给定集合，求一个最大的x，使得存在一个0 ~ 2x \- 1的排列，满足每相邻的两个数的异或值都在S中出现过。Si <= 2e5

解：若有a，b，c，令S1 = a ^ b, S2 = b ^ c，则有a ^ c = S1 ^ S2

因为有0存在，所以每个数都能表示成它到0路径上的所有间隔的异或和，也就是每个数都能被表示出来。我们用线性基来判断。

找到最大的x之后，我们可以发现，线性基中x个数的2x种选法一一对应这2x个数。于是直接采用格雷码来找这个排列，每加一位，就在x个数中添加 / 删除一个数到异或集合中。

我的实现较复杂。实际上只要把线性基这x个数记下来，格雷码的时候选择是否异或即可。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 
     3 const int N = 500010;
     4 
     5 int n, a[N], base[64], T, id[64], sta[N], pos[N], s;
     6 
     7 inline void clear() {
     8     memset(base, 0, sizeof(base));
     9     memset(id, 0, sizeof(id));
    10     return;
    11 }
    12 
    13 inline void insert(int x, int v) {
    14     int V = 0;
    15     for(int i = T - 1; i >= 0; i--) {
    16         if(!((x >> i) & 1)) {
    17             continue;
    18         }
    19         if(base[i]) {
    20             x ^= base[i];
    21             V ^= id[i];
    22         }
    23         else {
    24             base[i] = x;
    25             id[i] = V | (1 << i);
    26             break;
    27         }
    28     }
    29     return;
    30 }
    31 
    32 inline bool check() {
    33     for(int i = T - 1; i >= 0; i--) {
    34         if(!base[i]) {
    35             return false;
    36         }
    37     }
    38     return true;
    39 }
    40 
    41 inline void find(int x) {
    42     int t = x;
    43     for(int i = T - 1; i >= 0; i--) {
    44         if(!((x >> i) & 1)) {
    45             continue;
    46         }
    47         x ^= base[i];
    48         sta[t] ^= id[i];
    49     }
    50     return;
    51 }
    52 
    53 void DFS(int k) {
    54     if(k == -1) {
    55         printf("%d ", pos[s]);
    56         return;
    57     }
    58     DFS(k - 1);
    59     s ^= 1 << k;
    60     DFS(k - 1);
    61     return;
    62 }
    63 
    64 int main() {
    65     scanf("%d", &n);
    66     for(int i = 1; i <= n; i++) {
    67         scanf("%d", &a[i]);
    68     }
    69     std::sort(a + 1, a + n + 1);
    70     int fin = 0;
    71     for(T = 0; T <= 18; T++) {
    72         int lm = (1 << T) - 1;
    73         clear();
    74         for(int i = 1; i <= n && a[i] <= lm; i++) {
    75             insert(a[i], i);
    76         }
    77         if(check()) {
    78             fin = T;
    79         }
    80     }
    81     T = fin;
    82     /// T 
    83     int lm = (1 << T) - 1;
    84     for(int i = 1; i <= lm; i++) {
    85         find(i);
    86         pos[sta[i]] = i;
    87     }
    88     printf("%d\n", T);
    89     DFS(T - 1);
    90     puts("");
    91     return 0;
    92 }

AC代码

转载于:https://www.cnblogs.com/huyufeifei/p/11097417.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/11c23f6a04d249d6b5a72a098e0b8928.png