前些天在写毕业论文，开题弄了个什么神经网络什么数据融合，至今没搞懂过，真是没话说，但是又不得不硬着头皮写，废话连篇，说来说去就那么几句。做的东西本来挺简单的，没用到那么高深的理论，不过为了装装深度，硬要往上面套，希望最好别出什么问题吧。写论文的时候我就想嗄，写代码好玩多了，异常怀念那段天天在poj上写程序的日子。这两天交完初稿，继续做做题，一是玩玩，二是为了原来定下的一个小目标：毕业前水到500题，还差20。两个比较好玩也折腾得比较久的题目。

poj 2050

这题折腾了很久很久，刚开始误以为每个文件的最大行数为1500，最后因为输出格式问题。代码也比较长330行，954ms。 使用数组作为hash，使用位图记录文件中存在的单词，idx为由单词转化得到的该单词在hash表中的index。

unsigned int docs_flag[MAXDOC][(MAXWORDS+31)/32]; //记录某个文件中是否存在某个单词
void set_docflag(int doc[], unsigned int idx)
{
        doc[idx>>5] |= (1<<(idx&0x1f));
}

int  get_docflag(int doc[],unsigned int idx)
{
        return doc[idx>>5] & (1<<(idx&0x1f));
}

poj 2518

这个好玩，一个4*4的方格，里面分别放四个A,B,C,D，初始状态从输入获取，先随便选取一个字母，然后能进行很多次操作。 每次能交换两个相邻的方格，到任何一个小的2*2的方格中全部都是所选的字母就获胜。对于每一个输入，求最少多少次交换就能达到胜利状态， 以及有多少方案可以达到这个目的。

例如：

AABB
ABAB
CDCD
CCDD          output ==> 1 4 (选择A或者B 交换BA 选择C或者D 交换DC)

ACAB
CBBD
ADAD
DCBC          output ==> 4 96

首先想到还是搜索，用bit来减少空间。求最少次数，BFS搜索也许太慢，毕竟每次状态转移会有16个选择。对于每一个输入，先枚举A,B,C,D进行搜索。对于每一个字母，比如A，用一个整数表示其在方格的位置(最大数字到1<<16)，

AABB
ABAB
CDCD
CCDD            state ==> 1100 1010 0000 0000

胜利的状态有9个，可以先枚举出来，1100110000000000等等。胜利状态比较多，照一般的BFS写下去代码肯定比较复杂，时间和空间肯定也都要求比较多。考虑可以从胜利状态反着向初始状态搜，先把9个胜利状态放入数组，求到初始状态最少的步数，同时可以算出有多少种走法。这样做了还是超时，看有人说线上输入有很多组数据。

看来每次计算调用了四次BFS确实比较要时间，看提示打表，对于每一个输入先查查看以前计算过没有，计算过则直接输出结果，否则照上面的枚举字母，调用BFS。提交还是超时。

再想想，每次输入可能A的分布是一样的，其他字母分布不一样，照上面那样做对于A还是BFS搜索了一次。从16个位置选择4个位置给A的总分布数目是C(16,4)=1820，不是很大的。很开心，把A的状态记录下来，对于每个输入先看看A这种布局以前算过了没有，如果算过则不用算了，其他字母都是一样处理。结果还是超时，无语了。

正要崩溃时，发现自己还是没看到本质，对于A的每一个布局，B不是一样么，是A还是B没关系的啊。所以，打表不用分字母需要1820*4这么大的表，只要一个1820的表就行了。对于每个输入，分字母获取四个分布状态，看这个状态以前是否算过了，如果算过直接拿那个结果，如果没算过算了存下来。再提交，终于AC了，：）这一步步够辛苦的。