UVA-1482 Playing With Stones(SG函数打表找规律)

左手的ㄟ右手 2022-06-10 03:15 127阅读 0赞

Playing With Stones    UVA1482

![Center][]

今天训练博弈的时候看到了这道题，看到1e18的数据很快就把SG函数表打了出来，准备找规律，但是无论怎么找都找不到一个比较好的公式，后来看了别人的博客，发现只要a是奇数，那么SG(a)=SG(a/2)，这个规律实在是高明，让这道题直接变成水题，膜拜大佬。

#pragma comment(linker, "/STACK:1024000000,1024000000") 
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 1000005;
    const int MOD = 1e9 + 7;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    
    LL getSG(LL x)
    {
    	if (x & 1)
    		return getSG(x / 2);
    	return x / 2;
    }
    
    int main()
    {
    	int T;
    	int n;
    	LL ans;
    	LL x;
    	scanf("%d", &T);
    	while (T--)
    	{
    		ans = 0;
    		scanf("%d", &n);
    		while (n--)
    		{
    			scanf("%lld", &x);
    			ans ^= getSG(x);
    		}
    		if (ans == 0)
    			printf("NO\n");
    		else
    			printf("YES\n");
    	}
    }

[Center]: /images/20220610/40b5e789fe5d4d90ac167e08404ae87b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，127人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 1564-Play a game（博弈-找规律）

Play a game Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/

亦凉/ 2022年08月22日 03:52/ 0 赞/ 122 阅读

相关 uva10067 Playing with Wheels 【建图+最短路】

题目：[uva10067 Playing with Wheels ][uva10067 Playing with Wheels] 题意：给出一个机器，有四个循环的轮

水深无声/ 2022年08月12日 00:07/ 0 赞/ 83 阅读

相关 uva 10673 ——Play with Floor and Ceil

题意：给定两个数n和m，对于n/m一个向上取整，一个向下取整，然后得到一个方程即P\floor(n/m）+q\ceil(n/m)=n; 求该公式中p和q的值的大小。

太过爱你忘了你带给我的痛/ 2022年08月09日 13:49/ 0 赞/ 101 阅读

相关 HDU 2897-邂逅明下（博弈-SG函数打表找规律）

邂逅明下 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

小灰灰/ 2022年07月24日 05:09/ 0 赞/ 115 阅读

相关 Parity check——打表找规律+大数取模

Think： 1打表找规律，寻找循环节 2字符串存储大数+大数取模 [SDUT题目链接][SDUT] Parity check Time Limit: 2000

缺乏、安全感/ 2022年06月16日 09:23/ 0 赞/ 130 阅读

相关 UVA-1482 Playing With Stones(SG函数打表找规律)

Playing With Stones UVA1482 ![Center][] 今天训练博弈的时候看到了这道题，看到1e

左手的ㄟ右手/ 2022年06月10日 03:15/ 0 赞/ 128 阅读

相关 UVa 11401 Triangle Countin（找规律）

Triangle Counting Input: Standard Input Output: Standard Output ![p11401.gif][] You

╰+攻爆jí腚メ/ 2022年06月04日 03:56/ 0 赞/ 245 阅读

相关炫酷数学（暴力+打表找规律）

链接：[https://ac.nowcoder.com/acm/contest/331/J][https_ac.nowcoder.com_acm_contest_331_J]

迈不过友情╰/ 2022年03月21日 08:39/ 0 赞/ 171 阅读

相关 (打表找规律+前缀异或和)MORE XOR

题目链接：[https://nanti.jisuanke.com/t/38230][https_nanti.jisuanke.com_t_38230] 比赛的时候也在推规律，

待我称王封你为后i/ 2022年02月16日 14:02/ 0 赞/ 167 阅读

相关西安邀请赛-L（打表找规律）

题目链接：https://nanti.jisuanke.com/t/39279 题意：给定n个不同的数表示的序列，定义两种操作：1. 交换前一半和后一半（如果有奇数个，则中间

一时失言乱红尘/ 2021年12月21日 01:05/ 0 赞/ 204 阅读