双人猜数游戏 题解

· · 题解

题目大意

Alice 和 Bob 两个人在玩“最强大佬”猜数游戏，主持人会先想两个数 N, M，告诉两个人一个数 S，保证 S \leq\ M \leq\ N。然后告诉 Alice N \times M 的值，告诉 Bob N + M 的值。接着主持人进行 T 个提问，由 Alice 和 Bob 轮流回答，每次都回答“知道”或“不知道”。请构建出一组 N, M，使主持人在 T 个提问后两个人都知道 N, M 的值了。

解题思路

这道题乍一看还挺玄学的，就两个人在那说着说着不知道然后突然就都知道了。

认真分析一下，既然知道 N 与 M 的范围，那两个人就可以根据自己的信息求出所有可能的组合，然后根据别人知不知道排除与信息不符的选项，从而得出结果了。

举个样例 1 例子：

所以大致思路就是，每日根据自己的信息解出所有可能的组合，通过对方的信息筛掉其他的组合，最后剩下一个情况时就可以确定了。

看看这道题的数据，看起来范围并不是很大。所以我们直接枚举 N 和 M 的所有情况，然后使用一个函数判断即可。

怎么判断呢？可以用递归！这个递归的目的就是求出指定的 N 和 M 前若干次两个人的回答情况。

如果只需要一次回答了，就返回当前所有情况集合中是否只有一个元素。否则就两个人轮流搜索递归调用，把不符合的情况删去，把答案保存在一个 vector 里，在函数结束后检查 T 次询问的最后两个是否为两个 1 就可以了。

最后就是每个点用程序跑一遍，直接提交即可。

注意事项

递归需要加上记忆化，否则会 TLE。

AC code

这里给出用来跑的代码。

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll,ll> P;
const int N=504;
ll s,beg;
unordered_map<ll,vector<bool>>mp[N][N];
string name;
vector<bool> dfs(ll n,ll m,ll t){
    if(mp[n][m].count(t)){
        return mp[n][m][t];
    }
    vector<P> a;
    vector<P> b;    
    ll x=n*m;
    for(int i=s;i<=x;i++){
        if(x%i==0){
            ll j=x/i;
            if(i>j){
                break;
            }
            a.push_back(P(i,j));
        }
    }
    x=n+m;
    for(int i=s;i<=x;i++){
        ll j=x-i;
        if(j<i){
            break;
        }
        b.push_back(P(i,j));
    }
    vector<bool> ans;
    if(beg&1){
        ans.push_back(a.size()==1);
    }else{
        ans.push_back(b.size()==1);
    }
    if(t==1){
        return ans;
    }
    vector<P> tmp;
    for(int i=2;i<=t;i++){
        if((i&1)==(beg&1)){
            for(P x:a){
                if(dfs(x.first,x.second,i-1)==ans){
                    tmp.push_back(x);
                }
            }
            swap(tmp,a);
            tmp.clear();
            ans.push_back(a.size()==1);
        }else{
            for(P x:b){
                if(dfs(x.first,x.second,i-1)==ans){
                    tmp.push_back(x);
                }
            }
            swap(tmp,b);
            tmp.clear();
            ans.push_back(b.size()==1);
        }
    }
    return mp[n][m][t]=ans;
}
int main(){ 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0); 
    ll t;
    cin>>s>>name>>t;
    if(name[0]=='A'){
        beg=1;
    }else{
        beg=2;
    }
    for(int sum=s+s;true;sum++){
        for(int n=s;n<=sum;n++){
            ll m=sum-n;
            if(m<n){
                break;
            }
            vector<bool> ans=dfs(n,m,t+2);
            for(int i=0;i<t;i++){
                if(ans[i]){
                    goto X;
                }
            }
            if(ans[t]&&ans[t+1]){
                cout<<n<<' '<<m;
                exit(0);
            }
            X:;
        }
    }
}

最后，祝各位能 AC 这道题！