https://ac.nowcoder.com/acm/contest/53366/E
思路:::打表 找规律 即可
打表代码::
//打表程序
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3;
int d[N][N];
int dfs(int x,int y)
{ //记忆化搜索
if(d[x][y]) return d[x][y];//如何搜索过就直接返回答案
//保持x<y方便,,,,因为(x,y)==(y,x)
if(x>y) return dfs(y,x);
//切割左边(题目要求保留面积大的)
for(int i=1;i<=(x-1)/2;i++)
{//搜索所有下一个状态,,下一个状态是-1那么这个状态就是1
if(dfs(i,y)==-1) return 1;
}
//切割y
for(int j=1;j<=(y-1)/2;j++)
{//搜索所有下一个状态,,下一个状态是-1那么这个状态就是1
if(dfs(x,j)==-1) return 1;
}
//没有状态1则返回-1
return d[x][y]=-1;
}
int main()
{ //先出手必然必败
d[1][1]=d[1][2]=d[2][1]=d[2][2]=-1;
for(int i=1;i<=50;i++) //打表找(50,50)全部答案
{
for(int j=1;j<=50;j++)
d[i][j]=dfs(i,j);
}
for(int i=1;i<=50;i++){
//0代表A必胜 X代表A必败
for(int j=1;j<=50;j++)
{
if(d[i][j]==1) cout<<'O';
else cout<<'X';
}
cout<<endl;
}
}
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3;
void _()
{
int n,m;
cin>>n>>m;
n++,m++;
ll bi=1;
int p;
for(int i=1;i<=32;i++)
{
bi<<=1;
if(bi>n){
p=i-1;break;
}
}
if(m>=pow(2,p)&&m<pow(2,p+1)) cout<<"Bob"<<endl;
else cout<<"Alice"<<endl;
}
int main()
{
int t;cin>>t;
while(t--) _();
}
优化代码
#include<bits/stdc++.h>
using namespace std;
int le(int x)
{
int r=0;
while(x){
x/=2;r++;
}
return r;
}
void _()
{
int n,m;
cin>>n>>m;
n++,m++;
if(le(n)!=le(m)) cout<<"Alice"<<endl;
else cout<<"Bob"<<endl;
}
int main()
{
int t;cin>>t;
while(t--) _();
}