用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 雪黛依夢 閱讀(250) |
評論 (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 雪黛依夢 閱讀(290) |
評論 (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 雪黛依夢 閱讀(375) |
評論 (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 雪黛依夢 閱讀(365) |
評論 (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 雪黛依夢 閱讀(193) |
評論 (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 雪黛依夢 閱讀(129) |
評論 (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 雪黛依夢 閱讀(309) |
評論 (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 雪黛依夢 閱讀(197) |
評論 (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 雪黛依夢 閱讀(404) |
評論 (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 雪黛依夢 閱讀(410) |
評論 (0) |
編輯 收藏