帐前卒专栏

有许多其实开始就知道即使尽力也很难实现。所以在结果出来之时，我还是询问下是否尽力了。尽力而为或者与虽败尤荣是同义词，只不过一个是在之前说，另外一个是在之后说
。说尽力是真话，反正也可以作为幌子。真与假只有自己评定。这是一份诚信的答卷，可是仍然可以写不诚信的答案。机会给了又给却还是不一定有机会。人何必执着，没有必要
为一个信念而活，就如同不要在一颗树上吊死一样。于是我说，那就在两棵树上吊死好了…都是死掉还分什么多少？墓葬的人可曾想到？…但是人的确是执着的，结果就
沦为固执。本来就是度的问题，结果因为不可量化而导致不同的结局。当然要看结局是什么。所有人都是结局论者，因为历史中没有假设。自己也是极端主义者，因为假设了所有
的人。运气是实力的一部分，我很赞同。因为在对的地点遇到对的人做对的事情本来就是攒了许多人品的运气。师兄的杯子留给了我，里面是黑黑的茶垢还有数不尽的细菌和病毒
，我准备用它来养花。但是首先要将它戳个洞。事情总要有先决条件，没有的话就是想到也做不成。因为我这里没有锥子。真实世界和计算机世界有太多不同，这就是许多技术牛
人至今仍然默默无闻的原因，这也是许多出了名的往往不是技术牛人的原因。混是很好的词，它反映了当今社会的主流趋势。所以即使你不想同流合污，也必须混成非主流。呓语
有终但无始。散文形散而意不散，我的形散意也散。真想将此文当资格评审卷考一下语文老师们。他们是无论如何也揣摩不出我的深层含义，当然你们也一样。这让我想到说的所
有话都是歧义句，我怎么可能有全部理解正确的时候？知道自己的信念就坚持走下去，总有人会跟随…换句话说也对，坚持走下去总会产生自己的信念，并为别人所信仰…
.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include<iostream>

using namespace std;

int Partition(int * a, int start, int end){
    swap(a[start],a[start+rand()%(end-start+1)]);
    int p = a[start];
    while(start<end){
        while(start<end && a[end] >= p) end--;
        swap(a[start],a[end]);
        while(start<end && a[start]<= p) start++;
        swap(a[start],a[end];)
    }
    return start;
}

void QuickSort(int * a, int start, int end){

     if(end-start>=1){
         int mid = Partition(a,start, end);
         QuickSort(a,start,mid-1);
         QuickSort(a,mid+1,end);
     }
}

But If you want do some optimization in QuickSort, first when the number of elements is small than 10, do insert sort not quick sort. Second, To find the near-like middle element of array, and not use the random one. Third, when the array is already sorted , do not use quick sort. and Reduce the function call. You will the following codes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

#include<iostream>

using namespace std;

void QuickSort(int *a, int start, int end){

    if(end - start <= 0 ) // or you can throw some exceptions!
       return ;

// if the number of element is less than 8, do insert sort;

    if(end - start<7){

      for(int i = start; i <= end; i++){

         for(int j = i; j > start && a[j] < a[j-1]; j--)

             swap(a[j],a[j-1]);

      }

      return;
    }

// check if the array is sorted.

    bool isSorted = true;
    for(int i = start; i < end; i++){
       if(a[i]>a[i+1])
         isSorted = false;
    }
    if(isSorted)
      return;

// get the near-like middle element, use 3 point middle method.

    int dm = start+(end-start)/2;

    int dl, dh;

    if(end-start<40){

       int d = (end-start+1)/8;

       dl = mid(a, start,start+d,start+2*d);

       dm = mid(a,dm-d,dm,dm+d);

       dh = mid(a,end-2*d,end-d, end);

       dm = mid(a,dl,dm,dh);

    }

// do partition

    swap(a[start],a[dm]);

    int low=start, high = end, p = a[start];
    while(low<high){
        while(low < high && a[high]>= p) high--;
        swap(a[low],a[high]);
        while(low<high && a[low]<= p) low ++;
        swap(a[low],a[high]);
    }
    QuickSort(a,start, low-1);
    QuickSort(a,low+1,end);
}

写了一个upper_bound的实现。其中递归使用二分法求解最上界，虽然写的完全不像STL的风格，但是练手还是可以的。

#include #include #include #include
using namespace std; int UpperBound(int* a, int start, int end , const int&
value){ int mid = 0; int index = 0; int up_index = 0; if(a[end]<value) //
特判比最后一个数大时，end+1 return end+1; //这里是经典的二分 while(start<= end){ mid = start +
(end - start)/2; if(a[mid] == value){ index = mid + 1; // 去递归的找一下上界 up_index =
UpperBound(a,mid+1,end,value); // 如果找到的上界比现在的还小，那么就用现在的 return up_index >
index? up_index : index; } else if(a[mid]<value){ start = mid+1; } else{ end =
mid-1; // 记录上界 index = mid; } } return index; }

如果原数组中没有存在那个元素，就根本没有调用那个递归程序，递归只有在出现多个此元素时才会调用。另外中间递归调用段地方还可以改写为：

if(a[mid] == value){ index = mid + 1; /* up_index =
UpperBound(a,mid+1,end,value); return up_index > index? up_index : index; */
// 因为只有在递归调用中start>end时，才会返回一个index = 0 return (mid+1>end) ? index :
UpperBound(a,mid+1,end,value); }

这样写完后写一下测试代码,顺便wrap一层upper_bound：

int upper_bound(int * a,int n, const int& value){ // 使用宏可以在编译时去除 #ifdef TEST
// pre-condition assert(NULL != a && n>0); // check the array a is sorted by
elements for(int i = 1; i < n; i++){ assert(a[i-1]<=a[i]); } int * tmp_a = new
int[n]; memcpy(tmp_a,a,sizeof(int)*n); #endif int index =
UpperBound(a,0,n-1,value); #ifdef TEST // post-condition //check whether the
array is changed or not for(int i = 0; i < n; i++) assert(a[i] == tmp_a[i]);
if(index == 0){ // min assert(a[index]>value); } else if(index == n){ // max
assert(a[index-1]<=value); } else{ assert(a[index]>value &&
a[index-1]<=value); } delete [] tmp_a; #endif return index; }

如果希望别人不调用UpperBound而只调用upper_bound,可以使用static 关键字， 将UpperBound限制在只在本文件中使用。别人调用
就只能调用upper_bound()函数。不过STL的教学源码比我这精简的多，根本无须使用递归。真正的STL源码变量名称会使用下划线__作为起始。

template <class ForwardIterator, class T> ForwardIterator upper_bound (
ForwardIterator first, ForwardIterator last, const T& value ) {
ForwardIterator it; iterator_traits::distance_type count,
step; count = distance(first,last); while (count>0) { it = first;
step=count/2; advance (it,step); if (!(value<*it)) // or: if
(!comp(value,*it)), for the comp version { first=++it; count-=step+1; } else
count=step; } return first; }

这里的advance()函数定义类似:

template<class Iterator, class Distance> void advance(Iterator& i, Distance
n); 类似于 i = x.begin()+n; i is an iterator of x

最后把主函数贴上做结：

int main(int argc, char* argv[]) { // 这里你可以使用random的方法进行测试。 int x[] =
{1,2,3,4,5,5,5,5,9}; vector v(x,x+9); sort(v.begin(),v.end()); cout <<
(int)(upper_bound(v.begin(),v.end(),9)-v.begin()); cout << upper_bound(x,9,9);
return 0; }

package test; import java.util.*; // Key class class A{ public int a; public
int b; A(int a, int b){ this.a = a; this.b = b; } public boolean equals(Object
o){ A x = (A)o; if(x.a == this.a && x.b == this.b) return true; return false;
} public int hashCode(){ return a+b; } } public class HashTableTest { /** *
@param args */ public static void main(String[] args) { // TODO Auto-generated
method stub HashMap<A,Integer> hm = new HashMap<A,Integer>(); A a1 = new
A(2,3); A a2 = new A(4,5); A a4 = new A(2,3); A a3 = new A(3,2); hm.put(a1,
new Integer(1)); hm.put(a2, new Integer(3));
System.out.print(hm.containsKey(a4)); } }

对于Key这个类，这里需要重载boolean  equals(Object o) 和int hashCode()
两个函数。这两个函数必须都要重载，否则会导致key找到不到。这里要说为什么，估计是HashMap中使用key相等的策略是
if(key1.equals(key2) && key1.hashCode() == key2.hashCode()),
因为hashcode可能会有多个不同的实例对应于一个hashCode, 所以这个东东会重叠。对于判断两个对象是否相等，java默认使用的是引用相等，即a
== b。但是对于String等其他内置的类来说，他们有自己的重载equals()方法。另外java
doc中也提到，当重载equals()方法时，最好把hashCode()方法也重载掉。这样看来if(key1.equals(key2) &&
key1.hashCode() == key2.hashCode())这句应该变为：

Key k = this.Get(key2.hashCode()); if (k.equals(key2)) return …

this article is about how to print one row only, and do not need to write infos to another row. I don’t know how to describe it in Chinese or English. And I also don’t know this article how to be searched.

This effect is like use wget to downloading files. You will see the process bar moving. How to display this effect? Use the following code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include<cstdio>
#include<unistd.h>
using namespace std;

int main(){
    printf("====>\r");
    fflush(stdout);       #flush buffer
    sleep(2);             # wait
    printf("======>\r");
    fflush(stdout);
    sleep(3);
    printf("========>\n");
    return 0;
}

In the above code, ‘\r’ is “Enter” character, and ‘\n’ is “newline” character. If input ‘\n’ into printf(), it will go to a new line. If input ‘\r’ into printf(), the output cursor will go to the beginning. If you do not use fflush(stdout); you will never your output without ‘\n’.

• if number >= 0 , then number >> 31 == 0

• if number < 0   , then number >> 31 == 0xFFFFFFFF

• number ^ 0xFFFFFFFF = ~number
• number ^ 0x00000000 = number

If you know above, then the goal of |x| = (x^(x>>31))+(~(x>>31)+1).

(x^(x>>31)) means:

• x >= 0, x^(x>>31) = x^0x00000000 = x
• x < 0, x^(x>>31) = x^0xFFFFFFFF = ~x

• x >= 0, ~(x>>31)+1 = 0xFFFFFFFF+1 = 0
• x < 0, ~(x>>31)+1 = 0x00000000+1 = 1

The malloc function prototype is : void* malloc(size_t size); This function will allocates a block of size bytes of memory, returning a pointer to the beginning of the block. Attention: this function is only for allocating memory! So the initial value of these memory will be Non-Zero. Maybe sometimes, it will be zero. Code for example:

1
2
3
4
5
6
7
8
9
10
11

#include<stdio.h>
#include<stdlib.h>
int main(){

	int * a = NULL;
	a = malloc(sizeof(int)*4);
	// like int a[4], but those memory is in heap
	for(int i = 0; i< 4; i++)
		printf("%d ",a[i]);
	return 0;
}

The realloc function prototype is : void* realloc(void* ptr, size_t size); This function will reallocates a block of size bytes of memory, returning a pointer to the beginning of the block. If size is zero and ptr is not NULL, it will be used as free(). If prt is NULL and size is not zero, it will be used as malloc(). If ptr is NULL and size is zero, return value is some kind of memory which contains zero elements! Wooo~~~~. Look at the following codes:

1
2
3
4
5
6
7
8

char * p = NULL;
printf("%x",(int)p); // will output 0

p = (char*)realloc(p,0);
printf("%x",(int)p); // will output non-zero

p = (char*)realloc(p,0);
printf("%x",(int)p);

why?! Because if this function is called successfully, it will return non-zero memory address. And you will see the third output subtract the second output will be 16 bytes. If ptr is not NULL , and size is non-zero, and current block can simply expand without moving,  the return value is the same as ptr. But there is not enough space for simply expand, it will execute free(ptr) and return malloc(size). This function will become very dangerous!

1
2
3

char * k = (char*)realloc(NULL,100);
char * kbigger = (char*)realloc(k,104);
char * kbiggest = (char*)realloc(k,106); <span style="color: #ff0000;">// crash!</span>

Safety called will be like the following:

1
2
3

char * k = (char*)realloc(NULL,100);
k = (char*)realloc(k,4); // k's address is not changed
k = (char*)realloc(k,104); // k's address is changed

If there is not enough free memory to be allocated, this function will return NULL.Attention: this function will not initialize those memory also.

calloc's prototype is void* calloc(int num, size_t size).

1
2
3
4
5
6

char* p = (char*)calloc(20,sizeof(char));

// it is equal to

char* p = (char*)malloc(20*sizeof(char));
memset(p,0,20*sizeof(char));

But calloc is efficient!

free function is to delete memory which has been allocated. But free function will not assign the point to zero.

1
2
3
4
5
6
7
8

char * p = (char*)calloc(100);

p[0] = 'a';
printf("%c",p[0]);   // output 'a'
printf("%x",(int)p);
free(p);
printf("%c",p[0]); // output nothing
printf("%x",(int)p); // the value is the same as the first.

And all of those functions will not recommend to be used in c++, because those functions will not initialize class structure or v_ptr. free() function will not destruct parent class when sub class is destructed. In c++, maybe should always use new and delete!

package queens; import java.io.FileNotFoundException; import
java.io.IOException; import org.sat4j.csp.SolverFactory; import
org.sat4j.reader.ParseFormatException; import org.sat4j.reader.XMLCSPReader;
import org.sat4j.specs.ContradictionException; import
org.sat4j.specs.IProblem; import org.sat4j.specs.ISolver; import
org.sat4j.specs.TimeoutException; import org.sat4j.tools.ModelIterator; public
class Solver { public static void main(String[] args) { ISolver solver =
SolverFactory.newDefault(); solver.setTimeout(360); ModelIterator mi = new
ModelIterator(solver); XMLCSPReader reader = new XMLCSPReader(solver); try {
if (reader != null) reader.parseInstance(“queens.xml”); IProblem problem = mi;
boolean unsat = true; int count = 1; while (problem.isSatisfiable()) { unsat =
false; System.out.print(“[” + count + "] “); for (int i = 0; i <
mi.model().length; i++) { System.out.print(mi.model()[i] + " “); }
System.out.println(””); // Call mi.model() to be sure you iterate to the next
solution mi.model(); count++; } if (unsat) {
System.out.println(“Unsitisfied”); } } catch (TimeoutException e) {
System.out.println(“Timeout”); } catch (FileNotFoundException e) {
System.out.println(“File not found”); } catch (IOException e) {
System.out.println(“IO Exception”); } catch (ParseFormatException e) {
System.out.println(“ParseFormatException”); } catch (ContradictionException e)
{ System.out.println(“Contradiction”); } catch (java.lang.NullPointerException
e) { System.out.print(“NullPointerException”); } } }

上面一段代码不知道如何，一直报NULL Point Exception. 最后发现并非是代码写错，而是因为jre不对。需要使用opensdk-1.6。

然后：

然后：

选中java-opensdk1.6 然后在外面选中刚才的JavaSE-1.6 :

有时候eclipse报出Class Not Found错误，可能是因为jar包应该放在external
jar的地方，但是你却放错了位置。添加external jar的地方。如果想添加external jars,需要在：

选中propertise,然后：

左边add external jars, 添加需要的jar即可。

如果发生了selection dose not contain a main type,
那么就需要重新创建一个Project,然后将你的文件再重新导入到新的Project中。或者粘贴过去。不知道为什么eclipse经常发生这个错误。

上面一个XMLCSPReader的各种jar文件需要在sat4j.org 上下载。该下模块的都下，但是注意版本号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

int main(){
    try{
        throw 20;
    }catch(int i){
        cout << "Exception Num is NO."<<i<<endl;
    }
    try{
        throw 'X';
    }catch(char c){
        cout << "this exception is a char:"<<c<<endl;
    }

    try{
        throw "abc";
    }catch(const char * e){
        cout << "this is string exception:"<<e<<endl;
    }

    try{
        int *d = new int(65);
        throw d;
    }catch(const int * e){
        cout << "this is int point exception:"<<*e<<endl;
    }
    /* ok, catch will handle everything, if you throw correct type.*/
}

and if you want create classes for exceptions. You should add #include<exception> and inherit exception class, and then override the function “what”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include<iostream>
#include<exception>
using namespace std;

/// this exception class is from #include<exception>
/// you should override the function what() to generate your exception string
class MyException: public exception{
    virtual const char* what() const throw(){
        return "myExceptions!!!!!!!";

    }

};

class SubException: public MyException{
    virtual const char* what()const throw(){
        return "sub exception !!!!!!";
    }

};

int main(){
    try{
        throw MyException();
    }catch(exception& e){
        cout << e.what()<<endl;

    }
    try{
        throw SubException();
    }catch(bad_alloc&){
        // this will not occur, just test this type.
        // if it is occured, your computer will be locked.
        cout << "nothing"<<endl;
    }catch(exception& e){
        cout << e.what()<<endl;

    }

}

There are some standard exceptions in exception.h. These exceptions are:

bad_alloc

A bad_alloc is thrown by new if an allocation failure occurs.

bad_cast

A bad_cast is thrown by dynamic_cast when it fails with a referenced type.

bad_exception

A bad_exception is thrown when an exception type doesn’t match any catch

bad_typeid

A bad_typeid is thrown by typeid

ios_base::failure

An ios_base::failure is thrown by functions in the iostream library.

in #include<stdexecpt> can use these exception:
class logic_error; // : public exception
class domain_error; // : public logic_error
class invalid_argument; // : public logic_error
class length_error; // : public logic_error
class out_of_range; // : public logic_error
class runtime_error; // : public exception
class range_error; // : public runtime_error
class overflow_error; // : public runtime_error
class underflow_error; // : public runtime_error

If you don’t know which kind of exception will occur. you should use catch(…)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

try{
        srand(time(NULL));
        int i = rand()%4;

        switch(i){
            case 0:
                throw; // terminate called without an active exception
                       // Aborted, ... will not catch it.
                break;
            case 1:
                throw 'x';
                break;
            case 2:
                throw 50;
                break;
            case 3:
                throw "my string";
                break;
            default:
                break;

        }

    }catch(...){
        cout << "I don't know which exception will occur!"<<endl;
    }

But when i == 0, the program will execute throw;, and it will exit and print:

terminate called without an active exception

Aborted

1
2
3
4
5
6
7
8
9

try{
        try{
            throw 2;
        }catch(int i){
            throw; // here I use it again!
        }
    }catch(...){
        cout << "re-throw it!!!!"<<endl;
    }

you can declare your functions using throw(). But it is just declare!  you can throw everything! But you declare it will throw bad_exception, and use set_unexpected(), it will process some unexpected exceptions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void foo() throw(int,bad_exception){

    throw "abc";
}
void myunexpected(){
    cout << "I get unexpected exceptions!"<<endl;
    throw;
}

// in main

    set_unexpected(myunexpected);
    try{
        foo();
    }catch(int){
        cout << "catch a integer"<<endl;
    }catch(bad_exception&){
        cout << "bad_exception"<<endl;
    }
    // you can use catch(...)

output is

I get unexpected exceptions! bad_exception

In some languages which have finally clauses. But in c++, it dose not have finally clauses.

转载自http://blog.csdn.net/logic_nut/archive/2009/10/22/4711489.aspx

推荐看看：http://www.math.ucla.edu/~tom/

学习理论在这里：http://www.math.ucla.edu/~tom/Game_Theory/Contents.html

博弈问题
若你想仔细学习博弈论，我强烈推荐加利福尼亚大学的Thomas S.
Ferguson教授精心撰写并免费提供的这份教材，它使我受益太多。（如果你的英文水平不足以阅读它，我只能说，恐怕你还没到需要看“博弈论”的时 候。）

Nim游戏是博弈论中最经典的模型（之一？），它又有着十分简单的规则和无比优美的结论，由这个游戏开始了解博弈论恐怕是最合适不过了。

Nim游戏是组合游戏(Combinatorial Games)的一种，准确来说，属于“Impartial Combinatorial
Games”（以下简称ICG）。满足以下条件的游戏是ICG（可能不太严谨）：1、有两名选手；2、两名选手交替对游戏进行移动(move)，每次一
步，选手可以在（一般而言）有限的合法移动集合中任选一种进行移动；3、对于游戏的任何一种可能的局面，合法的移动集合只取决于这个局面本身，不取决于轮
到哪名选手操作、以前的任何操作、骰子的点数或者其它什么因素；
4、如果轮到某名选手移动，且这个局面的合法的移动集合为空（也就是说此时无法进行移动），则这名选手负。根据这个定义，很多日常的游戏并非ICG。例如
象棋就不满足条件3，因为红方只能移动红子，黑方只能移动黑子，合法的移动集合取决于轮到哪名选手操作。

通常的Nim游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所
有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。

这游戏看上去有点复杂，先从简单情况开始研究吧。如果轮到你的时候，只剩下一堆石子，那么此时的必胜策略肯定是把这堆石子全部拿完一颗也不给对手剩，然后
对手就输了。如果剩下两堆不相等的石子，必胜策略是通过取多的一堆的石子将两堆石子变得相等，以后如果对手在某一堆里拿若干颗，你就可以在另一堆中拿同样
多的颗数，直至胜利。如果你面对的是两堆相等的石子，那么此时你是没有任何必胜策略的，反而对手可以遵循上面的策略保证必胜。如果是三堆石子……好像已经
很难分析了，看来我们必须要借助一些其它好用的（最好是程式化的）分析方法了，或者说，我们最好能够设计出一种在有必胜策略时就能找到必胜策略的算法。

定义P-position和N-position，其中P代表Previous，N代表Next。直观的说，上一次move的人有必胜策略的局面是P-
position，也就是“后手可保证必胜”或者“先手必败”，现在轮到move的人有必胜策略的局面是N-position，也就是“先手可保证必
胜”。更严谨的定义是：1.无法进行任何移动的局面（也就是terminal position）是P-position；2.可以移动到P-
position的局面是N-position；3.所有移动都导致N-position 的局面是P-position。

按照这个定义，如果局面不可能重现，或者说positions的集合可以进行拓扑排序，那么每个position或者是P-position或者是N-
position，而且可以通过定义计算出来。

以Nim游戏为例来进行一下计算。比如说我刚才说当只有两堆石子且两堆石子数量相等时后手有必胜策略，也就是这是一个P-position，下面我们依靠
定义证明一下(3,3)是一个P-position。首先(3,3)的子局面（也就是通过合法移动可以导致的局面）有(0,3)(1,3)(2,3)（显
然交换石子堆的位置不影响其性质，所以把(x,y)和(y,x)看成同一种局面），只需要计算出这三种局面的性质就可以了。
(0,3)的子局面有(0,0)、(0,1)、(0,2)，其中(0,0)显然是P-position，所以(0,3)是N-position（只要找到 一个是P-
position的子局面就能说明是N-position）。(1,3)的后继中(1,1)是P-position（因为(1,1)的唯一子局 面(0,1)是N-
position），所以(1,3)也是N-position。同样可以证明(2,3)是N-position。所以(3,3)的所有 子局面都是N-
position，它就是P-position。通过一点简单的数学归纳，可以严格的证明“有两堆石子时的局面是P-position当且
仅当这两堆石子的数目相等”。

根据上面这个过程，可以得到一个递归的算法——对于当前的局面，递归计算它的所有子局面的性质，如果存在某个子局面是P-position，那么向这个子
局面的移动就是必胜策略。当然，可能你已经敏锐地看出有大量的重叠子问题，所以可以用DP或者记忆化搜索的方法以提高效率。但问题是，利用这个算法，对于
某个Nim游戏的局面(a1,a2,…,an)来说，要想判断它的性质以及找出必胜策略，需要计算O(a1a2…*an)个局面的性质，不管
怎样记忆化都无法降低这个时间复杂度。所以我们需要更高效的判断Nim游戏的局面的性质的方法。

直接说结论好了。(Bouton’s Theorem)对于一个Nim游戏的局面(a1,a2,…,an)，它是P-
position当且仅当a1^a2…^{an=0，其中}表示异
或(xor)运算。怎么样，是不是很神奇？我看到它的时候也觉得很神奇，完全没有道理的和异或运算扯上了关系。但这个定理的证明却也不复杂，基本上就是按
照两种position的证明来的。

根据定义，证明一种判断position的性质的方法的正确性，只需证明三个命题： 1、这个判断将所有terminal position判为P-
position；2、根据这个判断被判为N-position的局面一定可以移动到某个P-position；3、根据这个判 断被判为P-
position的局面无法移动到某个P-position。

第一个命题显然，terminal position只有一个，就是全0，异或仍然是0。

第二个命题，对于某个局面(a1,a2,…,an)，若a1^a2…^an!=0，一定存在某个合法的移动，将ai改变成ai’后满足
a1^a2…^ai’…^{an=0。不妨设a1}a2^…an=k，则一定存在某个ai，它的二进制表示在k的最高位上是1（否则k的
最高位那个1是怎么得到的）。这时ai^{k<ai一定成立。则我们可以将ai改变成ai’=ai}k，此时
a1^a2…^ai’…^an=a1a2^…an^k=0。

第三个命题，对于某个局面(a1,a2,…,an)，若a1^a2…^an=0，一定不存在某个合法的移动，将ai改变成ai’后满足
a1^a2…^ai’…^{an=0。因为异或运算满足消去率，由a1}a2^…an=a1^a2…^ai’…^an可以得
到ai=ai’。所以将ai改变成ai’不是一个合法的移动。证毕。

根据这个定理，我们可以在O(n)的时间内判断一个Nim的局面的性质，且如果它是N-position，也可以在O(n)的时间内找到所有的必胜策略。
Nim问题就这样基本上完美的解决了。

在下一节“Sprague-Grundy函数”中，我们将面对更多与Nim游戏有关的变种，还会看到Nim游戏的a1^a2…^an这个值更广泛的
意义。敬请期待。
上一期的文章里我们仔细研究了Nim游戏，并且了解了找出必胜策略的方法。但如果把Nim的规则略加改变，你还能很快找出必胜策略吗？比如说：有n堆石
子，每次可以从第1堆石子里取1颗、2颗或3颗，可以从第2堆石子里取奇数颗，可以从第3堆及以后石子里取任意颗……这时看上去问题复杂了很多，但相信你
如果掌握了本节的内容，类似的千变万化的问题都是不成问题的。

现在我们来研究一个看上去似乎更为一般的游戏：给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移动者判
负。事实上，这个游戏可以认为是所有Impartial Combinatorial
Games的抽象模型。也就是说，任何一个ICG都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。下
面我们就在有向无环图的顶点上定义Sprague-Garundy函数。

首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、
mex{2,3,5}=0、mex{}=0。

对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Garundy函数g如下：g(x)=mex{ g(y) | y是x的后继 }。

来看一下SG函数的性质。首先，所有的terminal
position所对应的顶点，也就是没有出边的顶点，其SG值为0，因为它的后继集合是空集。然后对于一个g(x)=0的顶点x，它的所有后继y都满足
g(y)!=0。对于一个g(x)!=0的顶点，必定存在一个后继y满足g(y)=0。

以上这三句话表明，顶点x所代表的postion是P-position当且仅当g(x)=0（跟P-positioin/N-position的定义的
那三句话是完全对应的）。我们通过计算有向无环图的每个顶点的SG值，就可以对每种局面找到必胜策略了。但SG函数的用途远没有这样简单。如果将有向图游
戏变复杂一点，比如说，有向图上并不是只有一枚棋子，而是有n枚棋子，每次可以任选一颗进行移动，这时，怎样找到必胜策略呢？

让我们再来考虑一下顶点的SG值的意义。当g(x)=k时，表明对于任意一个0<=i<k，都存在x的一个后继y满足g(y)=i。也就是
说，当某枚棋子的SG值是k时，我们可以把它变成0、变成1、……、变成k-1，但绝对不能保持k不变。不知道你能不能根据这个联想到Nim游戏，Nim
游戏的规则就是：每次选择一堆数量为k的石子，可以把它变成0、变成1、……、变成k-1，但绝对不能保持k不变。这表明，如果将n枚棋子所在的顶点的
SG值看作n堆相应数量的石子，那么这个Nim游戏的每个必胜策略都对应于原来这n枚棋子的必胜策略！

对于n个棋子，设它们对应的顶点的SG值分别为(a1,a2,…,an)，再设局面(a1,a2,…,an)时的Nim游戏的一种必胜策略是把
ai变成k，那么原游戏的一种必胜策略就是把第i枚棋子移动到一个SG值为k的顶点。这听上去有点过于神奇——怎么绕了一圈又回到Nim游戏上了。

其实我们还是只要证明这种多棋子的有向图游戏的局面是P-position当且仅当所有棋子所在的位置的SG函数的异或为0。这个证明与上节的 Bouton’s
Theorem几乎是完全相同的，只需要适当的改几个名词就行了。

刚才，我为了使问题看上去更容易一些，认为n枚棋子是在一个有向图上移动。但如果不是在一个有向图上，而是每个棋子在一个有向图上，每次可以任选一个棋子
（也就是任选一个有向图）进行移动，这样也不会给结论带来任何变化。

所以我们可以定义有向图游戏的和(Sum of Graph
Games)：设G1、G2、……、Gn是n个有向图游戏，定义游戏G是G1、G2、……、Gn的和(Sum)，游戏G的移动规则是：任选一个子游戏Gi
并移动上面的棋子。Sprague-Grundy
Theorem就是：g(G)=g(G1)^g(G2)…^g(Gn)。也就是说，游戏的和的SG函数值是它的所有子游戏的SG函数值的异或。

再考虑在本文一开头的一句话：任何一个ICG都可以抽象成一个有向图游戏。所以“SG函数”和“游戏的和”的概念就不是局限于有向图游戏。我们给每个
ICG的每个position定义SG值，也可以定义n个ICG的和。所以说当我们面对由n个游戏组合成的一个游戏时，只需对于每个游戏找出求它的每个局
面的SG值的方法，就可以把这些SG值全部看成Nim的石子堆，然后依照找Nim的必胜策略的方法来找这个游戏的必胜策略了！

回到本文开头的问题。有n堆石子，每次可以从第1堆石子里取1颗、2颗或3颗，可以从第2堆石子里取奇数颗，可以从第3堆及以后石子里取任意颗……我们可
以把它看作3个子游戏，第1个子游戏只有一堆石子，每次可以取1、2、3颗，很容易看出x颗石子的局面的SG值是x%4。第2个子游戏也是只有一堆石子，
每次可以取奇数颗，经过简单的画图可以知道这个游戏有x颗石子时的SG值是x%2。第3个游戏有n-2堆石子，就是一个Nim游戏。对于原游戏的每个局
面，把三个子游戏的SG值异或一下就得到了整个游戏的SG值，然后就可以根据这个SG值判断是否有必胜策略以及做出决策了。其实看作3个子游戏还是保守了
些，干脆看作n个子游戏，其中第1、2个子游戏如上所述，第3个及以后的子游戏都是“1堆石子，每次取几颗都可以”，称为“任取石子游戏”，这个超简单的
游戏有x颗石子的SG值显然就是x。其实，n堆石子的Nim游戏本身不就是n个“任取石子游戏”的和吗？

所以，对于我们来说，SG函数与“游戏的和”的概念不是让我们去组合、制造稀奇古怪的游戏，而是把遇到的看上去有些复杂的游戏试图分成若干个子游戏，对于
每个比原游戏简化很多的子游戏找出它的SG函数，然后全部异或起来就得到了原游戏的SG函数，就可以解决原游戏了。
例子程序：
acm.hdu上的例子

A New Tetris Game 22222

#include
#include
#include
#include

//better if find area that not linked and sg each
typedef bitset<32> int_set;
struct array2{
bitset<64> bs;
int r,c;
bool operator<(const array2& a2)const{
if(r!=a2.r)return r<a2.r;
if(c!=a2.c)return c<a2.c;
return (long long)&bs< (long long)&a2.bs;
}
bitset<64>::reference operator()(int ir,int ic){
return bs[ir*c+ic];
}
}g;
inline int mex(const int_set& is){
if(is.none())return 0;
for(int i=0;i!=32;++i){ //assum i will never exceed 32
if(is.test(i)==0)
return i;
}
}
inline bool check_ok(int ir,int ic){
return !g(ir,ic)&&!g(ir+1,ic)&&!g(ir,ic+1)&&!g(ir+1,ic+1);
}
map<array2,int> ma;
inline void set_it(int ir,int ic,int s){
g(ir,ic)=s;
g(ir+1,ic)=s;
g(ir,ic+1)=s;
g(ir+1,ic+1)=s;
}
inline int sg(int r,int c){
map<array2,int>::iterator p=ma.find(g);//optimizing for the repeated
if(p!=ma.end())return p->second;
int_set sgs;
for(int i=0;i<r-1;++i)
for(int j=0;j<c-1;++j)
if(check_ok(i,j)){
set_it(i,j,1);
sgs.set(sg(r,c));
set_it(i,j,0);
}
return ma[g]=mex(sgs);
}
int main(){
int n;
while(cin>>n){
int out=0;
while(n–){
int r,c;
cin>>g.r >>g.c;
for(int i=0;i!=g.r;++i)
for(int j=0;j!=g.c;++j){
char c;
cin>>c;
g(i,j)=c-‘0’;
}
out^=sg(g.r,g.c);
}
cout<<(out?“Yes”:“No”)<<endl;
}
return 0;
}