自动搬运

查看原文

来自洛谷，原作者为

	Delov Delovue

搬运于2025-08-24 22:00:24，当前版本为作者最后更新于2023-02-23 16:48:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

可以发现，每次是在根据“不知道”来排除决策集合中的某些东西，例如：

第一轮 A 说不知道，那么积拆分不唯一。

第二轮 B 说不知道，那么说明和对于所有和拆分 $(a,b)$，$a \times b$ 的和拆分不唯一的 $(a,b)$ 不唯一。

第三轮 A 又说不知道，那么对于所有的积拆分 $(a,b)$，$a+b$ 的所有积拆分中，其和拆分不唯一的的积拆分不唯一的 $(a,b)$ 不唯一。

我们发现每次说不知道，就是在嵌套上一个"和/积拆分...不唯一"，那么可以尝试递归解决问题。

函数 $\operatorname {DfsA}(dep,vec)$ 表示之前一共说过 $dep$ 次不知道，剩余决策集合为 $vec$，此时轮到 A 判断，返回 A 此时的决策集合。

$\operatorname {DfsB}(dep,vec)$ 同理。

考虑如何排除，就是枚举剩余决策集合的每个元素 $(a,b)$，将其和/积算出并作和/积拆分，考虑满足要求的拆分是否唯一，若不唯一则其仍是一个合法决策，否则排除之。是否满足要求则是一个递归问题，递归边界即为之前没有说过“不知道”，此时判断条件就是和/积拆分方案数。

我们通过这样的处理可以找出前 $t$ 次两人都说不知道之后两人各自的剩余决策集合，现在我们需要看他们是否“知道”了。

判断方法相同，我们就枚举所有决策，看是否存在唯一一个满足要求的，判断是否满足的处理要求同上，递归处理即可。发现递归过程中，除了第一层决策集合可能是特殊的，往下递归后每层的决策集合实际上就是某个数的和/积拆分的所有方案，于是我们可以对这些过程记忆化。

跑的甚至比提交答案快？应该是所有提交代码里最快的。

code

#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i) 
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
using namespace std;

int Lim,Ned;
string str;

unordered_map<int,int>MapB,MapC;

int ExpandB(int x){
	if(MapB.count(x))return MapB[x];
	int res=0;for(int i=Lim;x-i>=i;++i)++res;
	return MapB[x]=res;
}

int ExpandC(int x){
	if(MapC.count(x))return MapC[x];
	int res=0;for(int i=Lim;x/i>=i;++i)if(x%i==0)++res;
	return MapC[x]=res;
}

vector<pii> DfsA(int ,const vector<pii>&);
vector<pii> DfsB(int ,const vector<pii>&);

vector<pii>ExA(int x){ vector<pii>res;for(int i=Lim;i*i<=x;++i)if(x%i==0)res.emplace_back(i,x/i);return res; }
vector<pii>ExB(int x){ vector<pii>res;for(int i=Lim;i+i<=x;++i)res.emplace_back(i,x-i);return res; }

unordered_map<int,int>MapAx[20],MapBx[20];

int CfsA(int,int);
int CfsB(int,int);

int CfsA(int dep,int x){
	if(dep==0)return ExpandC(x);
	if(MapAx[dep].count(x))return MapAx[dep][x];
	vector<pii>vec=ExA(x);int res=0;
	for(auto it : vec)res+=(CfsB(dep-1,it.fir+it.sec)>1);
	return MapAx[dep][x]=res;
}

int CfsB(int dep,int x){
	if(dep==0)return ExpandB(x);
	if(MapBx[dep].count(x))return MapBx[dep][x];
	vector<pii>vec=ExB(x);int res=0;
	for(auto it : vec)res+=(CfsA(dep-1,it.fir*it.sec)>1);
	return MapBx[dep][x]=res;
}

vector<pii> DfsA(int dep,const vector<pii> & vec){
	if(dep==0)return vec;
	vector<pii>res;
	for(auto it : vec)if(CfsB(dep-1,it.fir+it.sec)>1)res.emplace_back(it);
	/*for(auto it : vec){
		vector<pii> tmp=DfsB(dep-1,ExB(it.fir+it.sec));
		if(tmp.size()>1)res.emplace_back(it);
	}*/
	return res;
}

vector<pii> DfsB(int dep,const vector<pii> & vec){
	if(dep==0)return vec;
	vector<pii>res;
	for(auto it : vec)if(CfsA(dep-1,it.fir*it.sec)>1)res.emplace_back(it);
	/*for(auto it : vec){
		vector<pii> tmp=DfsA(dep-1,ExA(it.fir*it.sec));
		if(tmp.size()>1)res.emplace_back(it);
	}*/
	return res;
}

int Get(int n,int m){
	vector<pii>vecA=ExA(n*m),vecB=ExB(n+m);
	if(n==78 && m==108){ cerr<<"\n"; }
	if(str=="Alice"){
		Rep(i,1,Ned){
			if((i&1)){ vecA=DfsA(i-1,vecA);if(vecA.size()<=1)return 0; }
			else{ vecB=DfsB(i-1,vecB);if(vecB.size()<=1)return 0; }
		}
		if(!(Ned&1)){
			vecA=DfsA(Ned,vecA);int res=0;
			for(auto it : vecB){
				if(DfsA(Ned,ExA(it.fir*it.sec)).size()==1)++res;
			}
			if(vecA.size()==1 && res==1)return Ned;
			else return 0;
		}else{
			vecB=DfsB(Ned,vecB);int res=0;
			for(auto it : vecA){
				if(DfsB(Ned,ExB(it.fir+it.sec)).size()==1)++res;
			}
			if(vecB.size()==1 && res==1)return Ned;
			else return 0;
			
		}
	}
	if(str=="Bob"){
		Rep(i,1,Ned){
			if((i&1)){ vecB=DfsB(i-1,vecB);if(vecB.size()<=1)return 0; }
			else { vecA=DfsA(i-1,vecA);if(vecA.size()<=1)return 0; }
		}
		if(!(Ned&1)){
			vecB=DfsB(Ned,vecB);int res=0;
			for(auto it : vecA){
				if(DfsB(Ned,ExB(it.fir+it.sec)).size()==1)++res;
			}
			if(vecB.size()==1 && res==1)return Ned;
			else return 0;
		}else{
			vecA=DfsA(Ned,vecA);int res=0;
			for(auto it : vecB){
				if(DfsA(Ned,ExA(it.fir*it.sec)).size()==1)++res;
			}
			if(vecA.size()==1 && res==1)return Ned;
			else return 0;
		}
	}
	return 0;
}

void solve(){
	cin>>Lim>>str>>Ned;
	for(int s=Lim+Lim;;++s){
		for(int i=Lim;s-i>=i;++i)
			if(Get(i,s-i)==Ned)return cout<<i<<" "<<s-i<<"\n",void();
	}
}

int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);return solve(),0; }