摘要: 和整除45差不多，枚举后两位。复杂度应该是25*1000 ，但很奇怪跑了390MS...可能中间计算常数时间比较大。再说几句，这题输出相当恶心啊，我挑了1个小时才大致理出输出的逻辑顺序，也许还不一定完全正确呢。这题还有优化的可能。请各路神牛指点
#include<iostream>#include<algorithm>#include<cmath>#inclu...
阅读全文
摘要: 五月份做的吧 那个时候用了dp 死活过不了 后来听人说dp是可行的 但我还是不会，囧。。。这题用了比较快的广搜算法，用v[i][j][k]存储余数从i->j,去掉数字为k的情况，由于状态空间<1000，所以穷搜状态空间是可行的。这题具体来说可以分成三种情况：1.字符串中既没有5也没有0，那么可以直接impossble掉2.如果字符串中有5但是没有0，可以先去掉一个5，然后在穷搜，最后在...
阅读全文
水陆草木之花，可爱者甚蕃。晋陶渊明独爱菊；自李唐来，世人甚爱牡丹；予独爱莲之出淤泥而不染，濯清涟而不妖，中通外直，不蔓不枝，香远益清，亭亭净植，可远观而不可亵玩焉。
予谓菊，花之隐逸者也；牡丹，花之富贵者也；莲，花之君子者也。噫！菊之爱，陶后鲜有闻。莲之爱，同予者何人？牡丹之爱，宜乎众矣！
《编程之美》读书笔记：2.9 Fibonacci序列
计算Fibonacci序列最直接的方法就是利用递推公式 F(n+2)=F(n+1)+F(n)。而用通项公式来求解是错误的，用浮点数表示无理数本来就有误差，经过n次方后，当n相当大时，误差能足够大到影响浮点数转为整数时的精度，得到的结果根本不准。
用矩阵来计算，虽然时间复杂度降到O(log n)，但要用到矩阵类，相当麻烦。观察：
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)，利用该递推公式和原递推公式，要计算F(n)，只要计算F([n/2])和F([n/2]+1)，时间复杂度为 O(lg n)。如：要计算F(58)，由 58 -> 29,30 -> 14,15 -> 7,8 -> 3,4 -> 1,2 可知只要算5次。可以用一个栈保存要计算的数，实际上，将n的最高位1（假设在第k位）左边的0去除掉后，第m次要计算的数是第k位到第k-m+1位这m个位组成的值t(m)，则第m-1次要计算的数为t(m-1)，且
t(m)=2*t(m-1)+(第k-m+1位是否为1)。
若第m-1次计算得到了f(k)和f(k+1)，则第m次计算：
|
第k-m+1位
|
已计算
|
待计算
|
|
1
|
f(k)
f(k+1)
|
f(2*k+1),f(2*k+2)
|
|
0
|
f(2*k),f(2*k+1)
|
具体公式见下面代码。
下面是计算F(n)最后四位数（某道ACM题）的代码。
/* Fibonacci数列第N个数的最后4位数
注意，当 N>93 时 第N个数的值超过64位无符号整数可表示的范围。
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是负数，造成结果不对
ret_ = (next + next + M - ret) * ret;
next = ret * ret + next * next;
}
ret = ret_ % M;
next = next % M;
}
return ret;
}
转自：
http://www.cppblog.com/flyinghearts/archive/2010/06/23/118593.html
看来不学居正哥搞个考成簿是不行了，最近事情实在太多，东忘西忘，还是要总结一下。
1.6月12号的GRE考试，数学争取拿满分吧，语文部分，你懂的。。。
2.6 月13号网易有道难题在线赛。
3.6月15号去南大.
4. 叶庆生的课程设计，这个真的有点变态。下周三答辩，考完GRE以后要全力做这个。
5.打印各门课的课件，重点是操作系统，大学化学（操作系统是重中之重，大学化学是很无奈。。。）。
6.然后就是网络安全，操作系统，算法设计与分析几门课，对了 别忘了大学化学，一定要开始看了。虽然课剩下的不是太多，但是稍微放松就完了，所以一定要提早看。
现在是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 |
转自:http://sciencewatch.com/ana/st/face/institution/
实际上就是枚举所有区间，求出所有区间可以获得的最大值和最小值，区间L的的结果可以由区间L-1的结果组合得到。
这题有一个小技巧很好用，就是求第i个结点顺时针向后的第t个结点如果是node(i,t)的话，那么node (i,t+1)的标号可以由
((i+t)%n )+1得到，实际上lebel[node(i,t)]=((i+t-1)%n )+1;所以这题结点从1开始存似乎更加便于计算。
//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;
}
【概述】
最近的几次比赛，博弈的题目一直不少，而且博弈问题是一块比较复杂、庞大的内容，因此在这里小结一下，希望能够帮自己理清一些思路，争取也多来几个系列，呵呵。
竞赛中出现的组合游戏问题一般都满足以下特征：
1. 二人博弈游戏，每个人都采用对自己最有利的策略，并且是两个人轮流做出决策
2. 在游戏中的任意时刻，每个玩家可选择的状态是固定的，没有随机成分
3. 游戏在有限步数内结束，没有平局出现
大部分的题目都满足上述条件，因此这里只讨论在上述条件范畴内的博弈问题。这类博弈问题，通常还有若干分类。一种是规定移动最后一步的游戏者获胜，这种规则叫做
Normal Play Rule；另一种是规定移动最后一步的游戏者输，这种规则叫做
Misere Play Rule，也称为Anti-SG游戏。此外，对于游戏的双方，如果二者博弈的规则相同，那么称为这类游戏是
对等(impartial games)的；否则称为
不平等游戏(partizan games )。当初WHU的那场比赛就是由于对于这个概念不是很清晰，导致看完题目之后就用SG定理来做，浪费了很多机时。实际上，解决不平等博弈问题的方法和普通的博弈问题（SG游戏）是有区别的，一般会采用动态规划或者surreal number。
【博弈基础知识】
在SG游戏中，最为人熟知的是必胜必败态，也叫NP态理论。注意的是，P态对应的是先手必败态，N态对应的是先手必胜态。必胜必败态理论是：
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
英文的表述非常简洁清晰，而且这个理论也很好理解，如果在当前状态的下一步可以走到必败态，那么当前玩家就可以走到那个状态，把必败态推给另一方；如果所有可达状态都是必胜态，那么当前玩家无论如何走，都会把必胜态让给对方。根据必胜必败态理论，我们可以递归的求出每个状态是N态还是P态。必胜必败态理论其实已经把博弈问题转化成了一个有向图，借助图这个模型来分析问题，使得问题变得形象了许多。需要注意的是，这种SG游戏对应的有向图是无环的，因为如果有环，那么游戏双方就可能在环上不停的转换状态，游戏不能在有限步终止，这样就不满足组合游戏的特征3了。
然而在很多时候仅仅知道某个状态是必胜还是必败是不够的，因为如果存在多个组合游戏（比如经典的Nim），对应的状态集合非常大，无法直接利用必胜必败态理论求解，因此需要用到博弈论中一个很重要的工具：SG函数。
某个状态的SG函数值定义为当前状态所有不可达的状态编号中最小的编号，其中终止态的SG函数值是0。有了这个工具，就引入一个非常强大的定理——SG分解定理：
多个组合游戏的SG函数值是每个组合游戏的函数值的和。（这里的和定义为异或操作）
SG分解定理的证明不是很难，其实和Nim的证明很像。根据这个定理，我们就知道为什么Nim的解法是异或所有的石子个数了，因为每堆石子的SG值就是石子的个数。SG分解定理告诉我们任何SG游戏都可以转化成Nim游戏来做。
Nim中的一个变形就是拿走最后一块石子的人算输。通过修改SG的计算规则，可以得出相同的结论（因为当石子个数是1的时候SG值为0，因此要单独处理）；当然也可以利用一个叫做SJ定理的方法来做，依然是要处理当所有堆的SG值不大于1的情况。
【博弈基本模型】
除了Nim模型，很多模型都看似复杂，最后都划归到了Nim模型上，然后利用SG分解来做的。在证明两种模型等价的时候，可以通过计算SG值判断是否相同，或者通过判断必胜策略的走法将其转化为Nim。许多模型非常的神奇，其获胜策略又千差万别，因此无法一一列举，但是掌握一些经典模型是必须的，这样通过模型的转化可以简化问题的难度。
经典模型1：Nim变种。包括：
(1) 楼梯Nim。把奇数台阶的石子作为Nim，二者等价，因为必胜的策略是相同的。
(2) 每次可以取k堆，这个是经典的Moore Nim。它是泛化的Nim游戏。
(3) 两堆石子，每次可以取一堆或两堆，从两堆取得时候个数必须相同，谁先取完获胜。这个是著名的威佐夫博弈，跟黄金分割数有关，具体证明不是很清楚，但是用SG值打表可以找出规律。代码如下：
#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游戏，每次从可用状态集合中选择下一步的状态，有很多变形，核心思想还是计算SG函数值。
(5) Take-and-Break Game。每次把局面分成多个Nim子游戏，利用SG分解定理求出对应的SG值。
经典模型2：翻硬币游戏(Coin Turning Game) (1) 一维的翻硬币游戏，每次可以翻1个或两个。通过单独考虑每个可以翻的硬币发现，Coin Turning Game的SG值和Nim等价，因此两个模型等价。需要注意的是，许多翻硬币游戏根据题目的要求，一般编号从0开始。
(2) 一维的翻硬币游戏，每次可以翻1个或两个，限定了翻第二枚硬币的范围，那么就和Subtraction Game等价了。
(3) 一维的翻硬币游戏，每次可以翻1个、2个或3个，这个游戏叫做Mock Turtles，有一个神奇的规律，是Odious Number序列。
(4) 高维的翻硬币游戏，需要用到Nim积和Tartan定理。
翻硬币模型的变化更多，很多模型都有一些奇妙的规律，需要打表才能发现。
经典模型3：删边游戏(Green Hackenbush) (1) 树的删边游戏：Colon原理证明这种模型和Nim依然是等价的，多个叉的SG值异或就是对应根节点的SG值。
(2) 无向图删边游戏：利用Fursion定理收缩圈，然后就转换成树的删边游戏了，不过这个定理还不会证。
转自：
http://www.cppblog.com/sdfond/archive/2010/02/06/107364.aspxPS:最近做了好多博弈问题，但是总觉得还处在做一题，只会一题的状态，我想是时候系统的学习一下了。