CF1163E Magical Permutation

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

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

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

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

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

 #include <bits/stdc++.h>

 const int N = ;

 int n, a[N], base[], T, id[], sta[N], pos[N], s;

 inline void clear() {

     memset(base, , sizeof(base));

     memset(id, , sizeof(id));

     return;

 }

 inline void insert(int x, int v) {

     int V = ;

     for(int i = T - ; i >= ; i--) {

         if(!((x >> i) & )) {

             continue;

         }

         if(base[i]) {

             x ^= base[i];

             V ^= id[i];

         }

         else {

             base[i] = x;

             id[i] = V | ( << i);

             break;

         }

     }

     return;

 }

 inline bool check() {

     for(int i = T - ; i >= ; i--) {

         if(!base[i]) {

             return false;

         }

     }

     return true;

 }

 inline void find(int x) {

     int t = x;

     for(int i = T - ; i >= ; i--) {

         if(!((x >> i) & )) {

             continue;

         }

         x ^= base[i];

         sta[t] ^= id[i];

     }

     return;

 }

 void DFS(int k) {

     if(k == -) {

         printf("%d ", pos[s]);

         return;

     }

     DFS(k - );

     s ^=  << k;

     DFS(k - );

     return;

 }

 int main() {

     scanf("%d", &n);

     for(int i = ; i <= n; i++) {

         scanf("%d", &a[i]);

     }

     std::sort(a + , a + n + );

     int fin = ;

     for(T = ; T <= ; T++) {

         int lm = ( << T) - ;

         clear();

         for(int i = ; i <= n && a[i] <= lm; i++) {

             insert(a[i], i);

         }

         if(check()) {

             fin = T;

         }

     }

     T = fin;

     /// T

     int lm = ( << T) - ;

     for(int i = ; i <= lm; i++) {

         find(i);

         pos[sta[i]] = i;

     }

     printf("%d\n", T);

     DFS(T - );

     puts("");

     return ;

 }

AC代码

巴特西

CF1163E Magical Permutation

最新文章

热门文章