题解：P10831 [COTS 2023] 三角形 Trokuti

P_Bisector · 2025-08-07 18:07:42 · 题解

我爱乱搞。

正文

显然随机进行几次操作之后有极大概率可以确定一个三元环。（即返回 0 或 3）。

假设我们有点 j ，点 k，点 x 和点 y。 已知 j 和 x 之间的连边状况和 j 和 y 之间的连边状况。并且我们对其他四条边的连边状况一无所知。我们来尝试探索一下。

• 首先，我们询问 (j,k,x) 之间的连边状况。 有 \frac{1}{2} 的概率我们可以得出 (j,k) 和 (k,x) 的连边状况，还有另外 \frac{1}{2} 的概率我们只能确定这两对未知关系中恰有一条边。

• 接着，我们询问 (j,k,y) 之间的连边状况。同样的，有 \frac{1}{2} 的概率我们可以得出 (j,k) 和 (k,y) 的连边状况，顺便可以推出 (k,x) 之间的连边状况，还有另外 \frac{1}{2} 的概率我们只能确定这两对未知关系中恰有一条边。

• 显然，我们在上面两次询问后可以发现 (j,k) 和 (k,x) 中恰有一条边， (j,k) 和 (k,y) 中恰有一条边。由此我们可以推出 (k,x) 和 (k,y) 同时连边或不连边。

• 然后，我们询问 (k,x,y) 之间的连边状况。接下来我们分类讨论：

  • 如果有 0 条边，那么 (k,x)，(k,y) 之间必定无边，则 (j,k) 之间有边。同时我们可以发现 (x,y) 之 间必无边。

  • 如果有 1 条边，那么 (k,x)，(k,y) 之间必定无法同时连边，因此必定无边，则 (j,k) 之间有边。同时我们可以发现 (x,y) 之间必有边。

  • 如果有 2 条边，那么 (k,x)，(k,y) 之间必定同时有边，则 (j,k) 之间无边。同时我们可以发现 (x,y) 之间必无边。

  • 如果有 3 条边，那么 (k,x)，(k,y) 之间必定同时有边，则 (j,k) 之间无边。同时我们可以发现 (x,y) 之间必有边。

我们来简单算一下这一波当中每次询问的收益的期望。

• 有 \frac{1}{2} 的概率第一步就有效，这个时候我们可以得知两条边，平均每次询问的收益（得到有效信息的量）为 2。
• 有 \frac{1}{2}\times\frac{1}{2}=\frac{1}{4} 的概率第二步就有效，这个时候我们可以得知三条边，平均每次询问的收益为 3 \div 2=\frac{3}{2}。
• 有 \frac{1}{4} 的概率第三步才有效，这个时候我们可以得知四条边，平均每次询问的收益为 4 \div 3=\frac{4}{3}。

综上，平均每次询问的收益的期望 E=\frac{1}{2}\times2+\frac{1}{4}\times\frac{3}{2}+\frac{1}{4}\times\frac{4}{3}=\frac{41}{24}。而要求 3400 次询问，边共 4950 条，3400 \times \frac{41}{24}=5808\frac{1}{3}>4950，看起来绰绰有余的样子。

我们考虑如何将询问用在“刀刃”上。在钦定一些边之后，我们暴力枚举所有完全未知的三元环代替 (k,x,y)，并且暴力枚举合法的 j，然后按照上文方法计算即可。注意在操作结束后枚举所有未知边，并且注意未用上的询问的回收。一些参数可见代码。

::::info[代码如下]

//最大询问数：3251。
#include<bits/stdc++.h>
#define B __int128
#define pb push_back
#define PLL pair<int,int>
#define Qin ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;void solve();
int main(){Qin;int t,M=0;M?(cin>>t,0):t=1;while(t--)solve();return 0;}
#define int long long
const int inf=1e18,N_=100050,mod=998244353,P=1e9+7,N=1e6+50,N2=150;
int n=100;
int G[N2][N2],t[N2][N2][N2],a[N2];
int query(int a,int b,int c){
    int x=min(min(a,b),c),y=max(max(a,b),c);
    int z=a+b+c-x-y;
    if(t[x][y][z])return t[x][y][z]-1;
    cout<<"? "<<a<<" "<<b<<" "<<c<<endl;
    int tmp;
    cin>>tmp;
    return (t[x][y][z]=tmp+1)-1;
}
int chkq(int a,int b,int c){
    int x=min(min(a,b),c),y=max(max(a,b),c);
    int z=a+b+c-x-y;
    return !!t[x][y][z];
}
struct edge{int u,v;};
vector<int>v[N2];
void subsolve(int j,int x,int y,int k){
    if(G[x][k]==2&&G[y][k]==2&&G[j][k]==2){
        int tmp1=query(j,k,x)-G[j][x];
        if(tmp1!=1){
            G[j][k]=G[k][j]=G[k][x]=G[x][k]=tmp1/2;
            v[j].push_back(k),v[k].push_back(j);
            v[x].push_back(k),v[k].push_back(x);
            return;
        }
        int tmp2=query(j,k,y)-G[j][y];
        if(tmp2!=1){
            G[j][k]=G[k][j]=G[k][y]=G[y][k]=tmp2/2;
            G[x][k]=G[k][x]=tmp1-tmp2/2;
            v[x].push_back(k),v[k].push_back(x);
            v[j].push_back(k),v[k].push_back(j);
            v[y].push_back(k),v[k].push_back(y);
            return;
        }
        int tmp=query(k,x,y);
        if(tmp%3==0){
            G[x][k]=G[k][x]=G[k][y]=G[y][k]=
            G[x][y]=G[y][x]=tmp/3;
            G[k][j]=G[j][k]=tmp1-tmp/3;
        }else if(tmp==1){
            G[x][y]=G[y][x]=1;
            G[x][k]=G[k][x]=G[y][k]=G[k][y]=0;
            G[j][k]=G[k][j]=tmp1;
        }else{
            G[x][y]=G[y][x]=0;
            G[x][k]=G[k][x]=G[y][k]=G[k][y]=1;
            G[j][k]=G[k][j]=tmp1-1;
        } 
        v[x].push_back(k),v[k].push_back(x);
        v[y].push_back(k),v[k].push_back(y);
        v[x].push_back(y),v[y].push_back(x);
        v[k].push_back(j),v[j].push_back(k);
        return;
    }
}
void solve(){
    int n=100,cnt=0;
//  cin>>n; 
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)G[i][j]=(i!=j)*2,a[i]=i;
    vector<edge>q;
    for(int i=1;i<=50||cnt<=25;i++){
        int a=rand()%n+1,b=rand()%n+1,c=rand()%n+1;
        while(b==a)b=rand()%n+1;while(c==b||c==a)c=rand()%n+1;
        int tmp=query(a,b,c);
        if(tmp==3||tmp==0){
            G[a][b]=G[a][c]=G[b][c]=G[b][a]=G[c][b]=G[c][a]=!!tmp,
            v[a].pb(c),v[a].pb(b),v[b].pb(c),v[b].pb(a),v[c].pb(a);
            v[c].pb(b); 
            cnt++;
            q.pb({a,c}),q.pb({b,c}),q.pb({a,b});
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                if(G[i][j]+G[i][k]+G[j][k]==6){
                    for(int l=1;l<=n;l++){
                        if(G[i][l]<2&&G[j][l]<2&&j!=l&&i!=l&&k!=l){
                            subsolve(l,i,j,k);
                        }
                    } 
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(G[i][j]==2){
                for(int k=1;k<=n;k++){
                    if(chkq(i,j,k)&&G[i][k]<2&&G[j][k]<2&&i!=k&&j!=k){
                        int tmp=query(i,j,k);
                        G[j][i]=G[i][j]=tmp-G[i][k]-G[j][k]; 
                        goto OK;
                    }
                }
            }
            OK:;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(G[i][j]==2){
                for(int k=1;k<=n;k++){
                    if(G[i][k]<2&&G[j][k]<2&&i!=k&&j!=k){
                        int tmp=query(i,j,k);
                        G[j][i]=G[i][j]=tmp-G[i][k]-G[j][k]; 
                        goto OP;
                    }
                }
            }
            OP:;
        }
    }
    cout<<"!\n";
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<G[i][j];
        }
        cout<<endl;
    }
}

::::

PS：目前已经将询问次数卡到 3227 了。