牛客小白月赛2 E.是是非非_综合

牛客小白月赛2 E.是是非非

题目链接

题目描述

坎为水，险阳失道，渊深不测；离为火，依附团结，光明绚丽。
坎卦：水洊至，习坎；君子以常德行，习教事。一轮明月照水中，只见影儿不见踪，愚夫当财下去取，摸来摸去一场空。
离卦：明两作，离，大人以继明照四方。官人来占主高升，庄农人家产业增，生意买卖利息厚，匠艺占之大亨通。

有一些石子堆，第 $i$ 堆有 $a_i$ 个石子。你和算卦先生轮流从任一堆中任取若干颗石子（每次只能取自一堆，并且不能不取），取到最后一颗石子的人获胜。
算卦先生来问你，如果你先手，你是否有必胜策略？若是改动其中几个石子堆中石子的数量呢？

输入描述:

第一行两个正整数 $n,q$ ，表示有 $n$ 个石堆， $q$ 次操作。
第二行 $n$ 个整数，第 $i$ 个数 $a_i$ 表示第 $i$ 个石堆初始有 $a_i$ 个石子。
接下去 $q$ 行，每行两个正整数 $x,y$ ，表示把第 $x$ 堆石子的个数修改成 $y$ 。操作是累计的，也就是说，每次操作是在上一次操作结束后的状态上操作的。

输出描述:

共 $q$ 行，输出每次操作之后先手是否有必胜策略。
如果有，输出 $\texttt{"Kan"}$ ，否则输出 $\texttt{"Li"}$ 。

示例1

输入

输出

Kan
Kan
Li
Li

典型的 Nim 博弈，n 堆石子任选一堆任取若干个，只需要判断抑或和是否为 $0$ 即可，若等于 $0$ 则无必胜策略，每次将第 $x$ 个修改为 $y$ ，只需要将抑或和 $sum$ 修改成 $sum\oplus a[x]\oplus y$ 即可，AC代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,q,x,y,a[N],sum=0;
int main()
{scanf("%d%d",&n,&q);for(int i=1;i<=n;i++){scanf("%d",&a[i]);sum^=a[i];}while(q--){scanf("%d%d",&x,&y);sum=sum^a[x]^y;a[x]=y;if(sum) printf("Kan\n");else printf("Li\n");}return 0;
}