题解
设\(f[p][a][b]\)表示询问了\(p\)次，答案是\(a,b\)是否会被猜出来
然后判断如果\(p = 1\)
第一个问的\(Alice\)，那么\([s,\sqrt{nm}]\)约数只有一个，\(f[p][a][b] = 1\)否则为\(0\)
如果第一个问的\(Bob\)，那么\(a + b - 2 * S <= 1\)那么\(f[p][a][b] = 1\)否则为\(0\)
剩下的按照\(p\)这次操作询问谁，且然后从可能的数对里找\(f[p - 1][i][j]\)为\(0\)的有几个，如果只有1个就猜出来了
同时还要保证，在某个人猜出来之后，另一个猜出来的人询问第\(T + 1\)回合刚好能被猜出来的数对中，也只会问出一个，那么答案就是\(a,b\)了
用记搜，跑得还是挺快的
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define MAXN 20005
#define eps 1e-8
#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int f[25][505][505],cnt[505 * 505],g[505][505];
vector<int> v[505 * 505];
int S,T,k;
char c[25];
bool dp(int p,int a,int b) {
if(p == 0) return 0;
if(f[p][a][b] != -1) return f[p][a][b];
if(p == 1) {
if(k == 1) {
if(cnt[a * b] > 1) f[p][a][b] = 0;
else f[p][a][b] = 1;
}
else {
if(a + b - 2 * S <= 1) f[p][a][b] = 1;
else f[p][a][b] = 0;
}
return f[p][a][b];
}
if(dp(p - 1,a,b)) return f[p][a][b] = 1;
if(p % 2 == k) {
int c = 0;
for(auto h : v[a * b]) {
if(!dp(p - 1,h,a * b / h)) ++c;
}
if(c == 1) f[p][a][b] = 1;
else f[p][a][b] = 0;
}
else {
int c = 0;
for(int i = S ; i <= (a + b) / 2 ; ++i) {
if(!dp(p - 1,i,a + b - i)) ++c;
}
if(c == 1) f[p][a][b] = 1;
else f[p][a][b] = 0;
}
return f[p][a][b];
}
bool check(int a,int b) {
if(g[a][b] != -1) return g[a][b];
int c = 0;
if((T + 2) % 2 == k) {
for(auto h : v[a * b]) {
if(dp(T + 1,h,a * b / h) && !dp(T,h,a * b / h)) ++c;
}
}
else {
for(int i = S ; i <= (a + b) / 2 ; ++i) {
if(dp(T + 1,i,a + b - i) && !dp(T,i,a + b - i)) ++c;
}
}
if(c == 1) g[a][b] = 1;
else g[a][b] = 0;
return g[a][b];
}
pii Solve() {
memset(f,-1,sizeof(f));
memset(cnt,0,sizeof(cnt));
memset(g,-1,sizeof(g));
for(int i = S * S ; i <= 500 * 500 ; ++i) {
int t = sqrt(i);
v[i].clear();
for(int j = S ; j <= t ; ++j) {
if(i % j == 0) {
cnt[i]++;
v[i].pb(j);
}
}
}
for(int s = S + S ; s <= 1000 ; ++s) {
for(int i = S ; i <= 500 ; ++i) {
if(i > s) break;
for(int j = i ; j <= s - i ; ++j) {
if(i + j > s) break;
if(dp(T + 1,i,j) && !dp(T,i,j) && check(i,j)) {return mp(i,j);}
}
}
}
}
int main() {
for(int i = 1 ; i <= 25 ; ++i) {
stringstream ss;
string num;
ss << i;
ss >> num;
string str1 = "guess/guess" + num + ".in";
FILE *fin = fopen(str1.c_str(),"r");
fscanf(fin,"%d%s%d",&S,c + 1,&T);
string str2 = "answer/guess" + num + ".out";
FILE *fout = fopen(str2.c_str(),"w");
if(c[1] == 'A') k = 1;
else k = 0;
pii ans = Solve();
fprintf(fout,"%d %d\n",ans.fi,ans.se);
printf("OK with %d task\n",i);
}
return 0;
}