专栏文章

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

PP_BisectorGo ahead
P10831题解参与者 2已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mioh1fjf
此快照首次捕获于
2025/12/02 19:05
3 个月前
此快照最后确认于
2025/12/02 19:05
3 个月前
查看原文
我爱乱搞。

正文

显然随机进行几次操作之后有极大概率可以确定一个三元环。（即返回 00 或 33）。
假设我们有点 jj ，点 kk，点 xx 和点 yy。 已知 jj 和 xx 之间的连边状况和 jj 和 yy 之间的连边状况。并且我们对其他四条边的连边状况一无所知。我们来尝试探索一下。
  • 首先，我们询问 (j,k,x)(j,k,x) 之间的连边状况。 有 12\frac{1}{2} 的概率我们可以得出 (j,k)(j,k) 和 (k,x)(k,x) 的连边状况，还有另外 12\frac{1}{2} 的概率我们只能确定这两对未知关系中恰有一条边。
  • 接着，我们询问 (j,k,y)(j,k,y) 之间的连边状况。同样的，有 12\frac{1}{2} 的概率我们可以得出 (j,k)(j,k) 和 (k,y)(k,y) 的连边状况，顺便可以推出 (k,x)(k,x) 之间的连边状况，还有另外 12\frac{1}{2} 的概率我们只能确定这两对未知关系中恰有一条边。
  • 显然，我们在上面两次询问后可以发现 (j,k)(j,k) 和 (k,x)(k,x) 中恰有一条边， (j,k)(j,k) 和 (k,y)(k,y) 中恰有一条边。由此我们可以推出 (k,x)(k,x) 和 (k,y)(k,y) 同时连边或不连边。
  • 然后，我们询问 (k,x,y)(k,x,y) 之间的连边状况。接下来我们分类讨论：
    • 如果有 00 条边，那么 (k,x)(k,x)，(k,y)(k,y) 之间必定无边，则 (j,k)(j,k) 之间有边。同时我们可以发现 (x,y)(x,y) 之 间必无边。
    • 如果有 11 条边，那么 (k,x)(k,x)，(k,y)(k,y) 之间必定无法同时连边，因此必定无边，则 (j,k)(j,k) 之间有边。同时我们可以发现 (x,y)(x,y) 之间必有边。
    • 如果有 22 条边，那么 (k,x)(k,x)，(k,y)(k,y) 之间必定同时有边，则 (j,k)(j,k) 之间无边。同时我们可以发现 (x,y)(x,y) 之间必无边。
    • 如果有 33 条边，那么 (k,x)(k,x)，(k,y)(k,y) 之间必定同时有边，则 (j,k)(j,k) 之间无边。同时我们可以发现 (x,y)(x,y) 之间必有边。
我们来简单算一下这一波当中每次询问的收益的期望。
  • 有 12\frac{1}{2} 的概率第一步就有效，这个时候我们可以得知两条边，平均每次询问的收益（得到有效信息的量）为 22。
  • 有 12×12=14\frac{1}{2}\times\frac{1}{2}=\frac{1}{4} 的概率第二步就有效，这个时候我们可以得知三条边，平均每次询问的收益为 3÷2=323 \div 2=\frac{3}{2}。
  • 有 14\frac{1}{4} 的概率第三步才有效，这个时候我们可以得知四条边，平均每次询问的收益为 4÷3=434 \div 3=\frac{4}{3}。
综上，平均每次询问的收益的期望 E=12×2+14×32+14×43=4124E=\frac{1}{2}\times2+\frac{1}{4}\times\frac{3}{2}+\frac{1}{4}\times\frac{4}{3}=\frac{41}{24}。而要求 34003400 次询问，边共 49504950 条，3400×4124=580813>49503400 \times \frac{41}{24}=5808\frac{1}{3}>4950，看起来绰绰有余的样子。
我们考虑如何将询问用在“刀刃”上。在钦定一些边之后，我们暴力枚举所有完全未知的三元环代替 (k,x,y)(k,x,y)，并且暴力枚举合法的 jj，然后按照上文方法计算即可。注意在操作结束后枚举所有未知边，并且注意未用上的询问的回收。一些参数可见代码。
代码如下CPP
//最大询问数：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：目前已经将询问次数卡到 32273227 了。

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...