20150714学校測试

末蓝、 2022-03-27 06:21 112阅读 0赞

*  **前言**  
    4个题里有两个SCOI的题。还都是2005年的。
 *  **题目**
 *  **一、整数的表示**  
    不论什么一个正整数都能够用2的幂次方表示.比如:137=27\+23\+20同一时候约定次方用括号来表示,即ab可表示为a(b)由此可知,137可表示为:2(7)\+2(3)\+2(0)进一步:7=22\+2\+20(21用2表示)3=2\+20所以最后137可表示为:2(2(2)\+2\+2(0))\+2(2\+2(0))\+2(0)又如:1315=210\+28\+25\+2\+1所以1315最后可表示为:2(2(2\+2(0))\+2)\+2(2(2\+2(0)))\+2(2(2)\+2(0))\+2\+2(0)  
    输入文件:  
    仅仅有一行，就是正整数n(n≤20000)  
    输出文件:  
    仅仅有一行，就是符合约定的n的0,2表示(在表示中不能有空格)
 *  **二、排数问题：**  
    设有n个正整数，将他们连接成一排，组成一个最大的多位整数。
    
    比如：n=3时。3个整数13,312,343,连成的最大整数为:34331213。又如：n=4时。4个整数7,13,4,246连接成的最大整数为7424613。  
    输入文件：  
    输入文件有N+1行。第一行为整数N（≤100）。
    
    此后N行，每行输入一个正整数（≤32767）。  
    输出文件：  
    输出:连接成的多位数。
    
      
    输入输出举例：  
    输入arra.in：  
    3  
    13  
    312  
    343  
    输出arra.out：  
    34331213
 *  **三、 骑士精神（Knight）**  
    在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士。 且有一个空位。在不论什么时候一个骑士都能依照骑士的走法（它能够走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。  
    给定一个初始的棋盘。如何才干经过移动变成例如以下目标棋盘：  
    ![这里写图片描写叙述][20150714153612234]  
    为了体现出骑士精神，他们必须以最少的步数完毕任务。  
    输入文件：  
    第一行有一个正整数T(T≤10)。表示一共同拥有N组数据。接下来有T个5×5的矩阵。0表示白色骑士，1表示黑色骑士，\*表示空位。
    
    两组数据之间没有空行。
    
      
    输出文件：  
    对于每组数据都输出一行。假设能在15步以内（包含15步）到达目标状态，则输出步数。否则输出－1。
    
      
    输入输出举例：  
    Knight.in：  
    2  
    10110  
    01\*11  
    10111  
    01001  
    00000  
    01011  
    110\*1  
    01110  
    01010  
    00100  
    Knight.out  
    7  
    \-1
 *  **四 扫雷 (Mine)**  
    相信大家都玩过扫雷的游戏。
    
    那是在一个n\*m的矩阵里面有一些雷。要你依据一些信息找出雷来。万圣节到了，“余”人国流行起了一种简单的扫雷游戏，这个游戏规则和扫雷一样，假设某个格子没有雷，那么它里面的数字表示和它8连通的格子里面雷的数目。如今棋盘是n×2的，第一列里面某些格子是雷，而第二列没有雷，例如以下图：  
    ![这里写图片描写叙述][20150714153741336]  
    由于第一列的雷可能有多种方案满足第二列的数的限制，你的任务即依据第二列的信息确定第一列雷有多少种摆放方案。
    
      
    输入文件：  
    第一行为N，第二行有N个数，依次为第二列的格子中的数。(1≤N≤10000）  
    输出文件：  
    一个数，即第一列中雷的摆放方案数。
    
      
    输入输出举例：  
    Mine.in:  
    2  
    1  
    Mine.out  
    2
 *  **题解和代码**
 *  第一题一看就是递归处理。
    
    递归中最重要的一环就是设计好边界，本题中当n=20时输出2(0)，n=21时输出2，其余的就能够把n进行二进制分解再分别递归了。要注意何时输出+号。这里能够用树状数组里的低位技术(lowbit)在O(logn)的时间里完毕分解。实測Codevs中(n约为1012)用了7ms，非常快。
    
    分解过后的数能够储存在一个栈里。把栈弹到仅仅剩一个元素时就不要输出+号了。

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int n;
    void init()
    {
        freopen("number.in", "r", stdin);
        freopen("number.out", "w", stdout);
        scanf("%d", &n);
    }
    inline int f(int x)
    //求指数
    {
        int y = -1;
        while(x != 0)
        {
            ++y;
            x >>= 1;
        }
        return y;
    }
    void work(int k)
    {
        int *s = new int[20], top = 0;
        memset(s, 0, sizeof(s));
        while(k != 0)
        {
            s[++top] = (k & (-k));
            k -= (k & (-k));
        }
        for(int i = top; i > 1; --i)
        {
            if(f(s[i]) == 0)
            {
                printf("2(0)");
            }
            else
            {
                if(f(s[i]) == 1)
                {
                    printf("2");
                }
                else
                {
                    printf("2(");
                    work(f(s[i]));
                    printf(")");
                }
            }
            printf("+");
        }
        if(f(s[1]) == 0)
        {
            printf("2(0)");
        }
        else
        {
            if(f(s[1]) == 1)
            {
                printf("2");
            }
            else
            {
                printf("2(");
                work(f(s[1]));
                printf(")");
            }
        }
        delete [] s;
        s = NULL;
    }
    int main()
    {
        init();
        work(n);
        return 0;
    }

*  第二题是非常明显的贪心，但有两种常见的错误思路：  
    把大的数放前面。
    
    反例，9、13，913>139;  
    把短的数放前面。反例。12、123。12312>12123。我一開始就犯了这个错误。  
    事实上仅仅要把a和b这两个数按ab和ba的方式分别放一下，然后若ab>ba，则把a放b前面（能够不相邻）；若ab<ba。则把b放a前面（也能够不相邻）。这样自己定义一个比較函数，快排就可以。

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    struct number
    {
        int num;
        bool operator < (number b) const
        {
            int *p = new int[20], *bp = new int[20];
            int top = 0, btop = 0, k = num;
            bool flag = false;
            memset(p, 0, sizeof(p));
            memset(bp, 0, sizeof(bp));
            //分解每一位
            while(k > 0)
            {
                p[++top] = k % 10;
                k /= 10;
            }
            while(b.num > 0)
            {
                bp[++btop] = b.num % 10;
                b.num /= 10;
            }
            long long s = 0, bs = 0;
            //按ab方式连
            for(int i = top; i > 0; --i)
            {
                s = s * 10 + p[i];
            }
            for(int i = btop; i > 0; --i)
            {
                s = s * 10 + bp[i];
            }
            //按ba方式连
            for(int i = btop; i > 0; --i)
            {
                bs = bs * 10 + bp[i];
            }
            for(int i = top; i > 0; --i)
            {
                bs = bs * 10 + p[i];
            }
            if(s > bs)
            {
                flag = true;
            }
            delete [] p;
            delete [] bp;
            p = bp = NULL;
            return flag;
        }
    };
    number a[105];
    int n;
    int main()
    {
        freopen("arra.in", "r", stdin);
        freopen("arra.out", "w", stdout);
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &a[i].num);
        }
        sort(a + 1, a + n + 1);
        for(int i = 1; i <= n; ++i)
        {
            printf("%d", a[i].num);
        }
        return 0;
    }

*  第三题一眼看上去是一道广搜，但算了一下状态数，发现最多到了815……于是乎想到启示式迭代加深，即IDA\*。然而不幸的是没\*对，全都-1。后来把启示函数改成了普通的可行性剪枝（就是代码中残留的h函数，它的返回值一開始是int的）。然后居然没T。IDA\*->dfsID……实际上这个可行性剪枝是非常强的，当前步数加上和标准答案不一致的位置数假设超过了总步数。那么一定无解。由于走一步顶多把一个骑士的位置修正到正确位置。

#include <cstdio>
    #include <queue>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int t[5][5] = {
          {
          1, 1, 1, 1, 1}, {
          0, 1, 1, 1, 1}, {
          0, 0, -1, 1, 1}, {
          0, 0, 0, 0, 1}, {
          0, 0, 0, 0, 0}};
    const int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[8] = {
          1, 2, 2, 1, -1, -2, -2, -1};
    int T, K, sx, sy;
    int s[5][5];
    bool flag;
    void init()
    {
        char a[10];
        flag = false;
        for(int i = 0; i < 5; ++i)
        {
            scanf("%s", &a);
            for(int j = 0; j < 5; ++j)
            {
                if(a[j] == '*')
                {
                    sx = i; sy = j;
                    s[i][j] = -1;
                }
                else
                {
                    s[i][j] = a[j] - '0';
                }
            }
        }
    }
    bool check(int p[5][5])
    {
        for(int i = 0; i < 5; ++i)
        {
            for(int j = 0; j < 5; ++j)
            {
                if(p[i][j] != t[i][j])
                {
                    return false;
                }
            }
        }
        return true;
    }
    bool h(int now[5][5], int nowk)
    {
        int k = 0;
        for(int i = 0; i < 5; ++i)
        {
            for(int j = 0; j < 5; ++j)
            {
                if(now[i][j] != t[i][j])
                {
                    ++k;
                    if(k + nowk > K)
                    {
                        return false;
                    }
                }
            }
        }
        return true;
    }
    void dfs(int now[5][5], int x, int y, int nowk)
    {
        if(nowk == K)
        {
            if(check(now))
            {
                flag = true;
                return;
            }
        }
        if(flag)
        {
            return;
        }
        for(int i = 0; i < 8; ++i)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx >= 0 && ny >= 0 && nx < 5 && ny < 5)
            {
                swap(now[x][y], now[nx][ny]);
                if(h(now, nowk))
                {
                    dfs(now, nx, ny, nowk + 1);
                }
                swap(now[x][y], now[nx][ny]);
            }
        }
    }
    int main()
    {
        freopen("knight.in", "r", stdin);
        freopen("knight.out", "w", stdout);
        scanf("%d", &T);
        while(T--)
        {
            init();
            for(K = 1; K <= 15; ++K)
            {
                dfs(s, sx, sy, 0);
                if(flag)
                {
                    printf("%d\n", K);
                    break;
                }
            }
            if(!flag)
            {
                puts("-1");
            }
        }
        return 0;
    }

*  第四题看上去像dp计数问题，但一開始并没有想到如何转移，于是先写了个暴搜。起初为了便于以后对拍大数据，就先预处理了一下必须放雷的格子。然后加了若干可行性剪枝。
    
    后来跑大数据时发现挺快的。于是交到了bzoj上，结果20msAC。
    
    省选题啊！暴搜都能过？

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int n, a[10005], ans, c[10005];
    bool f[10005];
    void init()
    {
        freopen("mine.in", "r", stdin);
        freopen("mine.out", "w", stdout);
        memset(f, 0, sizeof(f));
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &a[i]);
            if(a[i] == 3)
            {
                f[i - 1] = f[i] = f[i + 1] = true;
            }
        }
        if(a[1] == 2)
        {
            f[1] = f[2] = true;
        }
        if(a[n] == 2)
        {
            f[n] = f[n - 1] = true;
        }        
    }
    void dfs(int k, bool b)
    //该放第k个位置，同一时候第k-1个位置有没有放雷
    {
        if(k > n && c[k - 1] == a[k - 1])
        {
            ++ans;
            return;
        }
        if(c[k - 2] != a[k - 2])
        {
            return;
        }
        if(c[k - 1] < a[k - 1] && c[k] < a[k])
        {
            ++c[k - 1]; ++c[k]; ++c[k + 1];
            dfs(k + 1, true);
            --c[k - 1]; --c[k]; --c[k + 1];
        }
        if((!f[k]) && (c[k - 1] == a[k - 1]))
        {
            dfs(k + 1, false);
        }
    }
    void work()
    {
        ++c[1]; ++c[2];
        dfs(2, true);
        --c[1]; --c[2];
        dfs(2, false);
        printf("%d\n", ans);
    }
    int main()
    {
        init();
        work();
        return 0;
    }

后来想到了一种方式：f\[i\]\[0||1\]\[0||1\]\[0||1\]第一维表示递推到第i个位置。第二维表示i-1位置的放雷情况，第三维是i位置放雷情况，第四维i+1位置。这样方程就非常清晰（详见代码)。  
仅仅是要注意1的左边和n的右边是不能放雷的。

#include <cstdio>
    #include <algorithm>
    using namespace std;
    int n, a[10005], f[10005][2][2][2];
    void init()
    {
        freopen("mine.in", "r", stdin);
        freopen("mine.out", "w", stdout);
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &a[i]);
        }
        switch(a[1])
        {
            case 0: f[1][0][0][0] = 1;
                    break;
            case 1: f[1][0][1][0] = f[1][0][0][1] = 1;
                    break;
            case 2: f[1][0][1][1] = 1;
                    break;
            default:break;
        }
    }
    void work()
    {
        for(int i = 2; i < n; ++i)
        {
            switch(a[i])
            {
                case 0: f[i][0][0][0] = f[i - 1][1][0][0] + f[i - 1][0][0][0];
                        break;
                case 1: f[i][1][0][0] = f[i - 1][1][1][0] + f[i - 1][0][1][0];
                        f[i][0][1][0] = f[i - 1][1][0][1] + f[i - 1][0][0][1];
                        f[i][0][0][1] = f[i - 1][1][0][0] + f[i - 1][0][0][0];
                        break;
                case 2: f[i][1][1][0] = f[i - 1][1][1][1] + f[i - 1][0][1][1];
                        f[i][1][0][1] = f[i - 1][1][1][0] + f[i - 1][0][1][0];
                        f[i][0][1][1] = f[i - 1][1][0][1] + f[i - 1][0][0][1];
                        break;
                case 3: f[i][1][1][1] = f[i - 1][1][1][1] + f[i - 1][0][1][1];
                        break;
                default:break;
            }
        }
        int ans = 0;
        switch(a[n])
        {
            case 0: ans += f[n - 1][1][0][0] + f[n - 1][0][0][0];
                    break;
            case 1: ans += f[n - 1][1][1][0] + f[n - 1][0][1][0];
                    ans += f[n - 1][1][0][1] + f[n - 1][0][0][1];
                    break;
            case 2: ans += f[n - 1][1][1][1] + f[n - 1][0][1][1];
                    break;
            default:break;
        }
        printf("%d\n", ans);
    }
    int main()
    {
        init();
        work();
        return 0;
    }

*  **总结**  
    临时没思路时要毫不犹豫地先把搜索写上，再没思路就专心优化自己的搜索。
    
    遇到简单的题目更要细心，一旦想错了就什么都完了。

[20150714153612234]: /images/20220327/7b71d9fbeb5e40968e2f679b45bb1718.png
[20150714153741336]: /images/20220327/9a5ab8fb574d4f29ba55ecfab320c9c4.png