[JOIST 2025 Day3] 多方通信题解

FFTotoro · 2025-03-26 17:18:50 · 题解

思路提供自 @0x824EE 大佬。

很智慧的题。N=4 的构造较为简单，在此略过。

考虑 N=32 怎么做。建出一棵二叉索引树（又称“树状数组”），方便之后的求解。

不妨让每个结点在经过某些预处理后的所有轮次中，在自己的黑板上写的字母固定。尝试预处理这样的信息：一个结点在之后的轮次中黑板上的字母为 \texttt{T}，当且仅当其子树内含有“Parent”。使用如下的策略进行预处理：对于一个结点 u，它应该在预处理的过程中，在儿子的信息处理完之后，读取它的儿子的信息（某个儿子信息处理完，它直接在下一轮读取），并根据儿子的信息修改自己的信息。特别地，我们不需要处理结点 N 的信息，因为之后的过程中并不需要它。这总共需要 \log_2N-1=4 轮。

接着在树上二分，假设当前确定的区间为 [L,R]，令中点 M=\left\lfloor\frac{L+R}{2}\right\rfloor，查询“Parent”是否在 [L,M] 之间（由于 N=32 的特殊性，每个查询的区间必然都对应一棵子树）。这总共需要 \log_2N=5 轮。

但是限定的次数为 8 轮，而我们需要 4+5=9 轮！观察到在预处理的时候，都是父亲在读取儿子的信息，有一些东西被浪费了。

考虑“父亲读取儿子信息”的本质，其实就相当于对于一个区间 [L,R]，设其中点为 M=\left\lfloor\frac{L+R}{2}\right\rfloor，在某一轮中将 M 的信息传到了 R 上。由于只需要压掉一个轮数，所以考虑在预处理的每一轮中，使 [L,M] 都读取 R 的信息、[M+1,R] 都读取 M 的信息（但是不一定要修改自己的信息），这样就可以免去二分的第一次（因为这样所有人都可以推断出“Parent”在 \left[1,\frac{N}{2}\right] 还是 \left[\frac{N}{2}+1,N\right] 里）。于是成功地把轮数压进了 8，并且这种“合并区间”的思路还意外地使写法变得简洁了很多，一个递归就可以实现。

尝试把思路拓展到 N=48。48 没有 32 那么良好的性质，但是可以敏锐地发现 48=16\times 3，并且相较于 N=32 多给了一轮次数（即可以传递 9 轮信息）。沿用原来的思路处理 [1,16]、[17,32] 和 [33,48] 的子树信息，使用多出来的那一轮次数，让所有结点都知道“Parent”在三棵子树中的哪一棵中（只需要在另外两棵子树中随便选一棵询问）。然后按照原来的方法在目标子树内二分即可。

下面给出 N=48 时生成答案的代码，仅供参考。另外本人编写了一个简易版 SPJ（只能判断你的答案是否合法，并不能根据 N 和 L 来判断你的得分），方便大家调试，各位可以自行取用。

生成答案代码：

#include<bits/stdc++.h>
using namespace std;
inline int lowbit(int x){
  return x&-x;
}
int main(){
  freopen("output_03.txt","w",stdout);
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n=48,l=9; cout<<l<<endl;
  for(int i=1;i<=n;i++){
    cout<<i<<endl;
    vector C(n+1,vector<char>(l,'F'));
    vector P(n+1,vector<int>(l));
    function<void(int,int,int)> dfs=[&](int l,int r,int d){
      if(l==r)return;
      int m=l+r>>1;
      dfs(l,m,d-1),dfs(m+1,r,d-1);
      for(int j=l;j<=m;j++)
        P[j][d]=r;
      for(int j=m+1;j<=r;j++)
        P[j][d]=m;
      for(int j=l;j<=r;j++)
        if(C[j][d]=='F')C[j][d]=d?C[j][d-1]:(j==i?'T':'F');
      if(C[m][d]=='T')C[r][d+1]='T';
    }; // 递归预处理信息
    dfs(1,n/3,3),dfs(n/3+1,n/3*2,3),dfs(n/3*2+1,n,3);
    for(int i=1;i<=n/3;i++)
      if(P[i][4]=n;C[i][4]=='F')C[i][4]=C[i][3];
    for(int i=n/3+1;i<=n;i++)
      if(P[i][4]=n/3;C[i][4]=='F')C[i][4]=C[i][3];
    int x,y;
    if(i<=n/3)x=1,y=n/3;
    else if(i<=n/3*2)x=n/3+1,y=n/3*2;
    else x=n/3*2+1,y=n;
    for(int j=5;j<l;j++){
      for(int p=1;p<=n;p++)
        C[p][j]=C[p][j-1];
      int m=x+y>>1;
      for(int p=1;p<=n;p++)
        P[p][j]=m;
      if(i<=m)y=m;
      else x=m+1;
    } // 二分过程
    for(int j=1;j<=n;j++,cout<<endl)
      for(int k=0;k<l;k++)
        cout<<C[j][k]<<' '<<P[j][k]<<' ';
  }
  return 0;
}

Special Judge：

#include<bits/stdc++.h>
using namespace std;
int main(){
  freopen("output_03.txt","r",stdin);
  int n=48,l; cin>>l;
  vector c(n,vector(n,vector<char>(l)));
  vector p(n,vector(n,vector<int>(l)));
  for(int i=0;i<n;i++){
    int x; cin>>x;
    for(int j=0;j<n;j++)
      for(int k=0;k<l;k++)
        cin>>c[i][j][k]>>p[i][j][k],p[i][j][k]--;
  }
  bool f1=true,f2=true;
  for(int x=0;x<n;x++)
    for(int y=0;y<n;y++)
      if(x!=y){
        for(int a=0;a<n;a++){
          string s=(a==x?"T":"F"),t=(a==y?"T":"F");
          for(int i=0;i<l;i++){
            if(s==t)f1&=c[x][a][i]==c[y][a][i]&&p[x][a][i]==p[y][a][i];
            s+=c[x][p[x][a][i]][i],t+=c[y][p[y][a][i]][i];
          }
          f2&=s!=t;
        }
      }
  cout<<"Condition 1: "<<(f1?"Yes\n":"No\n");
  cout<<"Condition 2: "<<(f2?"Yes\n":"No\n");
  cout<<(f1&&f2?"Accepted\n":"Wrong Answer\n");
  return 0;
}

[JOIST 2025 Day3] 多方通信 题解

[JOIST 2025 Day3] 多方通信题解