* ! BJOI2018双人猜数游戏

很有意思的题目

考虑用DP模拟两人

\(f[n][m][k],k\)轮不知道后能否知道

首先\(f[n][m][k]=f[n][m][k-2]\)

用\(Alice\)举例，\(n*m=x*y\)则除\((n,m)\)外的\((x,y)\)都要在\(k-1\)轮得知才能确定\((n,m)\)，\(Bob\)推理同理

求答案时，\(t-1\)都要不知道\(t\)刚好知道，且\(t+1\)也要知道

注：\(t+1\)不能和前面的DP一起求，因为前面都是假定前面都不知道，但求\(t+1\)时\(t\)是知道的，所以除\((n,m)\)外都必须不知道

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c==‘-‘)f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
const int N=304,n=300;
int s,t,r,f[20][N][N];
char ch[8];
inline bool checka_dp(int t,int x,int y){
	for(int i=s,v=x*y,lim=sqrt(v);i<=lim;i++){
		if(v%i||(t&&f[t-1][i][v/i]))continue;
		if(i^x)return 0;
	}
	return 1;
}
inline bool checkb_dp(int t,int x,int y){
	for(int i=s,v=x+y,lim=v>>1;i<=lim;i++){
		if(t&&f[t-1][i][v-i])continue;
		if(i^x)return 0;
	}
	return 1;
}
inline bool checka_ans(int t,int x,int y){
	for(int i=s,v=x*y,lim=sqrt(v);i<=lim;i++){
		if(v%i||!f[t][i][v/i]||(t>=2&&f[t-2][i][v/i]))continue;
		if(i^x)return 0;
	}
	return 1;
}
inline bool checkb_ans(int t,int x,int y){
	for(int i=s,v=x+y,lim=v>>1;i<=lim;i++){
		if(!f[t][i][v-i]||(t>=2&&f[t-2][i][v-i]))continue;
		if(i^x)return 0;
	}
	return 1;
}
int main(){
	s=read();scanf("%s",ch);t=read();
	r=(ch[0]==‘B‘);
	for(int i=0;i<=t;i++,r^=1)
		for(int u=s;u<=n;u++)
			for(int v=s;v<=n;v++){
				if(i>=2)f[i][u][v]=f[i-2][u][v];
				if(!f[i][u][v])f[i][u][v]=(r?checkb_dp(i,u,v):checka_dp(i,u,v));
			}
	for(int i=s<<1,fl;;i++)
		for(int u=s;(u<<1)<=i;u++){
			fl=f[t][u][i-u];
			for(int j=0;(j^t)&&fl;j++)
				if(f[j][u][i-u])fl=0;
			if(!fl)continue;
			if(((t&1)&&ch[0]==‘A‘)||(!(t&1)&&ch[0]==‘B‘))fl=checka_ans(t,u,i-u);
			else fl=checkb_ans(t,u,i-u);
			if(fl){cout<<u<<" "<<i-u<<"\n";return (0-0);}
		}
	return (0-0);
}

* ! BJOI2018双人猜数游戏

原文：https://www.cnblogs.com/aurora2004/p/12577379.html