题目链接:https://ac.nowcoder.com/acm/contest/847/E
首先,这是我用打表猜出来的规律(想知道正解的巨巨可以绕道):如果禁手点为原始必败点并且横坐标小于等于三且不在右侧斜边上,则原先的胜负状态会逆转。
以下是打表代码:
#include <bits/stdc++.h>
using namespace std;
const int N=1007;
int a[N][N],n,b[N][N],q;
void f(int x,int y){
for(int i=n;i>=1;i--){
for(int j=min(i,n-1);j>=1;j--){
if(i==x&&j==y)continue;
if(a[i+1][j]==0||a[i][j+1]==0||a[i+1][j+1]==0){
a[i][j]=1;
}
else a[i][j]=0;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
printf("%d",a[i][j]);//1代表在该点行动的人必胜,0代表必败。
}printf("\n");
}
}
int main()
{
while(cin>>n){
for(int i=1;i<=n+1;i++){
for(int j=1;j<=n+1;j++)a[i][j]=1;
}
a[n][n]=0;
f(n,n);
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)b[i][j]=a[i][j];
for(int i=2;i<=n;i++){
for(int j=1;j<=min(i,n-1);j++){
if(a[i][j]==1)continue;
printf("%d %d\n",i,j);//i,j表示禁手点坐标
a[i][j]=1;
f(i,j);
for(int p=1;p<=n;p++){
for(int q=1;q<=p;q++)a[i][j]=b[i][j];
}
}
}
}
return 0;
}
接下来分析一下初始的胜负情况;
首先,显然在(n,n)点行动者是必败的,然后我们就可以进行递推:如果在某个点能走到使对方必败的点,那该点就是必胜的,而如果我怎么走都会落到使对方必胜的点,那该点就是必败的。
判断式:
if(a[i+1][j]==0||a[i][j+1]==0||a[i+1][j+1]==0){//如果我下一步能走到必败点
a[i][j]=1;
}
else a[i][j]=0;
然后,我们可以发现,选取必胜点对于游戏胜负是没有影响的,证明如下:
如果我走向必胜点,那我肯定是必败的了,所以我不会选择走必胜点,而禁手的效果同样如此,因此我们可以假设,禁手点=必胜点。
接下来我们只需要分析将必败点变为禁手的情况了,相当于将一个必败点变为必胜点,这样肯定会对全局有一定的影响,经过打表,外加上我明察秋毫(老眼昏花了一个小时)的观察力,将一个点选为禁手对整个棋盘的胜负点的影响是具有区间性的。因此我们可以简单猜出结论。
以下是ac代码:
#include <bits/stdc++.h>
using namespace std;
const int N=1007;
int a[N][N],n,q;
int main()
{
cin>>n>>q;
while(q--){
int x,y;
scanf("%d%d",&x,&y);
int flag=n%2;
if((n-x+1)%2==0||(n-y+1)%2==0){
if(n%2==0)
printf("Alice\n");
else printf("Bob\n");
}
else{
if(x==y){
if(n%2==0)
printf("Alice\n");
else printf("Bob\n");
}
else{
if(y<=3){
flag=!flag;
}
if(flag==0)printf("Alice\n");
else printf("Bob\n");
}
}
}
return 0;
}