Atcoder agc057

發表於 更新於 分類於 ， Disqus： 文章字數： 1.7k 所需閱讀時間 ≈ 6 分鐘
C (trie树, bit flip)

C

https://atcoder.jp/contests/agc057/tasks/agc057_c

0~ 2^N - 1的排列

问能否通过多次任选操作(每次操作独立,在上一次操作结果基础上), 让数列单调递增, 给出方案

操作1: a[i] = (a[i]+1)%(2^n) , 所有值循环+1

操作2: a[i] = a[i] xor x , 选定一个值,所有值异或它

限制

n<=18

我的思路

显然连续的异或没意义,甚至题目可以改成不是+1,+任意

所以问题变成 穿插的正数个+1和xor能否让数列单调递增, 若能给出方案

考虑所有+1/xor 末尾是1, 都是让所有末尾翻转, 因此结论是 末位前两个互为0/1,后面循环这两个

同理考察第二位,发现(0和2)(1和3)两对,互为0/1,后面的同样按照4个一组循环

同理考察第三位,发现(0和4)(1和5)(2和6)(3和7)四对,互为0/1,后面的同样按照8个一组循环

换句话说, 最低位1个自由元,其它由它决定,第2低位两个自由元,剩余的也是由它决定,第低3位4个自由元,低4位8个自由元…

我想先弄好一部分位再弄剩下的,从高位到低位或从低位到高位,但是 没想到实际怎么操作

题解

设计结构

trie tree

先不看方框, 看树上的边, 从根向叶子的方向, 对应值的从低到高的位

然后关注叶子方框,例如上面的6,二进制下是110,和它的路径是一样的

再看带有n的方框,意思是如果从树上截取某个点作为根来看,如果根表示的是n,那么一条边权是0子节点是2n+0,边权是1的子节点是2n+1, 注意的是这里并不是左右节点,而是由边权决定的

树的结构建好以后, 那么把叶子中再填入初始每个值所在的位置,完成初始化

接下来看+1和xor操作对树进行怎样的修改

+1

+1

因为我们的树是越接近根,对应的位越低,所以+1带来的进位效果也是从根向叶子前进的

如果我们以改变树上边的权值,而不是改变左右指向的视角来看,

那么对于根

0变成1

1变成0且它的子树受到和根一样的处理

这样发现改动的实际上只有log级别个

xor

xor

xor 比 +1 其实好观察,

对于xor二进制对应位为1的层级的0变成1,1变成0

实现

现在我们再回头看目标呢, 也就是位置上和它对应的值是一样的

这里可以思考为啥,是按边上的值来描述而不是左右描述的, 考虑不按照涂上那样初始摆,而是按照叶子直接放初始的值,比如这里0 4 2 6 1 5 3 7位置上对应的值, 在放值时就能明确的知道冲突的情况,排除一些不可能

问题变成了,如何让二叉树边上的0/1 变回 完全二叉树的位置对应的值

考虑把叶子变成 0,1 序列.

如果叶子是反着的1,0, 那么只需要把上面的路径变成 从根到它都是1,这样+1 就能完成修正

修正了所有叶子以后, 问题来了, 还可以通过+1/xor的组合修正非叶子吗

1
2
3
   1       0
 1   0   0   1 ( 其它位还有 不是xor 能解决的情况
0 1 0 1 0 1 0 1 ( 高位全部0,1顺序了

证明不可能, 首先 这种情况, 如果能修正,必定是奇数次操作到该层, 因为 xor不改相对一致性,+每次操作到这两个中的一个就会改,所以这两个操作次数总和必为奇数,考虑它们所覆盖的叶子节点,总操作次数也为奇数

因此要么 xor翻转能得到,要么就是不可能

从逻辑上, 已经完成了,还有个实现问题,如果通过枚举导数第二层,再模拟xor和+1, 虽然+1代价小,但是xor的代价可能达到O(n)的级别, 总的会变成n方

简单的增加一个翻转标识记录行的翻转状态, 因为+1是对单个点翻转,xor是行翻转,翻转两次等于未翻转,都是翻转,所以+1直接让对应位置的节点翻转, 而xor 通过行标识记录,

代码

https://atcoder.jp/contests/agc057/submissions/31596691

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

const int N = 262144;

vector<int> lr(N*4+10,-1); // -1 unset 0:01, 1:10

int a[N+10];

int n;
bool build(int pos,int val,int idx = 1,int pwr = 0){
  if(pwr == n)return true;
  int direction = pos%2;
  int v = direction != val%2;
  if(lr[idx] != -1 && lr[idx] != v){
    return false;
  }
  lr[idx] = v;
  return build(pos/2,val/2,idx*2+direction,pwr+1);
}

int xorcache[20] = {0}; // 不要实际的xor, 修改代价大

vector<int>ans;

void fix(int val){
  // printf("Fix %d\n",val);
  int x = 0;
  {
    int pwr = n-1;
    int v = val;
    while(pwr--){
      if(v%2 == (lr[v/2] ^ xorcache[pwr])){
        x |= (1<<(pwr));
      }
      v/=2;
    }
  }
  // printf("xor %d\n",x);
  if(x){
    ans.push_back(x);
    rep(pwr,0,n){
      if((1<<pwr) & x)xorcache[pwr]^=1; // 标记
    }
  }
  // printf("+1\n");
  {
    int idx = 1;
    rep(pwr,0,n){
      if(lr[idx]^xorcache[pwr]){
        idx=idx*2;
      }else{
        idx=idx*2+1;
      }
      lr[idx/2] ^= 1;
    }
  }
  ans.push_back(-1);
}


int main(){
  cin>>n;
  rep(i,0,(1<<n)){
    scanf("%d",a+i);
  }
  rep(i,0,(1<<n)){
    int r = build(i,a[i]);
    if(!r){
      printf("No\n");
      return 0;
    }
  }
  // rep(i,1,8){
  //   printf("lr[%lld]= %d\n",i,lr[i]);
  // }
  rep(i,(1<<(n-1)),(1<<n)){
    if(lr[i] == 0)continue;
    fix(i);
  }
  int x = 0;
  rep(pwr,0,n){
    if(lr[1<<pwr] ^ xorcache[pwr]){
      x |= 1<<pwr;
      xorcache[pwr] ^= 1;
    }
  }
  if(x){
    ans.push_back(x);
  }
  rep(pwr,0,n){
    rep(i,(1<<pwr),(1<<(pwr+1))){
      if(lr[i]^xorcache[pwr]){
        printf("No\n");
        return 0;
      }
    }
  }
  printf("Yes\n");
  printf("%d\n",(int)ans.size());
  rep(i,0,(int)ans.size()){
    printf("%d ",ans[i]);
  }
  printf("\n");
  return 0;
}

总结

其实我的思路和题解中trie树的结论是一致的,但是我的思路不是trie树形状的,所以再往后推导的阻力更大

一个经验就是对于这种2的幂次的 xor 或 加减操作,可以放在trie树中批量操作, 比如稍微变一变, 就可以变成给你+1/-1/xor操作序列,和询问第idx位置是什么,这样多个操作询问交替的题目

参考

官方题解 https://atcoder.jp/contests/agc057/editorial/3925