聊城哪里做网站,如何找到网站是谁做的,福州网站设计哪家比较好,wordpress 用户站点正题
题目链接:https://www.luogu.com.cn/problem/P3480 题目大意 nnn个石头堆上进行Nim\text{Nim}Nim游戏#xff0c;不过需要满足每次操作前后都有ai≤ai1(i∈[1,n))a_i\leq a_{i1}(\ i\in[1,n)\ )ai≤ai1( i∈[1,n) ) 解题思路
让每一个biai−ai−1b_ia_i-a_{i-1}bi…正题
题目链接:https://www.luogu.com.cn/problem/P3480 题目大意
nnn个石头堆上进行Nim\text{Nim}Nim游戏不过需要满足每次操作前后都有ai≤ai1(i∈[1,n))a_i\leq a_{i1}(\ i\in[1,n)\ )ai≤ai1( i∈[1,n) ) 解题思路
让每一个biai−ai−1b_ia_i-a_{i-1}biai−ai−1就是一个阶梯博弈问题了。
阶梯博弈问题nnn堆石头第iii堆石头有aia_iai个每次一个玩家可以取走若干个第一堆的石头或者将第iii堆的任意个石头丢到第i−1i-1i−1堆里面。
这个问题的sgsgsg函数就是编号为奇数的石头数量的异或和具体证明的话就是如果只看奇数堆石头那么转移奇数的堆里的石头就相当与去掉一些石头。所以如果奇数堆必胜的玩家一定会转移奇数堆的因为如果后手转移偶数堆里的那么先手再把新的转走状态就不会改变。
所以直接做就好了时间复杂度O(Tn)O(Tn)O(Tn) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1100;
int T,n,a[N];
int main()
{scanf(%d,T);while(T--){scanf(%d,n);for(int i1;in;i)scanf(%d,a[i]);for(int in;i1;i--)a[i]a[i]-a[i-1];int ans0;for(int in;i1;i-2)ans^a[i];puts(ans?TAK:NIE);}return 0;
}
