题意
有(n)堆石子,每堆有(a_i)个,并且相邻两堆石子的个数互不相同。
两个人轮流取石子,每次取(1)个。取石子的过程中不能打破相邻两堆石子个数不同的规则。
无法再取时,游戏终止。问先手必胜还是后手必胜。
注意:当某一堆个数是(0)时,也算是一堆
数据范围
(1 leq T leq 100)
(1 leq n leq 10^5)
(0 leq a_i leq 10^9)
思路
这道题表面看上去是个博弈,其实稍微转化一下,发现其实就是个模拟题。
可以先考虑一下两堆石子个数不同的规则,这个规则的含义其实就是取石子的过程中,相邻两堆石子数量的大小关系不变。
我们要考虑什么时候游戏结束。不妨设(f(x))为石子个数函数,我们寻找(f(x))的极小值。
设极小值是(I = {i_1, i_2, dots, i_k}),对(forall i in I),令(f(i) = 0, f(i + 1) = f(i - 1) = 1, dots, f(i + k) = f(i - k) = k),依此类推。
最后的答案就是(sum_{i = 1}^n (a_i - f(i)))
注意两端的石子要特判
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100010;
int n;
ll a[N];
int loc[N];
int cnt;
int main()
{
int T;
scanf("%d", &T);
for(int cas = 1; cas <= T; cas ++) {
scanf("%d", &n);
cnt = 0;
ll sum = 0;
for(int i = 1; i <= n; i ++) {
scanf("%lld", &a[i]);
sum += a[i];
}
if(n == 1) {
if(sum % 2) printf("Case %d: Alice
", cas);
else printf("Case %d: Bob
", cas);
continue;
}
for(int i = 2; i < n; i ++) {
if(a[i] < a[i - 1] && a[i] < a[i + 1]) {
loc[cnt] = i;
cnt ++;
}
}
a[0] = -1;
int r = 1;
while(r < n && a[r] < a[r + 1]) {
a[r] = a[r - 1] + 1;
r ++;
}
a[n + 1] = -1;
int l = n;
while(l > 1 && a[l] < a[l - 1]) {
a[l] = a[l + 1] + 1;
l --;
}
for(int i = 0; i < cnt; i ++) {
int t = loc[i];
a[t] = 0;
int l = t - 1, r = t + 1;
while(r < n &&a[r] < a[r + 1]) {
a[r] = a[r - 1] + 1;
r ++;
}
while(l > 1 && a[l] < a[l - 1]) {
a[l] = a[l + 1] + 1;
l --;
}
}
for(int i = 1; i <= n; i ++) {
if(i == 1 && a[1] > a[2]) a[1] = a[2] + 1;
else if(i == n && a[n] > a[n - 1]) a[n] = a[n - 1] + 1;
else if(a[i - 1] < a[i] && a[i] > a[i + 1]) a[i] = max(a[i - 1], a[i + 1]) + 1;
}
for(int i = 1; i <= n; i ++) sum -= a[i];
if(sum % 2) printf("Case %d: Alice
", cas);
else printf("Case %d: Bob
", cas);
}
return 0;
}