【Surreal Number】chocolate

Description

zzd和hcy在一起的时候喜欢用巧克力玩一些游戏。
一天,他们得到了n块巧克力,每块巧克力的大小是\(x_i*y_i\)的矩形。他们先是确定了这样的规则:两人轮流操作,操作是将一块巧克力完全切割成两块巧克力,并且边长必须始终为整数,hcy先操作,不能操作者输。
他们思考了一下发现这游戏太简单了,根本不能显示出他们的智慧。于是,他们又加入了一条规则:且zzd只能够横着切,hcy只能竖着切,即对于一块x*y的巧克力,zzd只能切成大小为z*y和(x-z)*y的两块,hcy只能切成大小为x*z和x*(y-z)的两块。
现在,zzd想问你对于当前的游戏,他是否有必胜的策略?

Input

第一行一个整数T,表示数据的组数。
对于每组数据:
第一行一个整数n,表示巧克力的初始块数。
接下来一共n行,每行两个数\(x_i,y_i\),描述每块巧克力的大小。

Output

对于每组数据,如果zzd有必胜的策略则输出一行“YES”,否则输出一行“NO”(不带引号)。

Data Range

\(n \leq 1000,x_i,y_i \leq 10^9,T \leq 20。\)

Solution

花了大概半个下午+一个晚上的时间拜读Matrix67的文章。。写得太好了%%%比集训队论文好看多了

放个链接(WordPress升级后的新功能好6啊)

实数、超实数和博弈游戏:数学的结构之美

和sg函数还是有那么一些相通点的。。感觉比sg还简单些呢(雾

Surreal Number的基础知识我就不讲了 Matrix67讲的非常好了

那么直接进入这道题

。。删掉了一大段

本来想写个证明证明这道题的 然后发现不会证啊不会证= =

似乎只能打表了

然后就会发现\(S(x,y)=S(\lfloor\frac{x}{2}\rfloor,\lfloor\frac{y}{2}\rfloor)\)

于是瞬间变水题

 

说点什么

  Subscribe  
提醒