摘要: 五月份做的吧 那個時候用了dp 死活過不了 后來聽人說dp是可行的 但我還是不會，囧。。。這題用了比較快的廣搜算法，用v[i][j][k]存儲余數(shù)從i->j,去掉數(shù)字為k的情況，由于狀態(tài)空間<1000，所以窮搜狀態(tài)空間是可行的。這題具體來說可以分成三種情況：1.字符串中既沒有5也沒有0，那么可以直接impossble掉2.如果字符串中有5但是沒有0，可以先去掉一個5，然后在窮搜，最后在...
閱讀全文
水陸草木之花，可愛者甚蕃。晉陶淵明獨(dú)愛菊；自李唐來，世人甚愛牡丹；予獨(dú)愛蓮之出淤泥而不染，濯清漣而不妖，中通外直，不蔓不枝，香遠(yuǎn)益清，亭亭凈植，可遠(yuǎn)觀而不可褻玩焉。
予謂菊，花之隱逸者也；牡丹，花之富貴者也；蓮，花之君子者也。噫！菊之愛，陶后鮮有聞。蓮之愛，同予者何人？牡丹之愛，宜乎眾矣！
《編程之美》讀書筆記：2.9 Fibonacci序列
計(jì)算Fibonacci序列最直接的方法就是利用遞推公式 F(n+2)=F(n+1)+F(n)。而用通項(xiàng)公式來求解是錯誤的，用浮點(diǎn)數(shù)表示無理數(shù)本來就有誤差，經(jīng)過n次方后，當(dāng)n相當(dāng)大時，誤差能足夠大到影響浮點(diǎn)數(shù)轉(zhuǎn)為整數(shù)時的精度，得到的結(jié)果根本不準(zhǔn)。
用矩陣來計(jì)算，雖然時間復(fù)雜度降到O(log n)，但要用到矩陣類，相當(dāng)麻煩。觀察：
F(n+2)=F(n)+F(n-1)＝2*F(n-1)+F(n-2)=3*F(n-2)+2*F(n-4)
用歸納法很容易證明 F(n) = F(k)*F(n+1-k) + F(k-1)*F(n-k)，利用該遞推公式和原遞推公式，要計(jì)算F(n)，只要計(jì)算F([n/2])和F([n/2]+1)，時間復(fù)雜度為 O(lg n)。如：要計(jì)算F(58)，由 58 -> 29,30 -> 14,15 -> 7,8 -> 3,4 -> 1,2 可知只要算5次。可以用一個棧保存要計(jì)算的數(shù)，實(shí)際上，將n的最高位1（假設(shè)在第k位）左邊的0去除掉后，第m次要計(jì)算的數(shù)是第k位到第k-m+1位這m個位組成的值t(m)，則第m-1次要計(jì)算的數(shù)為t(m-1)，且
t(m)=2*t(m-1)+(第k-m+1位是否為1)。
若第m-1次計(jì)算得到了f(k)和f(k+1)，則第m次計(jì)算：
|
第k-m+1位
|
已計(jì)算
|
待計(jì)算
|
|
1
|
f(k)
f(k+1)
|
f(2*k+1),f(2*k+2)
|
|
0
|
f(2*k),f(2*k+1)
|
具體公式見下面代碼。
下面是計(jì)算F(n)最后四位數(shù)（某道ACM題）的代碼。
/* Fibonacci數(shù)列第N個數(shù)的最后4位數(shù)
注意，當(dāng) N>93 時 第N個數(shù)的值超過64位無符號整數(shù)可表示的范圍。
F(n+2)=F(n)+F(n-1) F(0)=0 F(1)=1 F(2)=1 ==>
F(n)=F(k)*F(n+1-k) + F(k-1)*F(n-k) ==>
F(2*n)=F(n+1)*F(n)+F(n)*F(n-1)=(F(n+1)+F(n-1))*F(n)=(F(n+1)*2-F(n))*F(n)
F(2*n+1)=F(n+1)*F(n+1)+F(n)*F(n)
F(2*n+2)=F(n+2)*F(n+1)+F(n+1)*F(n)=(F(n+2)+F(n))*F(n+1)=(F(n+1)+F(n)*2)*F(n+1)
*/
unsigned fib_last4( unsigned num)
{
if ( num == 0 ) return 0;
const unsigned M=10000;
unsigned ret=1,next=1,ret_=ret;
unsigned flag=1, tt=num;
while ( tt >>= 1) flag <<= 1;
while ( flag >>= 1 ){
if ( num & flag ){
ret_ = ret * ret + next * next;
next = (ret + ret + next) * next;
} else {
//多加一個M，避免 2*next-ret是負(fù)數(shù)，造成結(jié)果不對
ret_ = (next + next + M - ret) * ret;
next = ret * ret + next * next;
}
ret = ret_ % M;
next = next % M;
}
return ret;
}
轉(zhuǎn)自：
http://www.shnenglu.com/flyinghearts/archive/2010/06/23/118593.html
看來不學(xué)居正哥搞個考成簿是不行了，最近事情實(shí)在太多，東忘西忘，還是要總結(jié)一下。
1.6月12號的GRE考試，數(shù)學(xué)爭取拿滿分吧，語文部分，你懂的。。。
2.6 月13號網(wǎng)易有道難題在線賽。
3.6月15號去南大.
4. 葉慶生的課程設(shè)計(jì)，這個真的有點(diǎn)變態(tài)。下周三答辯，考完GRE以后要全力做這個。
5.打印各門課的課件，重點(diǎn)是操作系統(tǒng)，大學(xué)化學(xué)（操作系統(tǒng)是重中之重，大學(xué)化學(xué)是很無奈。。。）。
6.然后就是網(wǎng)絡(luò)安全，操作系統(tǒng)，算法設(shè)計(jì)與分析幾門課，對了 別忘了大學(xué)化學(xué)，一定要開始看了。雖然課剩下的不是太多，但是稍微放松就完了，所以一定要提早看。
現(xiàn)在是15周周二 晚
The resulting database contained 142 institutions. Ranked by three separate measures Citations, Papers, and Citations Per Paper. Source dates: 1998-December 31, 2008 (sixth bimonthly period 2008).
| Citations |
| Rank |
Institution |
Citations |
Papers |
Citations
Per Paper |
| 1 |
MIT |
2429 |
114 |
21.31 |
| 2 |
Michigan State Univ |
1467 |
43 |
34.12 |
| 3 |
UNIV CALIF SAN DIEGO |
1404 |
50 |
28.08 |
| 4 |
UNIV ILLINOIS |
906 |
121 |
7.49 |
| 5 |
Carnegie Mellon Univ |
904 |
158 |
5.72 |
| 6 |
US ARMY |
896 |
41 |
21.85 |
| 7 |
DELFT UNIV TECHNOL |
722 |
15 |
48.13 |
| 8 |
Ohio State Univ |
702 |
37 |
18.97 |
| 9 |
UNIV AMSTERDAM |
697 |
32 |
21.78 |
| 10 |
UNIV BRITISH COLUMBIA |
662 |
29 |
22.83 |
| 11 |
NATL INST STAND & TECHNOL |
645 |
22 |
29.32 |
| 12 |
IBM Corp |
608 |
23 |
26.43 |
| 13 |
Max Planck Society |
584 |
22 |
26.55 |
| 14 |
AT&T |
574 |
11 |
52.18 |
| 15 |
Univ Connecticut |
561 |
51 |
11.00 |
| 16 |
HONG KONG POLYTECH UNIV |
553 |
129 |
4.29 |
| 17 |
GEORGE MASON UNIV |
508 |
32 |
15.88 |
| 18 |
CUNY |
476 |
17 |
28.00 |
| 19 |
Univ Calif Berkeley |
461 |
35 |
13.17 |
| 20 |
NANJING UNIV SCI & TECHNOL |
430 |
64 |
6.72 |
Papers
(  10 papers published between
1998-December 31, 2008 [sixth bimonthly period 2008]) |
| Rank |
Institution |
Citations |
Papers |
Citations
Per Paper |
| 1 |
CHINESE ACAD SCI |
345 |
231 |
1.49 |
| 2 |
Carnegie Mellon Univ |
904 |
158 |
5.72 |
| 3 |
TSING HUA UNIV |
55 |
140 |
0.39 |
| 4 |
HONG KONG POLYTECH UNIV |
553 |
129 |
4.29 |
| 5 |
HARBIN INST TECHNOL |
90 |
123 |
0.73 |
| 6 |
UNIV ILLINOIS |
906 |
121 |
7.49 |
| 7 |
MIT |
2429 |
114 |
21.31 |
| 8 |
UNIV MARYLAND |
381 |
93 |
4.10 |
| 9 |
NANYANG TECHNOL UNIV |
380 |
92 |
4.13 |
| 10 |
CHINESE UNIV HONG KONG |
166 |
78 |
2.13 |
| 11 |
Shanghai Jiao Tong Univ |
35 |
73 |
0.48 |
| 12 |
Univ Surrey |
163 |
73 |
2.23 |
| 13 |
NANJING UNIV SCI & TECHNOL |
430 |
64 |
6.72 |
| 14 |
UNIV TORONTO |
361 |
62 |
5.82 |
| 15 |
KOREA ADV INST SCI & TECHNOL |
106 |
61 |
1.74 |
| 16 |
Inha Univ |
18 |
53 |
0.34 |
| 17 |
YONSEI UNIV |
34 |
52 |
0.65 |
| 18 |
Hong Kong Baptist Univ |
217 |
51 |
4.25 |
| 19 |
INDIAN INST TECHNOL |
45 |
51 |
0.88 |
| 20 |
Univ Connecticut |
561 |
51 |
11.00 |
Citations Per Paper
( 43 papers published between
1998-December 31, 2008 [sixth bimonthly period 2008]) |
| Rank |
Institution |
Citations |
Papers |
Citations
Per Paper |
| 1 |
Michigan State Univ |
1467 |
43 |
34.12 |
| 2 |
UNIV CALIF SAN DIEGO |
1404 |
50 |
28.08 |
| 3 |
MIT |
2429 |
114 |
21.31 |
| 4 |
Univ Connecticut |
561 |
51 |
11.00 |
| 5 |
UNIV ILLINOIS |
906 |
121 |
7.49 |
| 6 |
NANJING UNIV SCI & TECHNOL |
430 |
64 |
6.72 |
| 7 |
Natl Univ Singapore |
328 |
50 |
6.56 |
| 8 |
UNIV TORONTO |
361 |
62 |
5.82 |
| 9 |
Carnegie Mellon Univ |
904 |
158 |
5.72 |
| 10 |
INRIA |
213 |
43 |
4.95 |
| 11 |
ARISTOTELIAN UNIV SALONIKA |
219 |
47 |
4.66 |
| 12 |
Univ So Calif |
190 |
43 |
4.42 |
| 13 |
HONG KONG POLYTECH UNIV |
553 |
129 |
4.29 |
| 14 |
Hong Kong Baptist Univ |
217 |
51 |
4.25 |
| 15 |
NANYANG TECHNOL UNIV |
380 |
92 |
4.13 |
| 16 |
UNIV MARYLAND |
381 |
93 |
4.10 |
| 17 |
Univ Surrey |
163 |
73 |
2.23 |
| 18 |
CHINESE UNIV HONG KONG |
166 |
78 |
2.13 |
| 19 |
Univ Calif Riverside |
88 |
46 |
1.91 |
| 20 |
UNIV YORK |
91 |
49 |
1.86 |
轉(zhuǎn)自:http://sciencewatch.com/ana/st/face/institution/
實(shí)際上就是枚舉所有區(qū)間，求出所有區(qū)間可以獲得的最大值和最小值，區(qū)間L的的結(jié)果可以由區(qū)間L-1的結(jié)果組合得到。
這題有一個小技巧很好用，就是求第i個結(jié)點(diǎn)順時針向后的第t個結(jié)點(diǎn)如果是node(i,t)的話，那么node (i,t+1)的標(biāo)號可以由
((i+t)%n )+1得到，實(shí)際上lebel[node(i,t)]=((i+t-1)%n )+1;所以這題結(jié)點(diǎn)從1開始存似乎更加便于計(jì)算。
//coded by abilitytao
//2010年6月1日17:25:38
#include <iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=100;
int n;
int fmax[maxn][maxn];
int fmin[maxn][maxn];
int v[maxn];
int op[maxn];
void init()//初始化
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
fmax[i][j]=-999999999;
fmin[i][j]=999999999;
}
for(int i=1;i<=n;i++)
fmax[i][0]=fmin[i][0]=v[i];
}
void input()
{
scanf("%d",&n);
cin.ignore();
int i;
for(i=1;i<=n;i++)
{
char tem[10];
scanf("%s",tem);
if(tem[0]=='t')
op[i]=0;//0代表+號
else
op[i]=1;//1代表乘號
scanf("%d",&v[i]);
}
}
void solve()//DP過程
{
int mm=-999999999;
int i,t,L;
for(L=1;L<=n-1;L++)
{
for(i=1;i<=n;i++)
{
for(t=0;t<=L-1;t++)
{
if(op[(i+t)%n+1]==0)
{
fmin[i][L]=min(fmin[i][L],fmin[i][t]+fmin[(i+t)%n+1][L-t-1]);
fmax[i][L]=max(fmax[i][L],fmax[i][t]+fmax[(i+t)%n+1][L-t-1]);
}
else
{
fmin[i][L]=min(fmin[i][L],fmin[i][t]*fmin[(i+t)%n+1][L-t-1]);
fmin[i][L]=min(fmin[i][L],fmin[i][t]*fmax[(i+t)%n+1][L-t-1]);
fmin[i][L]=min(fmin[i][L],fmax[i][t]*fmin[(i+t)%n+1][L-t-1]);
fmin[i][L]=min(fmin[i][L],fmax[i][t]*fmax[(i+t)%n+1][L-t-1]);
fmax[i][L]=max(fmax[i][L],fmin[i][t]*fmin[(i+t)%n+1][L-t-1]);
fmax[i][L]=max(fmax[i][L],fmin[i][t]*fmax[(i+t)%n+1][L-t-1]);
fmax[i][L]=max(fmax[i][L],fmax[i][t]*fmin[(i+t)%n+1][L-t-1]);
fmax[i][L]=max(fmax[i][L],fmax[i][t]*fmax[(i+t)%n+1][L-t-1]);
}
}
}
}
for(i=1;i<=n;i++)
if(fmax[i][n-1]>mm)
mm=fmax[i][n-1];
printf("%d\n",mm);
for(i=1;i<=n;i++)
if(fmax[i][n-1]==mm)
printf("%d ",i);
printf("\n");
}
int main()
{
input();
init();
solve();
return 0;
}
【概述】
最近的幾次比賽，博弈的題目一直不少，而且博弈問題是一塊比較復(fù)雜、龐大的內(nèi)容，因此在這里小結(jié)一下，希望能夠幫自己理清一些思路，爭取也多來幾個系列，呵呵。
競賽中出現(xiàn)的組合游戲問題一般都滿足以下特征：
1. 二人博弈游戲，每個人都采用對自己最有利的策略，并且是兩個人輪流做出決策
2. 在游戲中的任意時刻，每個玩家可選擇的狀態(tài)是固定的，沒有隨機(jī)成分
3. 游戲在有限步數(shù)內(nèi)結(jié)束，沒有平局出現(xiàn)
大部分的題目都滿足上述條件，因此這里只討論在上述條件范疇內(nèi)的博弈問題。這類博弈問題，通常還有若干分類。一種是規(guī)定移動最后一步的游戲者獲勝，這種規(guī)則叫做
Normal Play Rule；另一種是規(guī)定移動最后一步的游戲者輸，這種規(guī)則叫做
Misere Play Rule，也稱為Anti-SG游戲。此外，對于游戲的雙方，如果二者博弈的規(guī)則相同，那么稱為這類游戲是
對等(impartial games)的；否則稱為
不平等游戲(partizan games )。當(dāng)初WHU的那場比賽就是由于對于這個概念不是很清晰，導(dǎo)致看完題目之后就用SG定理來做，浪費(fèi)了很多機(jī)時。實(shí)際上，解決不平等博弈問題的方法和普通的博弈問題（SG游戲）是有區(qū)別的，一般會采用動態(tài)規(guī)劃或者surreal number。
【博弈基礎(chǔ)知識】
在SG游戲中，最為人熟知的是必勝必?cái)B(tài)，也叫NP態(tài)理論。注意的是，P態(tài)對應(yīng)的是先手必?cái)B(tài)，N態(tài)對應(yīng)的是先手必勝態(tài)。必勝必?cái)B(tài)理論是：
1. All terminal positions are P-positions
2. From every N-position, there is at least one move to a P-position
3. From every P-position, every move is to an N-position
英文的表述非常簡潔清晰，而且這個理論也很好理解，如果在當(dāng)前狀態(tài)的下一步可以走到必?cái)B(tài)，那么當(dāng)前玩家就可以走到那個狀態(tài)，把必?cái)B(tài)推給另一方；如果所有可達(dá)狀態(tài)都是必勝態(tài)，那么當(dāng)前玩家無論如何走，都會把必勝態(tài)讓給對方。根據(jù)必勝必?cái)B(tài)理論，我們可以遞歸的求出每個狀態(tài)是N態(tài)還是P態(tài)。必勝必?cái)B(tài)理論其實(shí)已經(jīng)把博弈問題轉(zhuǎn)化成了一個有向圖，借助圖這個模型來分析問題，使得問題變得形象了許多。需要注意的是，這種SG游戲?qū)?yīng)的有向圖是無環(huán)的，因?yàn)槿绻协h(huán)，那么游戲雙方就可能在環(huán)上不停的轉(zhuǎn)換狀態(tài)，游戲不能在有限步終止，這樣就不滿足組合游戲的特征3了。
然而在很多時候僅僅知道某個狀態(tài)是必勝還是必?cái)∈遣粔虻模驗(yàn)槿绻嬖诙鄠€組合游戲（比如經(jīng)典的Nim），對應(yīng)的狀態(tài)集合非常大，無法直接利用必勝必?cái)B(tài)理論求解，因此需要用到博弈論中一個很重要的工具：SG函數(shù)。
某個狀態(tài)的SG函數(shù)值定義為當(dāng)前狀態(tài)所有不可達(dá)的狀態(tài)編號中最小的編號，其中終止態(tài)的SG函數(shù)值是0。有了這個工具，就引入一個非常強(qiáng)大的定理——SG分解定理：
多個組合游戲的SG函數(shù)值是每個組合游戲的函數(shù)值的和。（這里的和定義為異或操作）
SG分解定理的證明不是很難，其實(shí)和Nim的證明很像。根據(jù)這個定理，我們就知道為什么Nim的解法是異或所有的石子個數(shù)了，因?yàn)槊慷咽拥腟G值就是石子的個數(shù)。SG分解定理告訴我們?nèi)魏蜸G游戲都可以轉(zhuǎn)化成Nim游戲來做。
Nim中的一個變形就是拿走最后一塊石子的人算輸。通過修改SG的計(jì)算規(guī)則，可以得出相同的結(jié)論（因?yàn)楫?dāng)石子個數(shù)是1的時候SG值為0，因此要單獨(dú)處理）；當(dāng)然也可以利用一個叫做SJ定理的方法來做，依然是要處理當(dāng)所有堆的SG值不大于1的情況。
【博弈基本模型】
除了Nim模型，很多模型都看似復(fù)雜，最后都劃歸到了Nim模型上，然后利用SG分解來做的。在證明兩種模型等價的時候，可以通過計(jì)算SG值判斷是否相同，或者通過判斷必勝策略的走法將其轉(zhuǎn)化為Nim。許多模型非常的神奇，其獲勝策略又千差萬別，因此無法一一列舉，但是掌握一些經(jīng)典模型是必須的，這樣通過模型的轉(zhuǎn)化可以簡化問題的難度。
經(jīng)典模型1：Nim變種。包括：
(1) 樓梯Nim。把奇數(shù)臺階的石子作為Nim，二者等價，因?yàn)楸貏俚牟呗允窍嗤摹?br> (2) 每次可以取k堆，這個是經(jīng)典的Moore Nim。它是泛化的Nim游戲。
(3) 兩堆石子，每次可以取一堆或兩堆，從兩堆取得時候個數(shù)必須相同，誰先取完獲勝。這個是著名的威佐夫博弈，跟黃金分割數(shù)有關(guān)，具體證明不是很清楚，但是用SG值打表可以找出規(guī)律。代碼如下：
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
const double k = (sqrt(5.0) + 1) / 2.0;
int a, b, t;
while (scanf("%d %d", &a, &b) == 2)
{
if (a > b)
swap(a, b);
t = b - a;
if (a == (int)(t * k))
puts("0");
else
puts("1");
}
return 0;
}
(4) Subtraction Games。一種通用的Nim游戲，每次從可用狀態(tài)集合中選擇下一步的狀態(tài)，有很多變形，核心思想還是計(jì)算SG函數(shù)值。
(5) Take-and-Break Game。每次把局面分成多個Nim子游戲，利用SG分解定理求出對應(yīng)的SG值。
經(jīng)典模型2：翻硬幣游戲(Coin Turning Game) (1) 一維的翻硬幣游戲，每次可以翻1個或兩個。通過單獨(dú)考慮每個可以翻的硬幣發(fā)現(xiàn)，Coin Turning Game的SG值和Nim等價，因此兩個模型等價。需要注意的是，許多翻硬幣游戲根據(jù)題目的要求，一般編號從0開始。
(2) 一維的翻硬幣游戲，每次可以翻1個或兩個，限定了翻第二枚硬幣的范圍，那么就和Subtraction Game等價了。
(3) 一維的翻硬幣游戲，每次可以翻1個、2個或3個，這個游戲叫做Mock Turtles，有一個神奇的規(guī)律，是Odious Number序列。
(4) 高維的翻硬幣游戲，需要用到Nim積和Tartan定理。
翻硬幣模型的變化更多，很多模型都有一些奇妙的規(guī)律，需要打表才能發(fā)現(xiàn)。
經(jīng)典模型3：刪邊游戲(Green Hackenbush) (1) 樹的刪邊游戲：Colon原理證明這種模型和Nim依然是等價的，多個叉的SG值異或就是對應(yīng)根節(jié)點(diǎn)的SG值。
(2) 無向圖刪邊游戲：利用Fursion定理收縮圈，然后就轉(zhuǎn)換成樹的刪邊游戲了，不過這個定理還不會證。
轉(zhuǎn)自：
http://www.shnenglu.com/sdfond/archive/2010/02/06/107364.aspxPS:最近做了好多博弈問題，但是總覺得還處在做一題，只會一題的狀態(tài)，我想是時候系統(tǒng)的學(xué)習(xí)一下了。