同为LOJ 2866

题目叙述

一共有 \(n\) 个触发器，每个触发器可以走到另一个器件。还有若干个开关，每个开关有两种出口。还有一个起点。
现在有一个球从起点出发，沿着线路走。开关有两种状态X和Y，如果在状态X必须走第一个出口，否则走第二个。一个开关被走一次之后会切换状态。现在 \(n\) 个触发器的经过顺序规定（可能重复），请给出构造使得满足这个条件。开关数量不能超过 \(n+\log_2 n\)

题解

一个开关有两个叉，而且只有开关有分叉。所以必须通过开关来实现触发器需要重复这件事情。
为什么是两个叉，是因为实际上题目想要你构造一个二叉树。但好像这题改成三叉树也可以。
考虑一颗完美二叉树，每个叶子节点连接根。可以发现，这样遍历叶子顺序是按照 \(rev_i\) 遍历的。但是最坏情况下，二叉树节点数量大概是 \(2n\) 。
考虑优化。发现一个节点如果两个子树内一个叶子都没有，那么直接让这个节点链接根即可。

反思

一般来说构造题会给很大的自由度给我们造成迷惑。因此应当自己限定一下构造的东西。比如构造一棵二叉树。另外时常思考一下剪枝。还有信息的重复利用。

代码

#include "doll.h"
#include <algorithm>
#include <iostream>
using namespace std;
const int MN=2e5+5;
int ls[MN*2],rs[MN*2],id[MN*2],len,n,totnode,rev[MN*2];
int build(int l,int r){
  if(r<len-n)return -1;
  if(l==r)return id[l];
  int mid=(l+r)>>1,ret=++totnode;
  ls[ret]=build(l,mid),rs[ret]=build(mid+1,r);
  return -ret;
}
void create_circuit(int M, vector<int> A) {
  A.push_back(0);
  len=1;
  n=A.size();
  while(len<n)len<<=1;
  for(int i=1;i<len;++i)rev[i]=(rev[i>>1]>>1)|((i&1)?(len>>1):0);
  static int tmp[MN*2];
  for(int i=len-n;i<len-1;++i)tmp[i-(len-n)]=i;
  sort(tmp,tmp+n-1,[](const int &x,const int &y){return rev[x]<rev[y];});
  for(int i=0;i<len;++i)id[i]=-1;
  for(int i=0;i<n-1;++i)id[tmp[i]]=A[i];
  id[len-1]=0;
  build(0,len-1);
  answer(vector<int>(M+1,-1),vector<int>(ls+1,ls+totnode+1), vector<int>(rs+1,rs+totnode+1));
}