前些天在写毕业论文，开题弄了个什么神经网络什么数据融合，至今没搞懂过，真是没话说，但是又不得不硬着头皮写，废话连篇，说来说去就那么几句。做的东西本来挺简单的，没用到那么高深的理论，不过为了装装深度，硬要往上面套，希望最好别出什么问题吧。写论文的时候我就想嗄，写代码好玩多了，异常怀念那段天天在 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

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

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 了，：）这一步步够辛苦的。