题解：P11992 [JOIST 2025] 电路 2 / Circuit 2

cwfxlh · 2025-06-21 15:03:50 · 题解

P11992 [JOIST 2025] 电路 2 / Circuit 2

可能没有黑啊，感觉不太难。

先考虑没有次数限制，胡一个简单的做法。

我们尝试从上往下确定符号。考虑怎么区分一个节点是 \texttt{AND} 还是 \texttt{OR}，显然可以通过输入 01 来确认。如果是 \texttt{AND}，输出就是 0，否则是 1。但是发现，如果返回值的位置不是根节点，是无法读取返回值的。考虑怎么通过确定的元件来把这个值保留地传到根节点。如果接下来一个元件是 \texttt{OR}，在这个元件的另一侧传入 0。否则将这个返回值取反，在另一侧传入 1，同时最终的值取个反。

上面操作涉及到一个问题：怎么做到在传入固定的值。这是简单的，将子树内所有输入全部改为 0 或全部改为 1。

这样就做到了线性。确认好的点构成了一个包含根的连通块，每次加入一个儿子，可以确定这个儿子的编号。

考虑能不能更高效一点。我们每次取若干个点，判断其中有没有 \texttt{OR}，然后这样就可以二分了。发现，这些点由于不知道符号，所以它们是不适合作为传递关键信息的节点的。

尝试一点简单的结构：取若干条链，并且这些链的链头的祖先链与其他链都不相交。这样的话，对于每条链，我们尝试在链头给出返回值。具体做法如下：在链尾输入 0，然后在所有链的另一侧输入 1，这样如果里面有 \texttt{OR}，那么就会返回 1，否则返回 0。

剩下的任务就是通过一些确定的符号将这些点的信息合并传到根部。考虑树形 DP 求转移方法，dp_{i,j} 表示子树 i 内的询问点是否有 \texttt{OR} 时，返回的值是多少，要求 dp_{i,0} 与 dp_{i,1} 能够区分。通过做一些反转操作，容易发现这样是必然可以合并的。

于是我们实现了询问。考虑具体该问哪些点，尝试这样做：每次在一个点集里二分第一个 \texttt{OR}。令当前确定符号的连通块为 S，考虑所有挂在 S 上的链，选若干条长链出来，将这些长链拼在一起二分。但是这样二分的次数太多，设计一个阈值 B，每次最多选 B 个点二分。于是询问次数为 O(R\log B+\frac{n-C}{B}+\sqrt{C})。

上面询问次数的分析如下：R\log B 指每次二分出一个 \texttt{OR} 所需的次数，剩余的情况就是指询问的所有点都没问题。考虑询问的时候有多少次没问满，令这些没问满的大小和为 C，那么问满的次数就是 \frac{n-C}{B}，没问满的那些，根据长链的性质，大小一定严格递减，所以询问次数不超过 \sqrt{C}。

上面那个式子在 C 取 O(B^2) 大小的时候取到最大，不过那个界没有卡特别满，所以不需要特别精细的分析，我的代码里 B 取了 60 就过了，最多的问了 920 次左右，比较充裕。询问一次时间复杂度是 O(n) 的。

代码：

#include<bits/stdc++.h>
using namespace std;
std::string solve(int NN, int RR, std::vector<int> U, std::vector<int> V);
int query(std::string s);
int n,R,ans[20003],fa[20003],k1,k2,k3,k4,k5,k6,k7,k8,k9,mxdep[20003],qrymk[20003],rev[20003],lft,rgt,mid;
int stk[20003],tots,dp[20003][2],dep[20003];
vector<int>son[20003];
void dfs(int now){
    mxdep[now]=now;
    for(auto i:son[now]){
        if(i>=n)continue;
        dfs(i);
        if(dep[mxdep[i]]>dep[mxdep[now]])mxdep[now]=mxdep[i];
        if(ans[now]!=-1&&ans[i]==-1){
            int u=tots;
            for(int j=mxdep[i];;j=fa[j]){
                stk[++tots]=j;
                if(j==i)break;
            }
            reverse(stk+u+1,stk+tots+1);
        }
    }
    if(ans[now]==-1&&now==0){
        int u=tots;
        for(int j=mxdep[now];;j=fa[j]){
            stk[++tots]=j;
            if(j==now)break;
        }
        reverse(stk+u+1,stk+tots+1);
    }
    return;
}
void mdf(int pos){
    dp[pos][0]^=1;dp[pos][1]^=1;rev[pos]^=1;
    return;
}
void dfs2(int now){
    if(now>=n){
        dp[now][0]=dp[now][1]=0;
        return;
    }
    int u=son[now][0],v=son[now][1];
    dfs2(u);dfs2(v);
    if(qrymk[now]){
        if(dp[v][0]==dp[v][1])swap(u,v);
        if(dp[u][0]==0)mdf(u);
        if(dp[v][0]==1)mdf(v);
        dp[now][0]=0;
        dp[now][1]=1;
    }
    else{
        if(dp[v][0]==dp[v][1])swap(u,v);
        if(dp[u][0]==dp[u][1]&&dp[v][0]==dp[v][1]){
            if(dp[u][0]==0)mdf(u);
            if(dp[v][0]==0)mdf(v);
            dp[now][0]=dp[now][1]=1;
            return;
        }
        if(dp[u][0]==dp[u][1]){
            if(ans[now]==0){if(dp[u][0]==0)mdf(u);}
            else if(dp[u][0]==1)mdf(u);
            dp[now][0]=dp[v][0];dp[now][1]=dp[v][1];
        }
        else{
            if(ans[now]==0){
                if(dp[u][0]==0)mdf(u);
                if(dp[v][0]==0)mdf(v);
                dp[now][0]=1;dp[now][1]=0;
            }
            else{
                if(dp[u][0]==1)mdf(u);
                if(dp[v][0]==1)mdf(v);
                dp[now][0]=0;dp[now][1]=1;
            }
        }
    }
    return;
}
int Query(int pos){
    for(int i=0;i<=n*2;i++)rev[i]=qrymk[i]=0;
    for(int i=1;i<=pos;i++)qrymk[stk[i]]=1;
    dfs2(0);
    string qs="";
    for(int i=0;i<=n*2;i++)qs+=(char)('0'+rev[i]);
    return (query(qs)==dp[0][1]);
}
string solve(int NN,int RR,vector<int> U,vector<int> V) {
    n=NN;R=RR;
    dep[0]=1;
    for(int i=0;i<n;i++){
        son[i].emplace_back(U[i]);
        son[i].emplace_back(V[i]);
        dep[U[i]]=dep[V[i]]=dep[i]+1;
        fa[U[i]]=fa[V[i]]=i;
    }
    for(int i=0;i<n;i++)ans[i]=-1;
    while(1){
        k1=1;
        for(int i=0;i<n;i++)if(ans[i]==-1)k1=0;
        if(k1)break;
        tots=0;
        dfs(0);
        tots=min(tots,60);
        if(!Query(tots)){
            for(int i=1;i<=tots;i++)ans[stk[i]]=0;
            continue;
        }
        lft=1;rgt=tots;
        while(lft<rgt){
            mid=((lft+rgt)/2);
            if(Query(mid))rgt=mid;
            else lft=mid+1;
        }
        for(int i=1;i<lft;i++)ans[stk[i]]=0;
        ans[stk[lft]]=1;
    }
    string ret="";
    for(int i=0;i<n;i++){
        if(ans[i])ret+='|';
        else ret+='&';
    }
    return ret;
}