「FSLOI Round I」石子 题解

· · 题解

解题思路

Subtask 1

由于 a 中元素全部相等，小 F 作为先手无法进行操作，胜者必定为小 L。

Subtask 2

由于 k 等于 1，所以每次操作都会使整个序列趋于平均且不会出现对局永远进行的情况。

设序列的平均数为 x，容易证明所有小于 x 的数与 x 的差值之和等于所有大于 x 的数与 x 的差值之和。采用反证法，若不相等，则序列的平均数必定不为 x。

所以我们统计所有数与 x 的差的绝对值之和，再除以二，将得到的值记为 num，那么经过 num 次操作之后序列中元素将全部相等。我们只需判断 num 除以 2 的余数就能够判断是小 F 获胜还是小 L 获胜了。

Subtask 3 & 4 & 5

有了 Subtask 2 的铺垫，正解呼之欲出。

首先我们判断，如果存在一个 i，使得 a_i 与 x 的差不能整除 k，则对局将无限进行下去。为什么？考虑反向思考，对局结束的条件一定是所有元素都等于 x，而此时不可能对 a_i 进行操作使得它等于 x，所以对局也就永远不会结束。

接下来考虑对局会在有限步后结束的情况。和 Subtask2 类似，我们这次记 num 为所有数与 x 的差的绝对值除以 k 之和，再除以二的结果。此时对局也将会在 num 步之后结束。故只需判断 num 除以 2 的余数即可。

代码示例

#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;
        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;
}