「FSLOI Round I」石子 题解
题目大意
题目的核心是通过特定规则移动石子，直到一方无法操作而失败。我们需要判断游戏的结果是平局（Draw）、小F获胜（F）还是小L获胜（L）。
题意还是太简单了。
关键规则：
- 每次操作需选择两堆石子 \(i\) 和 \(j\)，满足 \(a_i < x < a_j\)（ \(x\) 为平均值）。
- 从 \(j\) 堆移 \(k\) 个石子到 \(i\) 堆。
- 小F先手，双方都采用最优策略。
解题思路
-
平局判断：如果存在某堆石子与平均值的差值不是k的倍数，则无法通过操作使所有石子堆达到平衡状态，游戏会无限进行，结果为
Draw。 -
胜负判断：若所有差值都是 \(k\) 的倍数，则可以计算出总的有效操作次数。每次操作会使总操作次数减 \(1\) ，最后：
- 若总操作次数为奇数，先手小F获胜。
- 若总操作次数为偶数，后手小L获胜。
代码实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n,k,ave,a[200010];
signed main(){cin>>t;while(t--){int sum=0;cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];ave=sum/n;int flg=0;// 检查是否存在无法通过k调整到平均值的石子堆for(int i=1;i<=n;i++) if(abs(a[i]-ave)%k!=0) flg=1;if(flg){cout<<"Draw"<<endl;continue;}// 计算总操作次数int num=0;for(int i=1;i<=n;i++) num+=abs(a[i]-ave)/k;num/=2; // 每次操作会处理两个堆，所以总操作次数是总和的一半// 根据操作次数的奇偶性判断胜负cout<<(num%2?"F":"L")<<endl;}return 0;
}
时间&空间复杂度
- 时间复杂度：\(O(T×n)\) ,其中T是测试用例数量，
n是每堆石子的数量 - 空间复杂度：\(O(n)\) ，用于存储石子数量的数组。
AC记录