Posts

hdu 2873题目链接 题意：n*m个格子，有若干炸弹。对于在第一行或者第一列的炸弹，爆炸后会到那一行或者那一列的更前面（总的来说就是更靠近左上角）的位置。对于其他位置的炸弹，爆炸后会生成两个炸弹，分别到那一行的更前面或者那 一列的更前面。问先手是否有必赢策略。

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}

hdu1907题目链接 题意：n堆石子，每次选一堆，最少拿一个，最多拿光那一堆，拿走最有一个的人输。 问是否有必胜策略。 思路：anti-nim问题。。。 要用到sj定理（是啥。。。?)

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

hdu 1404题目链接 题意：一个数字串，每次可以选择一位减少任意大小到一个非负数，或者清除一个0以及该位右边的所有数字。问是否有必胜策略。。 思路：定义来搞。。所有能一步走到p点的都是n点，那么如果我们现在知道p点，就可以反过来推n点。。

终于忍不了因为没办法科学上网而不能做什么事的感觉了。。。 买了班瓦工 20刀/年。。。搭了ss。。然后全平台（ios/androd/fedora/win）的上网问题就全解决了。。。

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 1517 题目链接 题意：初始为1，每次可以乘2..9中的一个数，最先达到或者超过n的人胜利。问谁有必赢策略。。 思路：一开始想用sg函数。。然而n太大（4e10）。。。绝对会超时。。。

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

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

hdu1847题目链接 题意：n个石子，每次只能取2的幂次个。。。问先手是否有必赢策略。。。 思路：画n点p点。。。发现n为３的倍数的时候先手必输。。。否则先手必赢。。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年07月20日 星期三 18时54分46秒 4File Name :code/hdu/1847.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 while (scanf("%d",&n)!=EOF) 41 { 42 if (n%3==0) 43 { 44 puts("Cici"); 45 } 46 else 47 { 48 puts("Kiki"); 49 } 50 } 51 52 #ifndef ONLINE_JUDGE 53 fclose(stdin); 54 #endif 55 return 0; 56} 也可以利用sg函数求解。。。 从这里我们可以看出，sg函数类似于母函数，本身并不是一类问题，而是一种求解问题的工具。

参考资料　（后面的证明写错了，差评，不要看，看图就好了） 1 1. 题目1：今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根， 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。

hdu 2147 题目链接 题意：一个n*m的方格，有一个棋子初始在右上角（１，m），每次可以将棋子向下或者向左或者向左下移动**一个格子，**不能移出边界，当无路可走的时候就输了，问谁存在必赢策略。

hdu 1846 题目链接 题意：有n个石子，每次最多取m个，最少取１个，如果没有石子可取就输了。给出n,m，两个人都很聪明，问先手和后手谁赢。。 思路： 首先定义几个概念： p点：即必败点，某玩家位于此点，只要对方无失误，则必败

cf689C 题意：给出一个m。。问恰好使得不超过某个n的a*b^3（a,b是正整数）的方案数为m的n是多少。。。 思路：暴力+二分。。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年07月18日 星期一 15时58分55秒 4File Name :code/2016whust/G.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; 33LL m,n; 34LL ans; 35LL cal( LL x) 36{ 37 LL res = 0LL; 38 for ( LL i =2 ; i * i * i <= x ; i++) 39 res+=x/(i*i*i); 40 return res; 41} 42int main() 43{ 44 #ifndef ONLINE_JUDGE 45 freopen("code/in.txt","r",stdin); 46 #endif 47 48 cin>>m; 49 n = 0 ; 50 51 LL cur = 1LL<<60; 52// cout<<"cur:"<<cur<<endl; 53 while (cur!=0LL) 54 { 55 LL tmp = cal(n+cur); 56 if (tmp<m) n +=cur; 57 58 cur >>=1LL; 59 } 60 n++; 61// cout<<" n:"<<n<<endl; 62 if (cal(n)!=m) ans = -1; 63 else ans = n; 64 65 cout<<ans<<endl; 66 67 68 #ifndef ONLINE_JUDGE 69 fclose(stdin); 70 #endif 71 return 0; 72}

cf689B题目链接 题意：n点。。点i到点j的代价是|i-j|..给出n条近路。。。a[i]表示点i到a[i]的代价为1（注意近路不一定就近） 思路：一开始建边卡了一下。。。实际上只要连相邻的就好了。。。然后边表只开了2N蠢哭。。。实际上应该3M…因为连相邻的边是双向的。。。再加上近路的单向。。。然后spfa就好了。。。。

cf689A 思路：一个老式的电话键盘。。。。给出一个拨号的移动路径。。。问这个路径是否唯一。 思路：如果唯一就说明。。。不能平移。。。否则不唯一。。 平移可以上下左右。。所以先写4个常亮数组。。。标记平移后的结果。。。设置不合法位就可以了。。。

cf682C题目链接 题意：给一棵树。。有点权和边权。。。如果一个点v的子树中存在某点u，满足dis(u,v)>a[u]，那么点v就非常sad… dis(u,v)表示点u到v的距离。。。a[u]是u的点权。。现在问最少要删除多少个叶子节点才能使得没有点节点感到sad..

cf682B题目链接 题意：给出n个数。。每个数可以任意减小到一个正整数。。。问进行恰当的操作后。。。最小的没有出现的正整数的最大可能取值。。 思路：傻逼题。。。直接离散化。。。。注意不能超过初始。。。

cf682A题目链接 题意：两个数组，分别为1..n和1..m。。。从两个数组中各取一个，问和能被5整除的方案数。。。 思路：傻逼题。。。统计%5。。。然后乘法原理。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年07月18日 星期一 12时32分22秒 4File Name :code/2016whust/A.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=1E6+7; 34int n,m; 35LL a[N],b[N]; 36int main() 37{ 38 #ifndef ONLINE_JUDGE 39 freopen("code/in.txt","r",stdin); 40 #endif 41 42 cin>>n>>m; 43 ms(a,0); 44 ms(b,0); 45 for ( int i = 1 ; i <= n ; i++) 46 { 47 int x = i % 5; 48 a[x]++; 49 } 50 for ( int i = 1 ; i <= m ; i++) 51 { 52 int x = i % 5; 53 b[x]++; 54 } 55 LL ans = 0; 56 ans = a[0]*b[0]+a[1]*b[4]+a[2]*b[3]+a[3]*b[2]+a[4]*b[1]; 57 cout<<ans<<endl; 58 59 #ifndef ONLINE_JUDGE 60 fclose(stdin); 61 #endif 62 return 0; 63}