题意:
有一排 n 个石子,2个操作,Alice先手,不能操作的输。
操作 1:选择连续的 <= k 个石子的序列拿走
操作 2:选择连续的 k 个石子拿走,并必须留下 2 个非空序列
思路:
博弈,因为数据范围很大,很明显只能 SG 打表找规律了。
很明显 sg[0] = 0, sg[1~k] = 1, 因为进行操作 2 时,n 个石子一定会分成 2 段。
很明显有 n - k 种可能。SG 打表找规律即可。
打表代码:
// -----------------
const int N = 1e6 + 10;
int f[N];
int k;
int sg(int n)
{
if(f[n] != -1) return f[n];
set<int> S;
rep(i,1,n)
{
int j = n - i - k;
if(j <= 0) continue;
S.insert(sg(j) ^ sg(i));
}
int x = 0;
while(S.count(x)) x ++;
f[n] = x;
return x;
}
void dabiao()
{
cin >> k;
mem(f,-1);
f[0] = 0;
rep(i,1,k) f[i] = 1;
rep(i,k+1,100) f[i] = sg(i);
rep(i,1,1000) cout << f[i] << " ";
cout << endl;
rep(i,1,100)
{
if(f[i]==0)
{
cout << i << " ";
}
}
// 规律 :
// n <= k Alice n = k + 1 Bob
// n -= k + 1 循环节开始
// n % (4 * k + 2) = 0 Bob
}
AC代码:
void solve()
{
cin >> k >> n;
if(n >= k + 1)
{
n -= (k + 1);
if(n % (k * 4 + 2) == 0)
{
cout << "Bob" << endl; return;
}
}
cout << "Alice" << endl;
}