题解 P4459 【[BJOI2018]双人猜数游戏】
zhaotiensn · · 题解
这题一眼看下去很神，其实看过题解后觉得还好。
就先拿样例一举例来理解Alice和Bob的思维方式：
因为两个数分别是6和10，所以Alice拿到的是60，Bob拿到的是16。
主持人问Bob，因为16分解为两个大于等于5的数可以是：5 11；6 10；7 9；8 8。所以Bob不知道。
主持人问Alice，因为60分解出：5 12；6 10。然后Bob答不知道无法排除任何一个。所以Alice不知道。
主持人问Bob，因为Alice答不知道，所以肯定不是只有一种分解方案的数（例如55，如果Alice拿到的为55，55只能为5*11，Alice就知道了，反之），所以上面的5 11；7 9；8 8三个组合排除，只剩下了6 10。所以Bob知道了。
主持人问Alice，因为Bob知道了，所以可以排除5 12（因为如果Bob拿到的是17，Bob应该还有5 12；7 10；8 9可能，所以Bob应该是不知道），只剩下了6 10，所以Alice也知道了。
从上面的过程中可以看出方案的可能在保证有解的情况下一定是越来越少的，然后我们可以尝试着用f[i][j][k]表示一个数为i，另一个数为j，在k个不知道时是否被确定。
然后根据上面的过程写出暴力的转移方程：
1.如果f[i][j][k-2]已经确定了，那么f[i][j][k]肯定也是确定的（上一轮已经确定的，多一轮肯定也确定）
2.暴力枚举i和j其他的可能方案，拿Bob来举例，如果除f[i][j][k-2]外所有f[i-num][j+num][k-2]都已确定，那么f[i][j][k]就确定了，参考样例一中Bob回答知道的那一次，同样道理也使用于Alice。
将f数组处理出来然后就只要找到最小的那一组在t次不知道下首次被确定的i和j就好了。
另外因为f[i][j][k]与f[i][j][k-1]无关，所以可能存在f[i][j][k]确定，f[i][j][k-1]不确定的情况，需要判一下。
复杂度什么的不重要，好像后面的点一分钟一个，跑完20分钟左右
代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#define Max 2005//最大值看心情，越大越慢，最大的答案好像也就300不到，数组小一点也没有关系
using namespace std;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
int x=0;char ch=gc();bool positive=1;
for(;!isdigit(ch);ch=gc())if(ch=='-')positive=0;
for(;isdigit(ch);ch=gc())x=x*10+ch-'0';
return positive?x:-x;
}
inline void write(int x){
if(x<0)x=-x,putchar('-');
if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writeln(int x){
write(x);puts("");
}
//以上皆没用
int s,t;
bool flag,f[Max][Max][20];
char a[10];
inline bool check1(int x,int y,int t){
int num=x*y,len=sqrt(x*y),xx=0,yy=0,cnt=0;
for(int i=s;i<=len;i++){
if(num%i==0){
//枚举方案，然后暴力
if((!f[i][num/i][t-1])||(!t)){
xx=i;yy=num/i;
cnt++;
}
}
}//当只有x和y一种方案没有确定时f[x][y][t]就确定了
if(cnt==1&&xx==x&&yy==y){
return true;
}else{
return false;
}
}//Alice的暴力转移
inline bool check2(int x,int y,int t){
int num=x+y,len=(x+y)/2,xx=0,yy=0,cnt=0;
for(int i=s;i<=len;i++){
//转移同上
if((!f[i][num-i][t-1])||(!t)){
xx=i;yy=num-i;
cnt++;
}
}
if(cnt==1&&xx==x&&yy==y){
return true;
}else{
return false;
}
}//Bob的
inline bool check3(int x,int y,int t){
int num=x*y,len=sqrt(x*y),xx=0,yy=0,cnt=0;
for(int i=s;i<=len;i++){
if(num%i==0){
//与暴力转移差不多
if(f[i][num/i][t]&&(t<2||(!f[i][num/i][t-2]))){
xx=i;yy=num/i;
++cnt;
}
}
}
if(cnt==1&&xx==x&&yy==y){
return true;
}else{
return false;
}
}//特判
inline bool check4(int x,int y,int t){
int num=x+y,len=(x+y)/2,xx=0,yy=0,cnt=0;
for(int i=s;i<=len;i++){
if(f[i][num-i][t]&&(t<2||(!f[i][num-i][t-2]))){
xx=i;yy=num-i;
++cnt;
}
}
if(cnt==1&&xx==x&&yy==y){
return true;
}else{
return false;
}
}//同上
int main(){
freopen("guess.in","r",stdin);
freopen("guess.out","w",stdout);
s=read();
scanf("%s",a+1);
t=read();
if(a[1]=='A')flag=true;else flag=false;//flag表示当前是Alice还是Bob
for(int i=0;i<=t;i++,flag^=1){//dp
for(int j=s;j<=1000;j++){
for(int k=s;k<=1000;k++){
if(i>=2)f[j][k][i]=f[j][k][i-2];//转移方程1
if(flag){//根据Alice和Bob分开转移
f[j][k][i]=f[j][k][i]|check1(j,k,i);
}else{
f[j][k][i]=f[j][k][i]|check2(j,k,i);
}
}
}
}
int sum=2*s,x=0,y=0;
while(true){//枚举i+j的值
for(int i=s;i<=sum/2;i++){//枚举i
x=i,y=sum-i;
flag=f[x][y][t];//是否在t轮被确定
if(!flag)continue;
for(int j=0;j<t;j++){//是否在t轮首次被确定
if(f[x][y][j]){
flag=false;
break;
}
}
if(!flag)continue;
if(((t&1)&&a[1]=='A')||((!(t&1))&&a[1]=='B')){//特判
flag=check3(x,y,t);
}else{
flag=check4(x,y,t);
}
if(!flag)continue;
write(x);putchar(' ');writeln(y);
return 0;
}
sum++;
}
return 0;
}