CF1442F Differentiating Games

传送门

CF1442F Differentiating Games

题目大意

给你一个 DAG，\(n(n \le 1000)\) 个点，\(m(m \le 10^5)\) 条边。一次游戏为：两人轮流操作，每次可以选择一个硬币，向着某一条出边移动一步，不能操作者输。

你可以在最开始的时候修改 \(k(k \le 4242)\) 次这个图，每次可以加一条边或者删一条边，修改后可以不是 DAG。

有 \(T\) 次询问。每次交互库会选择一个隐藏节点 \(X\)。然后，你可以询问 \(t\) 次，每次给交互库一个可重集 \(S(\sum |S| \le 20)\)，交互库会告诉你：在这些位置各放一个棋子，再在 \(X\) 放一个棋子，那么游戏的结果是先手胜、先手负或是平局。你需要猜出 \(x\)。

思路

既然要删边加边，可以考虑满足哪些条件的图能保证猜出 \(X\)。

可以发现，如果图是一个完全 DAG，那么我们每次询问一个点：

1. 这个点是 \(X\)，那么询问这个位置就表示在这个位置上有两个棋子。后手跟着先手走，先手必败。

2. 这个点不是 \(X\)，因为是完全 DAG，先手可以一步变为两个棋子在同一个位置上。这时先手必胜。

虽然这样我们需要 \(O(n^2)\) 条边，但是我们只需要查询 \(n\) 次。题目要求查询 \(20\) 次，那我们是否可以建一个大小为 \(20\) 的完全 DAG 呢？

如果我们有一个大小为 \(20\) 的完全 DAG，那么首先我们如果发现一个点先手必败，显然是 \(X\)。

如果没有先手必败，那么每个点的答案就有两种情况，先手必胜或平局。

那么总的情况就有 \(2^{20}=1048576\) 个，能够满足 \(n \le 1000\) 的需求。

那么我们要如何构造图剩下的部分呢？

为了方便，我们将完全 DAG 中的点称作 \(A\) 类点，其它的称作 \(B\) 类点。

因为我们已经判断出了 \(X\) 是 \(A\) 类点的情况，所以现在我们只需要讨论 \(X\) 是 \(B\) 类点。

我们给所有 \(B\) 类点都建一个自环，并让所有 \(B\) 类点有边连向 \(A\) 类点。因为这样之后，对于先手来说，要么把 \(X\) 上的棋子走出自环，要么原地不动。如果先手走出去是必败状态，一定会选择不动。如果选择不动，那么后手拿到的情况与先手相同，一样会选择不动，就产生了平局。否则先手肯定必胜。这就符合我们所需要的 每个点的答案有两种情况，先手必胜或平局。

如果我们可以知道什么时候先手必胜，那么我们就可以构造边使得每个点的获胜情况两两不同。

那么什么时候先手必胜？

我们假设先手已经将棋子从 \(B\) 类点移到了 \(A\) 类点，那么这时两个棋子都在 \(A\) 类点中，也就是跟我们之前讨论的相同。

也就可以推出，如果 \(B\) 类点上的这个棋子能够直接到达另一个棋子的位置，那么先手必胜。

这样，我们让每个点的获胜情况两两不同，只需要让连向的 \(A\) 类点组成的集合两两不同即可。

现在我们需要让修改次数最小。这里我们取 \(n=1000\) 计算。

首先我们选出 \(A\) 类点。我们可以发现，选择拓扑序中最后的一些点能够使 \(A\) 类点到 \(B\) 类点没有边。

所以我们可以选择拓扑序中的后 \(20\) 个点作为 \(A\) 类点。那么连完全 DAG 的边就是 \(\frac{(1+19) \times 19}{2} = 190\)。给 \(B\) 类点连自环需要 \(980\) 条边。

为了让 \(B\) 类点到 \(A\) 类点的边更改数尽可能小，我们以更改的次数作为状态的排序依据，这个可以看代码理解。连边个数大约为 \(C_{20}^1 \times 1 + C_{20}^2 \times 2 + 770 \times 3 = 2710\)

总边数为 \(190+980+2710=3880\)，可以通过本题。

代码实现

#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(ll i=(a);i<=(b);++i)
#define Rep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
const ll N=4e3+10;
const ll M=2e6+10;
using namespace std;

ll cnt;//改变的边的数量
struct EDGE{
	ll x,y;//起终点
	ll opt;//0为删的边，1为连的边
}edge[M];//记录改变的边

ll n,m,k;
ll a[M];
vector<ll>e[M];//存边
ll vis[N][N];//快速判断是否有边
ll in[M];//入度
ll tot,tp[M],b[M];//tp是拓扑序，b是拓扑序中对应的位置
ll cntA,node[M];//A类点个数及编号，node[i]为0表示为B类点
ll book[M];//加边时判断状态是否能到达
ll ans[M];//记录答案点

void __top(){//拓扑序板子
	queue<ll>q;
	For(i,1,n)if(!in[i])q.push(i);
	while(!q.empty()){
		ll x=q.front();
		q.pop();
		tp[++tot]=x,b[x]=tot;//记录拓扑序
		for(ll y:e[x]){
			in[y]--;
			if(!in[y])q.push(y);
		}
	}
}

void find_A(){//找A类点
	cntA=0;
	Rep(i,tot,1){
		node[tp[i]]=++cntA;
		if(cntA>=20)break;
	}
}

void change(ll x,ll y,ll opt){//flag=0删边，flag=1加边
	edge[++cnt]=(EDGE){x,y,opt};
}

void changeA(){//删无用边，连出完全拓扑图
	For(x,1,n){
		if(!node[x])continue;//跳过B类点
		//删除不符合条件的边
		for(ll y:e[x]){
			if(node[y])continue;//A->A不需要删
			if(b[x]<b[y])continue;//A->B中拓扑序正确的不删
			change(x,y,0);//删边
		}
		//连成完全拓扑图
		For(y,1,n){
			if(!node[y])continue;//跳过B类点
			if(b[x]>=b[y])continue;//拓扑序不正确不连
			if(vis[x][y])continue;//有边不连
			change(x,y,1);//连边
		}
	}
}

void changeB(){//添加自环，调边使答案唯一
	//找出可以调整达到唯一对应一个点的win状态
	queue<ll>q;//状态队列
	vector<ll>tmp;//记录状态
	q.push(0);
	while(q.size()){
		ll s=q.front();//初始状态
		q.pop();
		tmp.pb(s);//记录状态
		For(i,1,cntA){
			ll t=s|(1<<i-1);//下一个状态
			if(!book[t]){
				book[t]=1;
				q.push(t);
			}
		}
	}
	For(x,1,n){
		if(node[x])continue;//跳过A类点
		change(x,x,1);//添加自环
		//状压能到达的A类点
		ll s=0;
		for(ll y:e[x]){
			if(!node[y])continue;//跳过B类点
			s|=1<<node[y]-1;
		}
		//调整边使每个B类点的win状态唯一
		for(ll i:tmp){
			ll t=s^i;//对应的win状态
			if(book[t]){
				ans[t]=x;
				book[t]=0;
				//使当前枚举的win状态唯一对应x
				For(y,1,cntA){
					if(i&(1<<y-1)){
						//因为选的A类点是拓扑序最后的几个，所以tp[tot-y+1]就是对应的编号
						if(s&(1<<y-1))change(x,tp[tot-y+1],0);//删边
						else change(x,tp[tot-y+1],1);//连边
					}
				}
				break;
			}
		}
	}
}

ll query(ll x){
	printf("? 1 %lld\n",x);
	fflush(stdout);
	char str[10];
	scanf("%s",str);
	if(str[0]=='W')return 1;//win
	if(str[0]=='L')return -1;//lose
	return 0;//draw
}

void mian(){
	
	scanf("%lld",&n);
	scanf("%lld",&m);
	scanf("%lld",&k);
	For(i,1,m){
		ll x,y;
		scanf("%lld%lld",&x,&y);
		e[x].pb(y),vis[x][y]=1;//e存边，vis快速判断是否有边
		in[y]++;//统计入度
	}
	
	__top();//拓扑序
	find_A();//找A类点
	changeA();//A类点：删无用边，连出完全拓扑图
	changeB();//B类点：添加自环，调边使答案唯一
	
	//输出改的边
	printf("%lld\n",cnt);
	For(i,1,cnt){
		if(edge[i].opt)printf("+ %lld %lld\n",edge[i].x,edge[i].y);
		else printf("- %lld %lld\n",edge[i].x,edge[i].y);
	}
	fflush(stdout);
	while(k--){
		ll s=0;//记录win状态
		ll flag=0;//标记
		Rep(i,tot,tot-cntA+1){
			ll x=tp[i];//点的编号
			ll answer=query(x);
			if(answer==-1){//lose
				printf("! %lld\n",x);
				fflush(stdout);
				flag=1;//标记
				break;
			}
			if(answer==1){//win
				s|=1<<node[x]-1;//记录状态
			}
		}
		if(!flag){
			printf("! %lld\n",ans[s]);//对应状态的答案
			fflush(stdout);
		}
		char str[10];
		scanf("%s",str);//读掉Correct
	}
	
}

int main(){
	int T=1;
//	scanf("%d",&T);
	while(T--)mian();
	return 0;
}

尾声

如果你发现了问题，你可以直接回复这篇题解

如果你有更好的想法，也可以直接回复！