用hash 怎么做呢？
#include <iostream>
#include <string>
using namespace std;
int main ()
{
int t;
int n;
while ( scanf ("%d", &t) != EOF )
{
for ( int i = 0; i < t; i ++ )
{
scanf ( "%d", &n );
bool flag = 0;
int count = 0;
while ( n != 1 )
{
if ( n % 2 == 0 )
{
n = n / 2;
}
else if ( n % 2 != 0 )
{
count ++;
flag = 1;
count == 1 ? printf ("%d", n) : printf (" %d", n);
n = n * 3 + 1;
}
}
if ( !flag )
printf ("No number can be output !\n");
else
printf ("\n");
}
}
// system ("pause");
return 0;
}
posted @
2010-08-28 11:27 雪黛依梦 阅读(234) |
评论 (0) |
编辑 收藏
把谁先捐满 n 元，看作共有 n 元每次可取 1——m元，谁最后取光————巴什博弈
#include <iostream>
#include <string>
using namespace std;
int main ()
{
int t, n , m;
scanf ("%d", &t);
while ( t -- )
{
scanf ("%d %d", &n, &m);
n % ( m + 1 ) == 0 ? printf ("Rabbit\n") : printf ("Grass\n");
}
// system ("pause");
return 0;
}
posted @
2010-08-27 22:19 雪黛依梦 阅读(270) |
评论 (0) |
编辑 收藏
//开始的时候没把题目看清,所以分析 N P 状态点的时候没有找出关系，是从 1 开始取牌
#include <iostream>
#include <string>
using namespace std;
int main ()
{
int n;
while ( scanf ("%d", &n ) != EOF )
{
n % 3 == 0 ? printf ("Cici\n") : printf ("Kiki\n");
}
// system ("pause");
return 0;
}
posted @
2010-08-27 21:18 雪黛依梦 阅读(354) |
评论 (0) |
编辑 收藏Nim游戏模型：
有三堆石子，分别含有x1，x2和x3颗石子。两人轮流取石子，每次可以选择一堆，从这堆里取走任意多颗石子，但不能不取。取走最后一颗石子的人获胜。
定理1：Nim游戏的一个状态(x1, x2, x3) 是P状态，当且仅当x1+x2+x3=0。
“Nim和”就是两个数二进制表示的不进位加法，就是两个整数转化成二进制之后进行异或^运算，相同取 0 不同取1
定义：两个数(xm…x0)2和(ym…y0)2，是(zm…z0)2，其中zi=(xi+yi) mod 2，0<=i<=m。
例如，22和51的Nim和是37 即：10110 和 110011 进行^运算，得到 100101
所以如果异或运算之后所有和都是 0 则为 p 状态
那么对应此题是不是就是：共有m个棋子就是有m堆石子，把每个位置的标号等价于该堆石子的数目，取走最后一颗石子的人获胜，就是最后一个回到 0 位置的人获胜，是不是就是nim 博弈问题呢？开始的时候我真的是一点头脑也摸不着，觉得好抽象啊！看了别人的解题报告之后才明白的。
#include <iostream>
#include <string>
using namespace std;
int main ()
{
int m;
int nim[1001];
int ki;
while ( scanf ("%d", &m) != EOF && m )
{
int res = 0;
for ( int i = 0; i < m; i ++ )
{
scanf ( "%d", &ki );
nim[ki] = ki;
res ^= ki; //怎样对两个数进行位运算 //进行位运算后相加和为 0 的话就是就是 p 状态
}
if ( res == 0 ) //先走的人面对的状态，所以走最后一步的人是后走的人，后走的人赢
printf ( "Grass Win!\n " );
else
printf ("Rabbit Win!\n");
}
// system ("pause");
return 0;
}
posted @
2010-08-27 15:12 雪黛依梦 阅读(339) |
评论 (0) |
编辑 收藏
//做博弈题的关键是通过找出的 P 状态点的值来些出和已知值之间的关系
#include <iostream>
#include <string>
using namespace std;
int main ()
{
int n, p, q;
while ( scanf ("%d %d %d", &n , &p, &q) != EOF )
{
if ( n % ( p + q) <= p && n % ( p + q) >= 1 )
printf ("LOST\n");
else
printf ("WIN\n");
}
// system ("pause");
return 0;
}
posted @
2010-08-27 11:20 雪黛依梦 阅读(173) |
评论 (0) |
编辑 收藏寻找平衡状态（也称必败态， 奇异局势），（满足：任意非平衡态经过一次操作可以变为平衡态）
(一)巴什博奕(Bash Game):
只有一堆n个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取m个.最后取光者得胜.
n = (m+1)r+s , (r为任意自然数,s≤m), 即n%(m+1) != 0, 则先取者肯定获胜
(二)威佐夫博奕(Wythoff Game):
有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜.
(ak,bk)(ak ≤ bk ,k=0,1,2,...,n)表示奇异局势
求法：
ak =[k(1+√5)/2], bk= ak + k (k=0,1,2,...,n 方括号表示取整函数)
判断：
Gold=(1+sqrt(5.0))/2.0；
1）假设（a，b）为第k种奇异局势(k=0,1,2...) 那么k=b-a;
2）判断其a==(int)(k*Gold),相等则为奇异局势
（注：采用适当的方法,可以将非奇异局势变为奇异局势.
假设面对的局势是(a,b)
若 b = a,则同时从两堆中取走 a 个物体,就变为了奇异局势(0,0)；
1. 如果a = ak,
1.1 b > bk, 那么,取走b - bk个物体,即变为奇异局势(ak, bk)；
1.2 b < bk 则同时从两堆中拿走 ak – a[b – ak]个物体,变为奇异局势( a[b – ak] , a[b – ak]+ b - ak)；
2 如果a = bk ,
2.1 b > ak ,则从第二堆中拿走多余的数量b – ak
2.2 b < ak ,则 若b = aj (j < k) 从第一堆中拿走多余的数量a– bj; (a > bj)
若b = bj (j < k) 从第一堆中拿走多余的数量a– aj; ( a > aj)
）
例题：pku 1067
(三)尼姆博奕(Nimm Game):
有n堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,多者不限,最后取光者得胜.
任何奇异局势(a1, a2, … , an)都有a1(+)a2(+)…(+)an =0. ( (+)为 按位与)
例题：pku 2234
例题：hdu 1730
例题：pku 1740
例题：pku 1704
例题：pku 1082 (大量分析… 结论很简单。 也可以根据简单的推论模拟实现
posted @
2010-08-27 10:53 雪黛依梦 阅读(110) |
评论 (0) |
编辑 收藏
理解了博弈中的巴什博弈就很简单，没理解的话就。。。。
#include <iostream>
#include <string>
using namespace std;
int main ()
{
int t, n, m;
scanf ("%d", &t);
while ( t -- )
{
scanf ("%d %d", &n , &m);
if ( n % (m + 1) == 0 ) // p 状态
printf ("second\n");
else
printf ("first\n");
}
// system ("pause");
return 0;
}
posted @
2010-08-27 10:30 雪黛依梦 阅读(281) |
评论 (0) |
编辑 收藏
博弈论是二人在平等的对局中各自利用对方的策略变换自己的对抗策略，达到取胜的意义。
博弈问题的关键在于如何根据题目的要求找到 p n 点，步骤如下
步骤一 将所有终止状态设为P状态。
步骤二 将所有一步之内可以到达一个P状态的状态设为N状态。
步骤三 如果一个状态，不管怎么走都只能走到N状态，那么就将这个状态设为P状态。
步骤四 返回步骤二。 （ 所以只要找出了 p n p 就可以找到下面的状态 ）
如果能够走到P状态，就能获胜。因为安照上面的定义，对手不管如何选择，只可能走到N状态。接下来总存在一个P状态你可以走到。这样一直走到终止状态，你获胜。当然这里所说得都是指对于最后走步的人（最后走步的人有石子取就设为 n ）获胜的游戏。
我们严格的来定义P状态和N状态
l 所有的终止状态都是P状态；
l 对于任何的N状态，肯定存在一种方式可以一步转到一个P状态；
l 对于任何的P状态，不管怎么走步，都只能转到N状态。
而对于最后走步的人失败的游戏，只要将所有终止状态改成N状态，然后开始倒推就可以了。当然，必胜状态是N状态。也就是说，如果想胜利，就希望面对N状态，转移到P状态。
定好 P N 点之后找出对应的数字规律即可
二：
Nim-Sum：
Nim游戏的一个状态(x1, x2, x3) 是P状态，当且仅当x1+x2+x3=0。
如果有n堆石子，状态(x1, x2, …, xn)是P状态的充要条件是x1+x2+…+xn=0。
“Nim和”就是两个数二进制表示的不进位加法，也就是两个整数进行xor位运算。
定义：两个数(xm…x0)2和(ym…y0)2，是(zm…z0)2，其中zi=(xi+yi) mod 2，0<=i<=m。
例如，22和51的Nim和是37。注意：计算时没有进位
posted @
2010-08-27 09:16 雪黛依梦 阅读(175) |
评论 (0) |
编辑 收藏
开始做这题的时候总是将它和最小生成树算法混淆，最短路径初始的时候是存的从其点到其他各点的距离，没有的设为无穷，每次都是找出最短的路径值（同时标记该顶点，说明已经找到了最短的路径，不需要再修改），并且不断修改起点到其他各点的距离，如此循环，知知道所有顶点都访问；
//思路：本质是找从 A 到 B 的最短路径，如果最短路径存在则一定会用满足题意的按最少次数的按钮
//如果最短路径不存在肯定找不到，输出 -1
//这里将可以到达的点设为 1, 是因为如果可以到达就按了一下按钮，如果不可到达则仍然是MAX
//此题中如果有某一个点找不到到达它的最短路径，说明电梯到达这一层之后不可能再达到其他任何了，所以return返回主函数检查；这是和模板不同的地方
#include <iostream>
#include <string>
using namespace std;
#define MAXN 99999999
int button[201]; //存储每一层按下按钮之后可升降的层数
int map[201][201];
int dist[201];
int visit[201];
int n, a, b;
void dijkstra ()
{
for (int i = 1; i <= n; i ++)
{
dist[i] = map[a][i]; //初值是起点到每个点的距离！
}
dist[a] = 0;
int k, min;
for ( int i = 1; i <= n; i ++ )
{
min = MAXN;
for (int j = 1; j <= n; j ++)
{
if ( !visit[j] && dist[j] < min ) //找最短的距离
{
min = dist[j];
k = j;
}
}
if ( min == MAXN ) //没有最短路了 // 顺序
return ;
visit[k] = 1;
for (int j = 1; j <= n; j ++)
{
if ( !visit[j] && map[k][j] + dist[k] < dist[j] )
{
dist[j] = map[k][j] + dist[k];
}
}
}
}
int main ()
{
while ( scanf ("%d", &n) != EOF && n )
{
scanf ( "%d %d", &a, &b );
memset ( button, 0, sizeof (button) );
memset ( dist, 0, sizeof (dist) );
memset ( visit, 0, sizeof (visit) );
for ( int i = 1; i <= n; i ++ )
{
for ( int j = 1; j <= n; j ++ )
{
map[i][j] = MAXN;
}
}
for ( int i = 1; i <= n; i ++ )
{
scanf ("%d", &button[i]);
if ( i + button[i] <= n )
{
map[i][i + button[i]] = 1;
}
if ( i - button[i] >= 1 ) //最大的错误不是else if啊！！！！
{
map[i][i - button[i]] = 1;
}
}
dijkstra ();
if ( dist[b] < MAXN ) //有路径到达
printf ("%d\n", dist[b]);
else
printf ("%d\n", -1);
}
//system ("pause");
return 0;
}
posted @
2010-08-26 20:38 雪黛依梦 阅读(388) |
评论 (0) |
编辑 收藏
//用并查积 和 克鲁是卡尔算法实现查找最短边
//利用快排按边递增排列，每次从中选出最短边,同时将最短边的两个顶点并入到集合中
心得：利用并查积 和 kruskal算法结合找最短路径可以使查找的效率更高
本题的关键是正确地设定好两个数组，一个是用于存放顶点边值的node1，另一个是用于并查积处理的node2，并且将这两个数组联系好
加入集合中的边都是构成最小生成树的边，所以每家一次sum 都要加上这两个顶点之间的距离
#include <iostream>
#include <string>
using namespace std;
struct node1 //用于存放顶点和边值
{
int x;
int y;
int distance;
};
node1 edge[5010]; // n 个顶点的边无向图最多有 n * (n - 1) / 2 条边
struct node2 //并查积数组
{
int parent;
int height;
};
node2 village[100];
bool cmp ( const node1 &a, const node1 &b )
{
return a.distance < b.distance;
}
//并查积初始化
void set ( int n )
{
for ( int i = 1; i <= n; i++)
{
village[i].parent = i;
}
}
//找根节点
int findfather (int a)
{
while ( a != village[a].parent ) //理解while 树状结构：找到最终的跟节点
a = village[a].parent;
return a;
}
//合并到同一集合
void merge (int a, int b) //注意参数：要合并两个节点的根
{
if ( village[a].height == village[b].height )
{
village[b].parent = a;
village[a].height ++;
}
//小树合并到大树
else if ( village[a].height > village[b].height )
{
village[b].parent = a;
}
else
village[a].parent = b;
}
int main ()
{
int n, k;
int x, y, d;
int a, b;
while ( scanf ("%d", &n ) != EOF && n )
{
set ( n );
memset ( edge, 0, sizeof (edge) );
//输入处理
k = n * ( n - 1 ) / 2;
for ( int i = 0; i < k; i ++ )
{
scanf ( "%d %d %d", &x, &y, &d );
edge[i].x = x;
edge[i].y = y;
edge[i].distance = d;
}
//排序
sort ( edge, edge + k, cmp );
//从已排好的序列中选出最短边同时利用并查积构建图
int sum = 0;
for ( int i = 0; i < k; i++ )
{
a = findfather ( edge[i].x );
b = findfather ( edge[i].y );
if ( a != b )
{
merge ( a, b );
sum += edge[i].distance;
}
}
printf ( "%d\n", sum );
}
//system ("pause");
return 0;
}
posted @
2010-08-26 16:02 雪黛依梦 阅读(390) |
评论 (0) |
编辑 收藏