题解：CF2096G Wonderful Guessing Game
maxiaomeng
·
·
题解
分析
我们先不考虑必须先提出所有查询和忽略一个询问这两个条件。
这样一来，题目和小学数学中的找假币问题十分相似。
因此我们可以用类似的做法做：
-
将 n 个数平均分成 3 个区间，从左到右记为 0、1、2 号区间。
-
如果余下 1 个数，就把这个数归到 2 号区间。例如：7 个数分为 [1,2]，[3,4]，[5,7] 三个区间。
-
如果余下 2 个数，假设除去两个数后区间长度除以 3 为 len，那么划分成：[1, len+1]，[len+2,2len+2]，[2len+3,3len+2]。例如：8 个数分为 [1,3]，[4,6]，[7,8] 三个区间。
-
再对 0 和 1 拼起来两个区间进行查询，结果为 L 则在 0 号区间，为 R 则在 1 号区间，为 N 则在 2 号区间。再在对应区间递归询问。
这样子总共 \lceil \log_3 n\rceil 次查询，可以证明这是最小查询次数。
接下来我们考虑加入必须先提出所有查询这个条件。
我们可以根据上面解法，先建出的决策树。每个结点是一个区间，对于结点 x 的区间划分出的 0 号区间，新建一个代表该区间的结点并向它连一条边权为 0 的边，对于结点 x 的区间划分出的 1 号区间，新建一个代表该区间的结点并向它连一条边权为 1 的边，以此类推。
当一个结点区间长度为 1 却没到最大深度（即 \lceil \log_3 n\rceil）时，钦定它有一个 2 号区间，这个区间就是它自己。
每一次询问，将每一层的所有 0 区间结点合在一起，1、2 号区间也是一样。然后对于每一层，将结合后的 0 区间和结合后的 1 区间拼在一起，询问这个东西。如果是结果为 L 则在 0 号区间，为 R 则在 1 号区间，为 N 则在 2 号区间。
也就是说，每一层的询问结果相当于一个“跳结点指令”，当跳到该层的结点时，为 L 则跳到这个结点的 0 号区间，为 R 跳到这个结点的 1 号区间，为 N 跳到这个结点的 2 号区间。
在决策树上，按照指令从根往下跳就能知道答案。
最后我们考虑忽略一个查询的条件，这时要再加一个查询，以便能够还原被忽略的查询。
考虑对于每个叶子结点，将根结点到每个叶子结点的边编号加起来对 3 取模。
如果这个模数为 x，钦定这个结点放在这次询问的 x 号区间。
可以注意到，三种编号有两种数量相同，将数量相同的两个编号映射到 0,1 号区间，另一个映射到 2 号区间，对映射后的查询完再映射回来即可。接着对映射后 0 和 1 两个区间拼起来进行查询，结果为 L 则在 0 号区间，为 R 则在 1 号区间，为 N 则在 2 号区间。
下面需要证明三种编号有两种数量相同。如证明无法理解可跳过。
证明
令 f_{i,j} 表示 n 个数的决策树，根结点到每个叶子结点的边编号加起来模 3 余 j 的数个数。则此命题即为：对于任意正整数 n 有 f_{n,0},f_{n,1},f_{n,2} 有两个相等。
（因为 n>1，为方便，n=1 时决策树最大深度为 2 而不是 1。）
为证明该命题，需要证明一个显然更强的命题：在原命题的基础上，如果 n \bmod 3=0，则 f_{n,0}=f_{n,1}=f_{n,2}，否则如果 n \bmod 3=2 则 f_{n,0}+f_{n-1,0}=f_{n,1}+f_{n-1,1}=f_{n,2}+f_{n-1,2}。
使用数学归纳法。
当 n=1,2 时已成立。当 n\ge 3 时，假设 1 到 n-1 时已成立，则有：
当 n \bmod 3=0 时
我们有：
\begin{cases}
f_{n,0}=f_{\lfloor \frac{n}3 \rfloor,0}+f_{\lfloor \frac{n}3 \rfloor,2}+f_{\lfloor \frac{n}3 \rfloor,1} \\
f_{n,1}=f_{\lfloor \frac{n}3 \rfloor,1}+f_{\lfloor \frac{n}3 \rfloor,0}+f_{\lfloor \frac{n}3 \rfloor,2} \\
f_{n,2}=f_{\lfloor \frac{n}3 \rfloor,2}+f_{\lfloor \frac{n}3 \rfloor,1}+f_{\lfloor \frac{n}3 \rfloor,0}
\end{cases}
则 f_{n,0}=f_{n,1}=f_{n,2}，命题成立。
当 n \bmod 3=2 时
我们有：
\begin{cases}
f_{n,0}=f_{\lfloor \frac{n}3 \rfloor+1,0}+f_{\lfloor \frac{n}3 \rfloor+1,2}+f_{\lfloor \frac{n}3 \rfloor,1}\\
f_{n,1}=f_{\lfloor \frac{n}3 \rfloor+1,1}+f_{\lfloor \frac{n}3 \rfloor+1,0}+f_{\lfloor \frac{n}3 \rfloor,2}\\
f_{n,2}=f_{\lfloor \frac{n}3 \rfloor+1,2}+f_{\lfloor \frac{n}3 \rfloor+1,1}+f_{\lfloor \frac{n}3 \rfloor,0}
\end{cases}
且有：
\begin{cases}
f_{n-1,0}=f_{\lfloor \frac{n}3 \rfloor,0}+f_{\lfloor \frac{n}3 \rfloor,2}+f_{\lfloor \frac{n}3 \rfloor+1,1} \\
f_{n-1,1}=f_{\lfloor \frac{n}3 \rfloor,1}+f_{\lfloor \frac{n}3 \rfloor,0}+f_{\lfloor \frac{n}3 \rfloor+1,2} \\
f_{n-1,2}=f_{\lfloor \frac{n}3 \rfloor,2}+f_{\lfloor \frac{n}3 \rfloor,1}+f_{\lfloor \frac{n}3 \rfloor+1,0} \\
\end{cases}
不妨将 f_{n,0},f_{n,1},f_{n,2} 同时减去一个数，f_{n-1,0},f_{n-1,1},f_{n-1,2} 同时减去一个数。
由式子的对称性，如果 \lfloor \frac{n}3\rfloor+1 \bmod 3=2 则不妨设：
\begin{cases}
f_{\lfloor \frac{n}3 \rfloor,0}=f_{\lfloor \frac{n}3 \rfloor,1}=0,f_{\lfloor \frac{n}3 \rfloor,2}=d \\
f_{\lfloor \frac{n}3 \rfloor+1,0}=f_{\lfloor \frac{n}3 \rfloor+1,1}=0,f_{\lfloor \frac{n}3 \rfloor+1,2}=-d
\end{cases}
则 f_{n,0}=f_{n,2}=-d,f_{n,2}=d，f_{n,0}=f_{n,2}=d,f_{n,2}=-d，f_{n,0}+f_{n-1,0}=f_{n,1}+f_{n-1,1}=f_{n,2}+f_{n-1,2}=0，命题成立。
如果 \lfloor \frac{n}3\rfloor+1 \bmod 3=1 则不妨设:
\begin{cases}
f_{\lfloor \frac{n}3 \rfloor,0}=f_{\lfloor \frac{n}3 \rfloor,1}=0,f_{\lfloor \frac{n}3 \rfloor,2}=0 \\
f_{\lfloor \frac{n}3 \rfloor+1,0}=f_{\lfloor \frac{n}3\rfloor+1,1}=0,f_{\lfloor \frac{n}3 \rfloor+1,2}=d
\end{cases}
如果 $\lfloor \frac{n}3\rfloor+1 \bmod 3=0$，此情况与$\lfloor \frac{n}3\rfloor+1 \bmod 3=1$ 对称，命题成立。
因此，更强的命题成立，原命题也成立。
## 代码
```cpp
#include<bits/stdc++.h>
#define int long long
#define __builtin_popcount __builtin_popcountll
using namespace std;
const int N=200005,M=25;
int n,m,q,cnt,a[M][N],w[N],cw[M],z;
struct node{
int l,r,son[3];
}tree[N<<2];
void build(int x,int l,int r,int d,int e){
tree[x].l=l;
tree[x].r=r;
for(int i=l;i<=r;i++){
a[d][i]=e;
}
if(d==m)return;
int len=r-l+1;
if(len==1){
tree[x].son[2]=++cnt;
build(tree[x].son[2],l,l,d+1,2);
return;
}
if(len==2){
tree[x].son[0]=++cnt;
tree[x].son[1]=++cnt;
build(tree[x].son[0],l,l,d+1,0);
build(tree[x].son[1],r,r,d+1,1);
return;
}
for(int i=0;i<3;i++)tree[x].son[i]=++cnt;
switch(len%3){
case 0:{
int w=len/3;
build(tree[x].son[0],l,l+w-1,d+1,0);
build(tree[x].son[1],l+w,r-w,d+1,1);
build(tree[x].son[2],r-w+1,r,d+1,2);
break;
}
case 1:{
int w=len/3;
build(tree[x].son[0],l,l+w-1,d+1,0);
build(tree[x].son[1],l+w,l+w+w-1,d+1,1);
build(tree[x].son[2],l+w+w,r,d+1,2);
break;
}
case 2:{
int w=len/3;
build(tree[x].son[0],l,l+w,d+1,0);
build(tree[x].son[1],l+w+1,l+w+w+1,d+1,1);
build(tree[x].son[2],l+w+w+2,r,d+1,2);
break;
}
}
}
inline int tonum(char c){
if(c=='L')return 0;
else if(c=='R')return 1;
else return 2;
}
inline int skip(string&s){
int x=1;
for(int i=1;i<=m;i++){
x=tree[x].son[tonum(s[i])];
}
return tree[x].l;
}
inline void solve(){
cin>>n;
cnt=1,m=0;
for(int i=1;i<=20;i++)for(int j=1;j<=n;j++)a[i][j]=w[j]=0;
cw[0]=cw[1]=cw[2]=0;
for(int p=1;p<n;p*=3)++m;
build(1,1,n,0,0);
cout<<m+1<<endl;
for(int i=1;i<=m;i++){
int c=0;
for(int j=1;j<=n;j++)if(a[i][j]!=2)++c;
cout<<c<<' ';
for(int j=1;j<=n;j++)if(a[i][j]==0)cout<<j<<' ';
for(int j=1;j<=n;j++)if(a[i][j]==1)cout<<j<<' ';
for(int j=1;j<=n;j++)(w[j]+=a[i][j])%=3;
cout<<endl;
}
for(int i=1;i<=n;i++)++cw[w[i]];
if(cw[0]==cw[1])z=0;
else if(cw[0]==cw[2])z=1;
else z=2;
for(int i=1;i<=n;i++)(w[i]+=z)%=3;
int c=0;
for(int j=1;j<=n;j++)if(w[j]!=2)++c;
cout<<c<<' ';
for(int j=1;j<=n;j++)if(w[j]==0)cout<<j<<' ';
for(int j=1;j<=n;j++)if(w[j]==1)cout<<j<<' ';
cout<<endl;
string s;
cin>>s;
s=' '+s;
int f=0,sum=0,sum2=0;
for(int i=1;i<=m;i++){
if(s[i]=='?'){
f=i;
}else{
(sum2+=tonum(s[i]))%=3;
}
}
if(f){
sum=(tonum(s[m+1])+3-z)%3;
s[f]="LRN"[(sum+3-sum2)%3];
}
cout<<skip(s)<<'\n';
}
signed main(){
cin>>q;
while(q--)solve();
return 0;
}
```