【洛谷4459】[BJOI2018] 双人猜数游戏(动态规划)

点此看题面

大致题意: 一直有两个数(m,n),已知(sle mle n),且(Alice)(Bob)二个“最强大佬”各知道(mn)(m+n)。每轮依次询问二人是否知道(m)(n)是多少,求构造一对合法的(m,n),使他们两个共说恰好(t)次不知道。

手玩样例

这题看起来真是神仙,差不多就是两个神仙人不停地说不知道,然后突然就知道了。。。

所以我们要来手(解)玩(释)一下样例。

这里先不讲如何求答案,就来讲一下这答案为什么可以,以样例(1)为例。

最后得到的(m,n)分别为(6,10),也就是说(Alice)(Bob)分别得到的是(60)(16)

那我们来模拟一下他们的思路:

(1)

  • (Bob):对于(Bob)来说,(16=5+11=6+10=7+9=8+8),在没有任何信息的情况下,无法排除任何一种答案。
  • (Alice):对于(Alice)来说,(60=5*12=6*10),这两种情况下的和分别为(17)(16),而如果(Bob)得到的是(17)(16),都不能一次确定答案,因此(Alice)也无法排除任何一种答案。

(2)

  • (Bob):上面提到过的(4)种情况,所对应的积分别为(55,60,63,64),而除了(60)以外,其余(3)种情况在(5le mle n)的情况下都只有一种分解方式,所以(Alice)可以直接确定。而(Alice)依然不知道,因此可以将这(3)种情况排除,就得出答案为(6,10)
  • (Alice):同理,在(Bob)确定之后也可以通过类似的方式确定。

动态规划

我们可以考虑用动态规划+剪枝来做这题。

(f_{i,j,k})表示已经说过(i)次不知道,且两个数分别为(j,k)时是否能确定

显然,对于每个人的询问是隔两次出现一次的。

而一个人如果上次被询问时已经知道答案了,下一次询问自然也知道。

于是可以推出第一个转移式:(f_{i,j,k}=f_{i-2,j,k})

而光这一个式子显然是不够的(废话),考虑上面手玩样例的过程,我们可以发现,以(Alice)为例,如果与(j,k)乘积相等的其他情况(设为(x,y))都可以使(f_{i-1,x,y}=1)(即如果是这种情况,上一次询问时另一个人就能得出答案),且(f_{i-1,j,k}=0),就可以排除其他所有情况,确定(f_{i,j,k}=1)

对于(Bob)同理。

这样就可以通过动态规划来预处理出(f)数组了。

求出答案

考虑到题目首先要求(m+n)最小,其次要求(m)最小,因此考虑先枚举(m+n),然后枚举(m)

于是就变成了判断一对(m,n)是否符合题目要求。

首先,由于要恰好说(t)次不知道,因此我们要保证对于任一(i<t)(f_{i,m,n}=0)

然后,还要特判一下(f_{t+1,m,n})是否确定,即判断此时的情况是否唯一,不然依然无法做到恰好说(t)次不知道。

这与之前动态规划的第二种转移方式的代码类似,具体实现详见代码。

代码

不知道不知道出了什么问题提答交不上去。。。只能直接交代码了(反正也跑得挺快,能(AC))。

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 15
#define V 300
using namespace std;
int n,t,k,f[N+5][V+5][V+5];char s[10];
I bool CheckA_Init(CI t,CI x,CI y)//预处理时对Alice的判断
{
    RI i,v=x*y,lim=sqrt(v),flag=0;for(i=k;i<=lim;++i)//枚举情况
    {
        if(v%i||(t&&f[t-1][i][v/i])) continue;//如果x*y不是i的倍数(即不存在这种情况),或者这种情况会使f[t-1][i][v/i]=1,就说明不符合条件
        if(i^x||flag) return false;flag=1;//如果符合条件的答案不为x,y,或有多种答案符合条件,说明不合法,返回false
    }return flag;//若只有x,y未确定,则可将其确定
}
I bool CheckB_Init(CI t,CI x,CI y)//预处理时对Bob的判断
{
    RI i,v=x+y,lim=v>>1,flag=0;for(i=k;i<=lim;++i)//枚举情况
    {
        if(t&&f[t-1][i][v-i]) continue;//如果这种情况会使f[t-1][i][v-i]=1,就说明不符合条件
        if(i^x||flag) return false;flag=1;//如果符合条件的答案不为x,y,或有多种答案符合条件,说明不合法,返回false
    }return flag;//若只有x,y未确定,则可将其确定
}
I bool CheckA_Answer(CI t,CI x,CI y)//求答案时对Alice的判断
{
    RI i,v=x*y,lim=sqrt(v),flag=0;for(i=k;i<=lim;++i)//枚举情况
    {
        if(v%i||!f[t][i][v/i]||(t>=2&&f[t-2][i][v/i])) continue;//如果x*y不是i的倍数(即不存在这种情况),或者这种情况无法确定f[t][i][v/i]=1,或者在上一轮已经可以确定f[t-2][i][v/i]=1,就说明不符合条件
        if(i^x||flag) return false;flag=1;//如果符合条件的答案不为x,y,或有多种答案符合条件,说明不合法,返回false
    }return flag;//若只有x,y合法,则可确定f[t+1][m][n]为1
}
I bool CheckB_Answer(CI t,CI x,CI y)//求答案时对Bob的判断
{
    RI i,v=x+y,lim=v>>1,flag=0;for(i=k;i<=lim;++i)//枚举情况
    {
        if(!f[t][i][v-i]||(t>=2&&f[t-2][i][v-i])) continue;//如果这种情况无法确定f[t][i][v-i]=1,或者在上一轮已经可以确定f[t-2][i][v-i]=1,就说明不符合条件
        if(i^x||flag) return false;flag=1;//如果符合条件的答案不为x,y,或有多种答案符合条件,说明不合法,返回false
    }return flag;//若只有x,y合法,则可确定f[t+1][m][n]为1
}
int main()
{
    RI i,j,l,STO,ORZ,op,flag;scanf("%d%s%d",&k,&s,&n),t=s[0]=='B';//读入数据
    for(i=0,op=t;i<=n;++i,op^=1) for(STO=k;STO<=V;++STO) for(ORZ=k;ORZ<=V;++ORZ)
        f[i][STO][ORZ]=i>=2&&f[i-2][STO][ORZ]?1:(op?CheckB_Init(i,STO,ORZ):CheckA_Init(i,STO,ORZ));//动态规划预处理
    for(i=k<<1;;++i) for(j=1;j<=(i>>1);++j)//枚举答案
    {
        for(flag=f[n][STO=j][ORZ=i-j],l=0;l^n&&flag;++l) f[l][STO][ORZ]&&(flag=0);if(!flag) continue;//若存在更早的情况,说明无法做到恰好t个,跳过
        if(!((n&1?!t:t)?CheckA_Answer(n,STO,ORZ):CheckB_Answer(n,STO,ORZ))) continue;//特判
        return printf("%d %d",STO,ORZ),0;//输出答案并结束程序
    }return 0;
}
原文地址:https://www.cnblogs.com/chenxiaoran666/p/Luogu4459.html