好用不经用 ，EG.

上上个星期买了一块EG, 正反狂3. 一个星期就适应了，比OC更适合我。 但是，今天重新刷一遍胶水，面材就脱落了一小块。。。。 真不经用。郁闷。

Blogger里面插代码

Blogger的HTML编辑器插入C代码比较麻烦,得加一个pre，但是pre也不太方便。真是的。不知道有什么好的办法。直接从本地编辑器复制出来的代码粘贴到Blogger就乱七八糟的，自作主张的做了各种排版。不知道在哪里去调整。 晚上去和表弟喝酒，这次的做题先就不写了，和下次的题目一起写。 唉，周末真无聊，自从英超被买断，再也没看过英超，意甲周末也是不一定有，西甲太晚，看球是没什么指望了。要不再去打大波罗？以前在学校是联机玩，单机我玩了一个死灵，到地狱打不动了，全招的，累死了。去玩个法师好了。

北京奥运

本来我对北京奥运没什么特别的感觉。但是最近的关于奥运的事件，打上ZD事件的烙印，觉得奥运对于中国，开始有了某种特殊的意义。这次ZD事件和奥运的风波，在中国，无论各方都在重新思考，世界和中国。

真的没玩够

我最不后悔的事情，和某些人比较，就是在大学的时候选择的是玩的路线，嘿嘿。真的很开心，现在工作了才觉得好明智，如果大学没玩，工作后就没有什么玩的意思了。 很庆幸的是，我到大学之后，电脑已经开始普及，高中的时候电脑游戏就开始兴起，不过大学之后，游戏更呈“专业化”发展。所以，玩的主题基本就是游戏了。其他的，于前辈人共有的比如喝酒唱歌之类，自然不在话下。无论何时，总能找到一帮子人，和你玩。大学三个班，第一年和三班玩，第二年和一班玩，第三年和一班玩，第四年和二班玩。 工作后，身边的朋友逐渐远走了，也没人可以玩了。生活真的黯淡了很多，也许有些人会说，玩够了，该干正经的了，或者说，年纪不小了，该收了。可是我怎么总是觉得没有玩够啊，现在每天没有人一起玩游戏，的确没什么时间，可是觉得现在这样是在浪费生命。 每天回去我都只能在cs,sc两个老游戏里面殴电脑，把他们想像成曾经的同学。。。 。。。 生命在于玩乐。

第三题很失败，1015。

妈的， space速度还真不是一般的慢，还是用我的blogspot好了，虽然国内无法访问。 这周做个题目不顺，就是那个1015,陪审团问题。虽然有个思路，但是因为实在没有时间去做，没有提交，因为老是没作对。 思路是类似动态规划。貌似不能叫做动态规划来解的题，因为题目的最优解并不是通过求解相同最优子结构来做的，而是通过相同子结构迭代求一系列解来做。求和问题和01背包很类似，有大量同子问题。通过增长决策的源数据下标，增长求和个数（<=20），不断求得一个范围内的和数问题。然后选择最优的。因为没有用去尝试这个解法（空间复杂度比较高，而且用C写，存路径很麻烦的，debug也要费不少时间），所以不敢保证是对的，也不想再纠缠下去。 Bs自己。 后来在《算法导论》的NP完全问题的近似解法中也看到一个类似的算法求子集和数的问题（不过这个和数是固定的，子结构中超过这个和数就可以cut掉，解法没什么，但是那个通过归并排序来求下个决策下标的和数比较不错），书上没说这个是属于动态规划，俺也不敢说。虽然真的和动态规划很像。

第二题1175和一些思考

第二题本来是乱选一个题目是个求解同棋局问题，但是我觉得题意有点不清晰。（到底是形状匹配还是下法匹配），打开discuss，有人说数据有问题，很容易pass,另外一个人说和1175题目完全一样，我就去做了1175。

http://acm.pku.edu.cn/JudgeOnline/problem?id=1175

1175是个很浪漫的题目，求解星空中所有相同的星簇（cluster）。 (98 IOI). 这个题目乍一看相当简单，但是做起来发现也是很容易出错的。
我的结果是16MS。未作更多优化。
思路很简单，先逐个查找出所有的星簇，当找到一个星星就从她开始递归的连接出所有的其他星星，存储宽，高等足够的信息。
然后从已经找到的星簇中寻找相同的，旋转和倒映的，如果没有找到就继续。找到了，要把星星标记重新标记为已经存在的那个字符。这里我对于旋转和映射没有使用公式而是使用一个scanner函数表，不同的方向各自一个，本质上就是对于源的一个scan顺序，目标只要使用scanner表离得任何一个通过检测就OK了。里面没用公式，推导公式我觉得不如组织好的代码更不容易出错。而且效率差不多。而且当时觉得scanner的状态可能对后面解题有帮助。（其实没有-_-!）

过了题目中的简单数据，提交上去，立刻WA...

（总是在拉屎的时候思路稍微清晰），如果两个相同的星系相互侵入，那么直接通过标记来判断就不对了，必须保留星星属于哪个星系的信息，否则再重标记之后就会导致以后的检测错误。简单了，再加个数组，存储星tag为他们所在星簇的idx.

OK。过了。
对于效率，因为数据量很小，并没有去做一些一优化，稍微加了一个星星总数判断，但是没有什么改观。
但是如果数据量很大，有一点值得思考，类似KMP的字符串普配算法，对于星系的匹配判断是可以做优化的：
就是一个方向的检测失败，这个结果是可以使用到其他方向的，而且这个因素是这个星簇自己的属性。因此可能有这么一个算法:

当方向d1测试失败，所处scanner的位置（简单起见，用其中一个整数，行）i,有：
此时i之前的数据都是已知的，那么就会有一些方向不需要再匹配，另外一些方向只需要从某个scanner位置开始匹配。这个信息可以作为:
f(d1, i, d2) =
{
   = -1 :不可能匹配
   or d2 scanner的起始位置 (i,j)。
}//d2是新的一个方向


那么每当得到一个cluster,就可以求出这个f的集合。可以自己和自己匹配得到。
比如：
[XXXXXX]
[XXXXXX]
[------]
[VVVVVV]
[VVVVVV]
x和v表示某两个方向的匹配成功，那么对x的来说，一次匹配失败如果在-----，那么到v的方向在匹配只需要到----
开始，如果在XXXXX就完蛋了，那么V也没必要比较。

这样做要增加空间复杂度来存储这些信息。降低星簇查找形同的匹配算法的时间复杂度常数因子。但是对于数据量很小，感觉得不偿失，自己和自己的匹配也是要时间的。这个想法也是一个粗糙的，没去实现，工作比较忙，也没什么时间

#include "stdio.h"

#define MAX_STAR 160
#define MAX_CLSTR 501
#define DIR_NUM 8
#define MAX_W   101
#define MAX_H   101

static char sky[MAX_H][MAX_W];
static int  tag[MAX_H][MAX_W];
static int w;
static int h;
   

typedef struct cluster_t
{
    /*int x[MAX_STAR];
    int y[MAX_STAR];*/
    int start_c;
    int start_l;
    int end_c;
    int end_l;

    int num;
   
    int  idx;
    char mark;
}TCluster;

typedef int (* _scanner_check_dir_fct)(TCluster * c1, TCluster * c2);
typedef int (* _scanner_step_dir_fct)(
    int *pi, int *pj, int sc, int ec, int sl, int el);

TCluster clusters[MAX_CLSTR];
int clusters_count = 0;

static int
simlar_check_star(
   TCluster * c1, int i1, int j1, TCluster *c2, int i2, int j2)
{
    return (      
                    (tag[i1][j1] == c1->idx && tag[i2][j2] == c2->idx)                  
               ||   (tag[i1][j1] != c1->idx && tag[i2][j2] != c2->idx)
              
           );
}




static int
_scanner_check_dir_wh(TCluster * c1, TCluster * c2)
{
    int w1, h1, w2, h2;
    w1 = c1->end_c - c1->start_c + 1;
    w2 = c2->end_c - c2->start_c + 1;
    h1 = c1->end_l - c1->start_l + 1;
    h2 = c2->end_l - c2->start_l + 1;
    if(w1 == w2 && h1 == h2 && c1->num == c2->num)
    {
        return 1;
    }
    return 0;
}

static int
_scanner_check_dir_hw(TCluster * c1, TCluster * c2)
{
    int w1, h1, w2, h2;
    w1 = c1->end_c - c1->start_c + 1;
    w2 = c2->end_c - c2->start_c + 1;
    h1 = c1->end_l - c1->start_l + 1;
    h2 = c2->end_l - c2->start_l + 1;
    if(w1 == h2 && w2 == h1 && c1->num == c2->num)
    {
        return 1;
    }
    return 0;
}

static int
_scanner_step_dir_lrtb(int *pi, int *pj, int sc, int ec, int sl, int el)
{
   
    (*pj)++;
    if(*pj > ec)
    {
        *pj = sc;
        (*pi) ++;
        if(*pi > el)
        {
            return 0;
        }
    }
    return 1;
}

static int
_scanner_step_dir_rltb(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pj)--;
    if(*pj < sc)
    {
        *pj = ec;
        (*pi) ++;
        if(*pi > el)
        {
            return 0;
        }
    }
    return 1;
}

static int
_scanner_step_dir_lrbt(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pj) ++;
    if(*pj > ec)
    {
        *pj = sc;
        (*pi) --;
        if(*pi < sl)
        {
            return 0;
        }
    }
    return 1;
}



static int
_scanner_step_dir_rlbt(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pj) --;
    if(*pj < sc)
    {
        *pj = ec;
        (*pi) --;
        if(*pi < sl)
        {
            return 0;
        }
    }
    return 1;
}


static int
_scanner_step_dir_tblr(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pi) ++;
    if(*pi > el)
    {
        *pi = sl;
        (*pj) ++;
        if(*pj > ec)
        {
            return 0;
        }
    }
    return 1;
}

static int
_scanner_step_dir_btlr(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pi) --;
    if(*pi < sl)
    {
        *pi = el;
        (*pj) ++;
        if(*pj > ec)
        {
            return 0;
        }
    }
    return 1;
}

static int
_scanner_step_dir_tbrl(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pi) ++;
    if(*pi > el)
    {
        *pi = sl;
        (*pj) --;
        if(*pj < sc)
        {
            return 0;
        }
    }
    return 1;
}



static int
_scanner_step_dir_btrl(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pi) --;
    if(*pi < sl)
    {
        *pi = el;
        (*pj) --;
        if(*pj < sc)
        {
            return 0;
        }
    }
    return 1;
}



/*l:0, c:1*/
static int _scanner_start[DIR_NUM][2] = {
    {0, 0},
    {0, 1},
    {1, 0},
    {1, 1},
    {0, 0},
    {1, 0},
    {0, 1},
    {1, 1}};



static _scanner_step_dir_fct _scanner_step_funcs[DIR_NUM] = {
    _scanner_step_dir_lrtb,
    _scanner_step_dir_rltb,
    _scanner_step_dir_lrbt,
    _scanner_step_dir_rlbt,
    _scanner_step_dir_tblr,
    _scanner_step_dir_btlr,   
    _scanner_step_dir_tbrl,
    _scanner_step_dir_btrl
};

static _scanner_check_dir_fct  _scanner_filter_funcs[DIR_NUM] = {
    _scanner_check_dir_wh,
    _scanner_check_dir_wh,
    _scanner_check_dir_wh,
    _scanner_check_dir_wh,
    _scanner_check_dir_hw,
    _scanner_check_dir_hw,
    _scanner_check_dir_hw,
    _scanner_check_dir_hw
};


static int
is_same(TCluster * c1, TCluster * c2, int * pdir)
{
    int dir;
    int i1, j1;
    int i2, j2;

  

    for(dir = 0;  dir < DIR_NUM; dir ++)
    {
        if(_scanner_filter_funcs[dir](
            c1, c2) == 0)
        {
            continue;
        }
        i2 = (_scanner_start[dir][0] == 1)?(c2->end_l):(c2->start_l);
        j2 = (_scanner_start[dir][1] == 1)?(c2->end_c):(c2->start_c);

        for(i1 = c1->start_l; i1 <= c1->end_l; i1 ++)
        {  
            for(j1 = c1->start_c; j1 <= c1->end_c; j1 ++)
            {              
                if(simlar_check_star(c1, i1, j1, c2, i2, j2))
                {
                    _scanner_step_funcs[dir](
                        &i2,
                        &j2,
                        c2->start_c,
                        c2->end_c,
                        c2->start_l,
                        c2->end_l);
                    continue;
                }
                else
                {
                    goto LB_NextCheck;
                }
              
            }           
        }
        *pdir = dir;
        return 1;
LB_NextCheck:;
    }

    return 0;
}


static void
remark_as_old(TCluster * clstr, int curmark, int oldmark)
{
    int i;
    int j;
    for(i = clstr->start_l; i <= clstr->end_l; i ++)
    {
        for(j = clstr->start_c; j <= clstr->end_c; j ++)
        {           
            if(sky[i][j] == curmark && tag[i][j] == clstr->idx)
            {
                sky[i][j] = oldmark;
            }
        }
    }
    clstr->mark = oldmark;
   
}

static int
find_and_merge_cluster(int c_idx)
{
    int i;
    int dir;
    TCluster * clstr;
    TCluster * old_clstr;

    clstr = clusters + c_idx;
   
    for(i = 0; i < c_idx; i ++)
    {
        old_clstr = clusters + i;
        if(is_same(old_clstr, clstr,  &dir) == 1)
        {
            remark_as_old(clstr, clstr->mark, old_clstr->mark);
            return 1;  
        }
    }
    return 0;
}


static void
build_cluster(int c_idx, int i, int j, char cur_mark)
{
    if(i <>= h || j >= w)
    {
        return;
    }

    if(sky[i][j] == '1')
    {
        sky[i][j] = cur_mark;
        tag[i][j] = c_idx;
        clusters[c_idx].num ++;
      
        if(i < clusters[c_idx].start_l)
        {
            clusters[c_idx].start_l = i;           
        }
        if(j < clusters[c_idx].start_c)
        {
            clusters[c_idx].start_c = j;           
        }
        if(i > clusters[c_idx].end_l)
        {
            clusters[c_idx].end_l = i;           
        }
        if(j > clusters[c_idx].end_c)
        {
            clusters[c_idx].end_c = j;           
        }
     
    }
    else
    {
        return;
    }

    build_cluster(c_idx, i - 1, j - 1, cur_mark);
    build_cluster(c_idx, i    , j - 1, cur_mark);
    build_cluster(c_idx, i + 1, j - 1, cur_mark);
    build_cluster(c_idx, i + 1, j    , cur_mark);
    build_cluster(c_idx, i + 1, j + 1, cur_mark);
    build_cluster(c_idx, i    , j + 1, cur_mark);
    build_cluster(c_idx, i - 1, j + 1, cur_mark);
    build_cluster(c_idx, i - 1, j    , cur_mark);
}




static void
get_clusters()
{
    int i, j;
    int idx;
    char cur_mark = 'a';
   
    for(i = 0; i < h; i ++)
    {
        for(j = 0; j < w; j ++)
        {
            if(sky[i][j] == '1')
            {
                idx = clusters_count;

                clusters[idx].mark      = cur_mark;
                clusters[idx].start_c   = MAX_W + 1;
                clusters[idx].end_c     = -1;
                clusters[idx].start_l   = MAX_H + 1;
                clusters[idx].end_l     = -1;
                clusters[idx].idx       = idx;
               
                build_cluster(idx, i, j, cur_mark);
                /*Not found old the same*/
                if(find_and_merge_cluster(idx) == 0)
                {
                    cur_mark ++;
                }

                clusters_count ++;
            }
        }
    }
}

static void
output()
{
    int i;
    int j;

    for(i = 0; i < h; i ++)
    {
        for(j = 0; j < w; j ++)
        {
            printf("%c", sky[i][j]);
        }
        printf("\n");
    }

}

int p_1175_go()
{
    int i;
    int j; 
    char inp;

    scanf("%d\n", &w);
    scanf("%d\n", &h);

    for(i = 0; i < h; i ++)
    {
        for(j = 0; j < w; j ++)
        {
            scanf("%c", &inp);           
            sky[i][j] = inp; 
            tag[i][j] = -1;
        }
        scanf("%c", &inp);
    }
   
    get_clusters();
    output();    
}
int main(void)
{
   
    p_1175_go(1175);
}

BT的第一题

做ACM题计划刚开始就让自己撞了个大钉子，随便选了一个题目，1011，没想到是个超级BT的搜索剪枝题。
Description

George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.
Input

The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.
Output

The output should contains the smallest possible length of original sticks, one per line.
Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
Sample Output

6
5刚看到这个题目觉得还挺简单的，（其实主要原因是有个中文翻译-_-~~). 大概思路就是一开始根据题目的条件有范围确定，接着就是可以回朔搜索了。搜索的时候要剪枝。。.
但是做了就知道根本不是这么简单的。TLE了无数次。
问题的特点就是除了快速求满足一个长度棍子的解之外，还得快速去掉解。
第一个很容易想到的，求解范围，需要整除棍子长度之和，不能小于最大的小棍子长度，个数在小棍子数之内。这些想不到，这题目直接88.
然后搜索的策略，我一开始就走的不对，一开始的方案是让小棍子选择原始棍子的标号搜索，然后剪去原始棍子标号重复。但是这个办法剪枝太难了，因为很容易进入很深的搜索却还对局势没有掌握。放弃。
只能一根根根子去求解，这里面剪枝就多了，棍子排序（自然会想到排序的，快点从大棍子的失败中解脱，并且在后面是的搜索本身呈现顺序性，易于剪枝），然后就是单独原始棍子的后续不要重复的剪枝，还有一个同一长度不在再次使用（在前面排了序，这儿就方便了）的剪枝。有些明显的东西比如长度要刚好满足一个棍子不能叫做剪枝了。上传TLE. TLE. TLE .......
上班比较忙，周末回家才想了一些新办法，但是不知道有些剪枝是不是有问题，最后找到几个可能的剪枝，但是实现起来，代码看着越来越烦了，真不想做了，后来才发现代码里有个保守的错误，这个错误改掉。AC.....大概600MS,虽然不是0MS，我也满意了，痛苦啊。。虽然还有可剪的，但是我已经不想再折磨自己了。
后来才知道1011是个经典的，BT的搜索剪枝题目。
BS 自己。

PS.那个排序用C qsort，速度比泡泡慢 -_~
代码改了很多，看着有点想吐！
#include "stdio.h"

int inp_b[64];
int inp_c = 0;
int min_inp;
int max_inp;
int curL[64];
int curCount[64];

/*int dbg_lay[64][5];*/
int lay[64][64];
int maxC;
int minL;

int used[64];
int usedCount = 0;
static int curSrcIdx;

#define USE(idx)\
do{\
used[idx] = 1;\
curL[curSrcIdx] += inp_b[idx];\
curCount[curSrcIdx] ++;\
usedCount ++;\
/*dbg_lay[curSrcIdx][curCount[curSrcIdx] - 1] = inp_b[idx];*/\
lay[curSrcIdx][curCount[curSrcIdx] - 1] = idx;\
}while(0)
#define UNUSE(idx)\
do{\
curL[curSrcIdx] -= inp_b[idx];\
used[idx] = 0; \
curCount[curSrcIdx] --;\
usedCount--;\
/*dbg_lay[curSrcIdx][curCount[curSrcIdx]] = 0;*/\
lay[curSrcIdx][curCount[curSrcIdx]] = 0;\
}while(0)

static int tryloop2(int lastIdx)
{
int idx;
int last = 100000;
int ret;
  
if(inp_c - usedCount < idx =" lastIdx;" last =" inp_b[idx];" cursrcidx ="="" ret =" tryloop2(lay[curSrcIdx" cursrcidx ="="" ret ="="" ret ="tryloop2(idx))" ret ="="" i =" 0;" i =" 0;" usedcount =" 0;" cursrcidx =" 0;"> *((int *)p2) )
{
 return -1;
}
else if(*((int *)p1) < *((int *)p2))  {   return 1;  }  else   {   return 0;  } } void b_sort(int inp_b[], int inp_c) {  int i;  int j;  int t;  for(i = inp_c - 1; i >= 0 ; i --)
{
 for(j = 0; j <> inp_b[j])
  {
   t = inp_b[j + 1];
   inp_b[j + 1] = inp_b[j];
   inp_b[j] = t;
  }
 }
}
}
int main(void)
{

int i;


int s = 0;


while(1)
{
 scanf("%d", &inp_c);
 if(inp_c == 0)
 {
  return 0;
 }

 for(i = 0; i < s =" 0;" max_inp =" 0;" min_inp =" 100;" i =" 0;"> inp_b[i])
  {
   min_inp = inp_b[i];
  }
  if(max_inp < max_inp =" inp_b[i];" maxc =" inp_c;"> 0; maxC --)
 {
 
  if(s % maxC == 0)
  {
   minL = s/maxC;
   if(minL < max_inp)
   {
    continue;
   }
  
   //An possible minL;
   if(start_tryloop() == 1)
   {
    break;
   }
  }
 }
}
}

在Linux下面开发GL

自从开始用DFB重新实现GL,但是终于要到目标平台上面做Porting,效果很差，问题很多。这段时间都很忙。看得很紧，今天终于出来界面了，但是问题太多了。Linux和以前的嵌入式的OS差距太大了。首先问题就是地址，以前的地址都是没有用户空间和内核空间的区别，现在有了，问题就出来了，关键是以前留下的代码很难更改。加上要实现的接口是一个用了好几年的一个庞大的库，自我有对下面Driver的依赖，转接到DFB上面也是相当的麻烦的扭捏。 这段时间到时真的学了一点点Linux开发，不过到现在Linux命令还不熟，真倒。

难写25周岁之后

2月6号过去了，还是个除夕。在窗外一片白茫茫中，和爸妈一起迎来了我的25周岁。 本来想做个25年来的大总结，大反省，大计划。可是一打开Blogger,就手发僵，不愿多写。又不是皇帝老子，粉饰和批评都没啥意思。 想写一个流水帐，把我记住的故事写下来，人不能丢掉记忆。我想写我的小学，中学，大学，想写我的亲人，朋友，爱人，想写编程，漫画，游戏... ...25年经历的东西太多了，怕自己忘记，可又怕写的不好，反而让美好的东西变成俗套。 我以为在这篇BLOG会写很多东西，但是这件草稿一直都没办法继续下去。以后看看找点系列来写。。。BS 自己

雪灾黄丝带

我们都想回家过年！ 请关注中国雪灾 虽然近在咫尺，我确都不一定能回成家。车票紧张，车更紧张。