【自用复习】牛客每日一题2026.4.22

参考@OvO_CYX的题解
原题链接

一开始还在想没放的部分组成的连通块数量和胜败态的关系，但是很复杂，而且很难列出都没放的情况属于哪种状态
因为位置只有16个，有2 16 = 65535 2^{16}=65535216=65535种棋局情况，暴力搜索得到每个棋局的状态
根据SG定理，后继一个状态为必败态，那么本状态为必胜态

intdx[4]={1,-1,0,1};intdy[4]={0,1,1,1};vector<int>st(N,-1);intarray_to_num(vector<vector<int>>a){intbt=0,res=0;forr(i,0,3){forr(j,0,3)res+=(1<<bt)*a[i][j],bt++;}returnres;}vector<vector<int>>num_to_array(intnum){vector<vector<int>>a(5,vector<int>(5));forr(i,0,3){forr(j,0,3){intbt=i*4+j;a[i][j]=((num>>bt)&1);}}returna;}intcnt=0;voiddfs(intnow){if(st[now]!=-1)return;cnt++;st[now]=0;vector<vector<int>>anow=num_to_array(now);// 判断now状态输赢forr(i,0,3){forr(j,0,3){if(anow[i][j]==0){// 先放一个anow[i][j]=1;intnnow=array_to_num(anow);dfs(nnow);st[now]|=(st[nnow]==0);// 后继状态输 本状态赢anow[i][j]=0;// 恢复现场 保持本次now不变 用于后续{i,j}的判断// 如果不恢复 遍历状态会少// 放多个forr(d,0,3){// 每个方向有单独的anxt 省去回复现场vector<vector<int>>anxt=anow;anxt[i][j]=1;intnx=i,ny=j;forr(s,1,2){nx+=dx[d],ny+=dy[d];if(nx<0||nx>3||ny<0||ny>3||anxt[nx][ny])break;anxt[nx][ny]=1;intnxt=array_to_num(anxt);dfs(nxt);st[now]|=(st[nxt]==0);}}}}}}voidinit(){// 预处理出每个棋局的状态st[65535]=0;// 对先手必败dfs(0);}voidsolve(){vector<vector<int>>mp(5,vector<int>(5));intnum=0;forr(i,0,7){forr(j,0,min(i,7-i-1)){// cout<<i<<' '<<j<<endl;charc;cin>>c;intid;if(i<=3)id=i+j*3;elseid=(3+(i-3)*4+j*3);intx=id/4,y=id%4;mp[x][y]=(c=='*');}}cout<<(st[array_to_num(mp)]?"Alice":"Bob")<<endl;}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int_=1;init();// cout<<cnt<<endl;cin>>_;while(_--){solve();}return0;}