[BJOI2018] 双人猜数游戏

Description

$\rm Link$

Solution

首先分析下样例。

第一轮，对于 Bob 而言，当前的可能方案有 $5+11,6+10,7+9,8+8$ ，所以他不能确定。

第二轮，对于 Alice 而言，当前的可能方案有 $5\times 12,6\times 10$ ，所以她不能确定。

第三轮，对于 Bob 而言，如果是 $5+11$ ，此时乘积为 $55$ ，合法分解只有一种，Alice 可以直接确定；$7+9,8+8$ 同理，所以他可以确定是 $6+10$ 。

第四轮，对于 Alice 而言，如果是 $5\times 12$ ，那么 Bob 在第三轮的时候应该会有 $8+9$ 和 $7+10$ 两种，他无法确定；所以 Alice 可以确定是 $6\times 10$ 。

根据上面的分析，我们考虑一个这样的 DP 。设 $f_{i,j,k}$ 表示 $m=i,n=j$ 时，经历了 $k$ 轮「不知道」后，第 $k+1$ 轮的人是否可以确定这两个数。根据第 $k+1$ 轮是 Alice 还是 Bob 分两种情况讨论。此处假设是 Alice 。转移有两种：

• 第 $k-2$ 轮后即可确定，那么本轮也可以确定。
• 若将 $q=i\times j$ 拆分成除 $(i,j)$ 外任意两个大于等于 $s$ 的数 $(x,y)$ 的乘积，都满足 $(x,y)$ 在第 $k-1$ 轮后可以确定，由于第 $k-1$ 轮是不知道，所以第 $k$ 轮可以确定。

对于 Bob， 只需要把乘积改成加法即可。

事实上，我们这样子只能确定第 $k+1$ 轮的人一定可以确定，但没办法保证第 $k+2$ 轮的人也一定可以确定。注意，此处不能简单用 $f_{i,j,k+1}$ 来判断，因为第 $k+1$ 轮是 「不知道」还是 「知道」这个信息对于第 $k+2$ 轮是有影响的。我们沿用之前转移的思路来特判。还是假设第 $k+2$ 轮是 Alice，那么她可以知道当且仅当：

• 若将 $q=i\times j$ 拆分成除 $(i,j)$ 外任意两个大于等于 $s$ 的数 $(x,y)$ 的乘积，都满足 $(x,y)$ 「不能在第 $k+1$ 轮时确定或者能够在第 $k-1$ 轮时确定」，那么当前 Alice 可以确定。

同样，对于 Bob， 只需要把乘积改成加法即可。

Code

const int N = 5e2, LIM = 4e2 + 23;
using namespace std;
int s, t;
int f[155][N][N];
char name[10];
bool dpBob(int, int, int);
bool dpAlice(int, int, int);
bool ckBob(int, int, int);
bool ckAlice(int, int, int);
int main(){

    //freopen("1.in", "r", stdin);

    fin >> s >> name >> t;
    
    int len = strlen(name);
    
    for(int k = 0; k <= t; ++k)
    for(int i = s; i <= LIM; ++i)
    for(int j = i; j <= LIM; ++j){
        if(k - 2 >= 0)
            f[k][i][j] = f[k - 2][i][j];
        if((k & 1) ^ (len == 3)) f[k][i][j] |= dpBob(k, i, j);
        else f[k][i][j] |= dpAlice(k, i, j);
    }

    int sum = s + s, turn = (t & 1) ^ (len == 3); // 0:Bob 1:Alice
    
    while("Shot me down."){
        for(int i = s; i <= sum / 2; ++i){
            int j = sum - i;
            bool flag = f[t][i][j];
            if(flag == 0) continue;
            for(int k = 0; k < t; ++k)
                flag &= f[k][i][j] == 0;
            if(flag == 0) continue;
            if(turn) flag &= ckAlice(t, i, j);
            else flag &= ckBob(t, i, j);
            if(flag){
                cout << i << " " << j << endl;
                exit(0);
            }
        }
        ++sum;
    }

    return 0;
}
bool dpBob(int k, int a, int b){
    int up = (a + b) / 2, cnt = 0;
    int chs = -1;
    for(int i = s; i <= up; ++i){
        int j = a + b - i;
        if(k == 0 or f[k - 1][i][j] == 0)
            chs = i, ++cnt;
    }
    if(cnt == 1 and chs == a)
        return true;
    return false;
}
bool dpAlice(int k, int a, int b){
    int up = sqrt(a * b), cnt = 0;
    int chs = -1;
    for(int i = s; i <= up; ++i){
        if(a * b % i != 0) continue;
        int j = a * b / i;
        if(k == 0 or f[k - 1][i][j] == 0)
            chs = i, ++cnt;
    }
    if(cnt == 1 and chs == a)
        return true;
    return false;
}
bool ckBob(int k, int a, int b){
    int up = (a + b) / 2, cnt = 0;
    int chs = -1;
    for(int i = s; i <= up; ++i){
        int j = a + b - i;
        if((k < 2 or f[k - 2][i][j] == 0) and f[k][i][j])
            chs = i, ++cnt;
    }
    if(cnt == 1 and chs == a)
        return true;
    return false;
}
bool ckAlice(int k, int a, int b){
    int up = sqrt(a * b), cnt = 0;
    int chs = -1;
    for(int i = s; i <= up; ++i){
        if(a * b % i != 0) continue;
        int j = a * b / i;
        if((k < 2 or f[k - 2][i][j] == 0) and f[k][i][j])
            chs = i, ++cnt;
    }
    if(cnt == 1 and chs == a)
        return true;
    return false;
}