kuangbin专题1：简单搜索

总结

差不多把课程的分数凑够以后决定系统地补习知识了。

第一个专题纯纯找手感，一直在写dfs/bfs。

记录如下：

1. POJ1321 - 求所有棋子摆放方式：dfs
2. POJ2251 - 达到某（些）位置最少步数：bfs
3. POJ3278 - 达到某位置最少步数：bfs
4. POJ3279 - 翻转问题：dfs求可行性，再选择总操作数最少的方案
5. POJ1426 - 求0和1组成的倍数：这题有意思，好像可以用dfs但有个更巧妙的暴力，下面详写
6. POJ3126 - 求一个质数变成另一个质数的纯质数路径：素数筛+bfs
7. POJ3087 - 洗牌直到最终状态：纯模拟
8. POJ3414 - 倒水，本质也是最少步数：bfs
9. FZU2150 - 放火，双起点最少步数：先dfs找联通块，再bfs求最小步数
10. UVA11624 - 逃离火场，双起点最少步数题：bfs，注意必须火和人一起轮流bfs否则会TLE
11. POJ3984 - 最少步数：bfs
12. HDU1241 - 求联通块数目：dfs
13. HDU1495 - 倒水，最少步数：bfs
14. HDU2612 - 双起点最少步数：各自单独bfs，然后检查每个终点求最优

POJ1426

参考：[https://blog.algorithmdn.net/lyy289065406/article/details/6647917] 简单来说就是利用模数的性质代替大数本身进行运算，下标对应大数自身的二进制读法（例子：1001 -> mod[0x1001]）；找到模数为0的就用下标重建大倍数结果。

int n;
int mod[524286];
void solve()
{
    mod[1] = 1 % n;

    int i;
    for (i = 2; mod[i - 1] != 0; i++)
    {
        mod[i] = (mod[i / 2] * 10 + i % 2) % n;
    }
    i--;
    int idx = 0;
    while (i)
    {
        mod[idx++] = i % 2;
        i /= 2;
    }
    while (idx)
        cout << mod[--idx];
    cout << endl;
}