M_sea

洛谷2148 [SDOI2009]E&D
LuoguBZOJ分析打表后发现 $SG(i)=i-1\text{的二进制表示}$。于是每一对数 $(i,j)$ ...
扫描右侧二维码阅读全文
19
2019/02

洛谷2148 [SDOI2009]E&D

Luogu

BZOJ

分析

打表后发现 $SG(i)=i-1\text{的二进制表示}$。

于是每一对数 $(i,j)$ 的 $SG$ 值就是 $\mathrm{mex}(i-1,j-1)$ 。

然后每一对数的 $SG$ 值都异或起来就行了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

inline int mex(int x) {
    int s=1,ans=0;
    while (x&s) s<<=1,++ans;
    return ans;
}

int main() {
    int T=read();
    while (T--) {
        int n=read()/2,ans=0;
        for (re int i=1;i<=n;++i) {
            int a=read(),b=read();
            ans^=mex((a-1)|(b-1));
        }
        puts(ans?"YES":"NO");
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 08 : 52 PM

2 条评论

  1. smy

    打表大佬%%%

    1. M_sea
      @smy

      假死了

发表评论