↓ 跳过正文
  1. Posts/

hdu 2509 Be the Winner (anti-sg,sg函数,sj定理)

·227 字·1 分钟

hdu2509题目链接 题意:???

思路:同1907

代码实现
 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年07月23日 星期六 04时41分38秒
 4File Name :code/hdu/2509.cpp
 5************************************************ */
 6
 7#include <cstdio>
 8#include <cstring>
 9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33int n;
34int main()
35{
36	#ifndef  ONLINE_JUDGE
37	freopen("code/in.txt","r",stdin);
38  #endif
39
40
41	while (~scanf("%d",&n))
42	{
43	    int sum =  0;
44	    int cnt = 0 ;
45	    for ( int i = 1 ; i <= n ; i++)
46	    {
47		int x;
48		scanf("%d",&x);
49		sum^=x;
50		if (x>1) cnt++;
51	    }
52	    if ((sum==0&&cnt==0)||(sum>0&&cnt>0))
53	    {
54		puts("Yes");
55	    }
56	    else
57	    {
58		puts("No");
59	    }
60	}
61
62  #ifndef ONLINE_JUDGE
63  fclose(stdin);
64  #endif
65    return 0;
66}

相关文章

hdu 1730 Northcott Game (二维sg函数)

·693 字·2 分钟
hdu 1730 题意:n行格子,每行m个,每行有一黑一白两个棋子,给定初始位置,先手执黑棋,后手执白棋,每次可以在同一行内向左移动,不能超过边界,且不能越过对方的棋子,同一个格子只能有一个棋子。问先手是否必赢。

hdu 1536 S-Nim (sg函数)

·350 字·1 分钟
hdu 1536题目链接 题意:还是若干堆石子,但是每次取的个数只能是集合S中有的数。。问是否必赢。。。 思路:sg函数。。。1A 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年07月20日 星期三 23时32分48秒 4File Name :code/hdu/1536.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E4+7; 34int sg[N]; 35bool vis[N]; 36int ok[N]; 37int k,m; 38 39void sg_init() 40{ 41 ms(sg,0); 42 43 for ( int i = 1; i < N ; i++) 44 { 45 ms(vis,false); 46 for ( int j = 1 ; j <= k ; j++) 47 if (i-ok[j]>=0) vis[sg[i-ok[j]]] = true; 48 49 for ( int j = 0 ; ; j++) 50 if (!vis[j]) 51 { 52 sg[i] = j; 53 break; 54 } 55 } 56} 57int main() 58{ 59 #ifndef ONLINE_JUDGE 60 freopen("code/in.txt","r",stdin); 61 #endif 62 63 while (~scanf("%d",&k)) 64 { 65 if (k==0) break; 66 ms(ok,0); 67 for ( int i = 1 ; i <= k ; i++) scanf("%d",&ok[i]); 68 sg_init(); 69 scanf("%d",&m); 70// cout<<"m:"<<m<<endl; 71 while (m--) 72 { 73 int num; 74 scanf("%d",&num); 75 int sum = 0 ; 76 while (num--) 77 { 78 int x; 79 scanf("%d",&x); 80 sum^=sg[x]; 81 } 82 if (sum==0) printf("L"); 83 else printf("W"); 84 } 85 printf("\n"); 86 } 87 88 #ifndef ONLINE_JUDGE 89 fclose(stdin); 90 #endif 91 return 0; 92}

hdu 1848 Fibonacci again and again (sg函数)

·448 字·1 分钟
hdu 1848题目链接 题意:三堆石头,每次任选一堆取,取的石子数目必须是斐波那契数列中的数(1,2,3,5,8….)问先手是否有必赢策略。 思路:sg函数即可。。。。这次sg函数的优越性终于体现出来了。。。其他方法估计很难写吧。。

hdu 1850 Being a Good Boy in Spring Festival (nim游戏问必胜方案数,sg函数)

·422 字·1 分钟
hdu1850题目链接 题意:n堆石子。。每堆可以取任意多个。。。先取完的赢。。问先手能否赢。。能赢的话第一步有几种取法。。 思路:sg函数。。对于方案数,可以用nim游戏的结论。 以及。。sg函数。。如果走的步数是任意的。。也就是没有限制。。。那么sg[i] = i…此时也就退化成了一般的nim游戏。。。