Java教程

[博弈论][HEOI2014]人人尽说江南好

本文主要是介绍[博弈论][HEOI2014]人人尽说江南好,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

\(n\) 堆石子排成一排,初始时每队1个。甲乙双方均可进行操作,操作方式为选取任意两堆石子合并为一堆,但需要满足新堆石子数 \(\le m\),否则无法进行操作。不能操作的一方失败,问先手是否必胜。必胜输出0,必败输出1。

结论1

设操作总次数为 \(k\),则 \(k\) 是奇数先手必胜,反之先手必败。

结论2

对于初始石子堆 \(\{1,1,...,1\}(n个)\),当前选手A一定可以将它变成 \(\{m,m,...,m,n\%m\}(n/m个m,/表示整除)\)。
证明:对于任意一个状态,后手选择将当前满足 \(a+b\) 最大的两堆 \(a,b(a+b\le m)\) 合为一堆。选手B会发现自己每次都“前功尽弃”,因为他做的所有工作都会“为A所用”。这就导致最终状态不会存在两堆 \(a_0,b_0\) 满足 \(a_0<m,b_0<m\) 但 \(a_0+b_0>m\)。

结论2'

对于初始石子堆 \(\{1,1,...,2\}(n-1个1)\),当前选手A一定可以将它变成 \(\{m,m,...,m,n\%m\}(n/m个m,/表示整除)\)。操作方式跟结论2一样。

策略

先手如果可以通过结论2的方式,以奇数次操作转移到目标状态,则他一定采用这种方式,先手必胜;
先手如果通过结论2的方式必败(即操作次数为偶数次),那么他在操作了一步之后一定变成结论2'的初状态,这时后手采用结论2'的方式只用操作奇数步就可以得到他的目标状态,即后手必胜,也即先手必败(因此,先手无法通过其他方式取胜)。

归纳得:
当 \(m\ge n\) 时,\(k=n-1\);
否则,当 \(m|n\) 时,\(k=n-n/m\);
否则(当 \(m\nmid n\) 时),\(k=n-(n/m+1)\)。
若 \(k\) 为奇数,先手必胜;反之,后手必胜。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t,n,m;
    cin>>t;
    while(t--){
        cin>>n>>m;
        if(m>=n)cout<<(n-1&1^1)<<endl;
        else if(n%m)cout<<(n-n/m-1&1^1)<<endl;
        else cout<<(n-n/m&1^1)<<endl;
    }
}
这篇关于[博弈论][HEOI2014]人人尽说江南好的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!