标签蓝桥杯下的文章

蓝桥杯2019初赛迷宫

作者: heky
时间: 2025-03-05
分类: 刷题
暂无评论

url: http://oj.ecustacm.cn/problem.php?id=1455

tag: 搜索

思路：使用bfs或者dfs。如果使用bfs需要将每次的路径也放入队列中，当搜到终点时，就直接将答案输出。使用dfs需要使用一种记忆化的剪枝技巧，每次判断当前的路径长度 + 1和即将到达的那个点的到那个点的最短的长度比较，如果大于就直接跳过，如果小于就更新那个点的值。这种做法含有记忆化搜索的思想。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char d[31][51];
char r[] = {'D', 'U', 'L', 'R'};
int nx[] = {1, -1, 0, 0};
int ny[] = {0, 0, -1, 1};
int minv = 0x3f3f3f3f;
string res = "";
bool st[31][51];
int mastep[31][51];
void dfs(int len, int x, int y, string ans)
{
    if (x == 30 && y == 50)
    {
        if (len == minv)
        {
            res = min(res, ans);
        }
        if (len < minv)
        {
            minv = len;
            res = ans;
        }
        return;
    }
    for (int i = 0; i < 4; i ++)
    {
        int xx = x + nx[i], yy = y + ny[i];
        if (xx < 1 || xx > 30 || yy < 1 || yy > 50 || st[xx][yy] || d[xx][yy] == '1') continue;
        if (len + 1 > mastep[xx][yy]) continue;
        if (len >= minv) continue;
        st[xx][yy] = true;
        mastep[xx][yy] = len + 1;
        dfs(len + 1, xx, yy, ans + r[i]);
        st[xx][yy] = false;
    }
}
int main()
{
    memset(mastep, 0x3f, sizeof mastep);
    for (int i = 1; i <= 30; i ++)
        for (int j = 1; j <= 50; j ++)
            cin >> d[i][j];
    dfs(0, 1, 1, "");
    cout << res << endl;
    return 0;
}

答案：

#include <iostream>
using namespace std;
int main()
{
    cout << "DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR" << endl;
}

蓝桥杯2018初赛明码

作者: heky
时间: 2025-02-24
分类: 刷题
暂无评论

url: http://oj.ecustacm.cn/problem.php?id=1369

tag:
模拟

思路：
求字节的二进制表示，其实就是求每个数的补码。对于正数来说，补码就是原码。对于负数来说，先是对原码求反码然后再加1.对于-128来说比较特殊，补码是10000000，通过正常的求法求不出，所以需要特殊判断。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int num[10];

void resoult(int a)
{
    int j = 8;
    while(a)
    {
        num[j --] = a % 2;
        a /= 2;
    }
}
void inverse()
{
    for (int i = 2; i <= 8; i ++)
    {
        if (num[i] == 0) num[i] = 1;
        else num[i] = 0;
    }
    num[8] += 1;
    for (int i = 8; i >= 3; i --)
    {
        num[i - 1] += num[i] / 2;
        num[i] %= 2;
    }
}
void binary(int a)
{
    if (a == -128)
    {
        cout << "1 " << endl;
        return;
    }
    memset(num, 0, sizeof num);
    if (a >= 0)
    {
        num[1] = 0;
        resoult(a);
    }
    else
    {
        num[1] = 1;
        resoult(abs(a));
        inverse();
    }
}
void print()
{
    for (int i = 1; i <= 8; i ++)
    {
        if (num[i]) cout << 1;
        else cout << ' ';
    }
}
int main()
{
    for (int i = 0; i < 10; i ++)
    {
        for (int j = 0; j < 16; j ++)
        {
            int a, b;
            cin >> a >> b;
            binary(a);
            print();
            binary(b);
            print();
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}

简洁版：

#include <iostream>
#include<cstring>
using namespace std;
int num[10];
void print()
{
    
    for(int i=1;i<=8;i++) printf("%c",num[i]==1?"1":" ");
}
int main()
{
    
    int a,b;
    for(int i=1;i<=10;i++)
    {
    
        for(int j=1;j<=16;j++)
        {
    
            cin>>a>>b;
            memset(num,0,sizeof(num ));
            for(int k =8;k>=1;i--) num[k]&=a,a>>=1;
            print();
             memset(num,0,sizeof(num ));
            for(int k =8;k>=1;k--) num[k]&=b,b>>=1;
            print();
            cout<<endl;
        }
        cout<<endl;
    }
    return 0;
}

结果：

     1
     1
     1    1
111111111111
     1    1
     1    1
     1    1
     1    1
     1    1
    1     1
    1     1
   1      1   1
   1      1   1
  1        1111
11

   1     1
   1     1
  1   1  1   1
 1111111 111111
 1    1 1    1
 1    11     1
 1    1      1
 1    1 1    1
 111111  11  1
 1    1   1  1
 1    1      1
 1    1      1
 1    1      1
 111111      1
 1    1   1 1
           1

     1
     1
     1
     1    1
111111111111
     1    1
     1    1
     1    1
     1    1
     1    1
    1     1
    1     1
   1      1   1
   1      1   1
  1        1111
11

        1

 1      1
 1
  11    1
  11
   1   1    1
       1111111
      1     1
    1    1 1
   1     1
  1      1
111      1
  1     1 1
  1     1 1
  1    1   1
  1   1     1
  1  1      111
  1 1        1

     1
      11
       1
             1
111111111111111
     1
     1     1
     11111111
     1     1
     1     1
     1     1
    1      1
    1      1
   1       1
  1     1 1
 1       1

   1     1
   1 1   1  1
  11111 111111
 1  1  1  1
     1 1   1
       1
  11111111111
       1
111111111111111
         1
         1 1
  11111111111
    1    1
     1   1
       1 1
        1


           1
  11111111111
       1
       1
       1
       1     1
111111111111111
       1
       1
       1
       1
       1
       1
       1
     1 1
      1

      1
      1
     1111111
    1     1
   11    1
  1  1 11
  1  1 1
      1 1
      1
    11  1
    11
 111   1111111
      1     1
    11     1
   1  1   1
  1    111
       1
    111
 111

       1
       1
       1
    1  1  1
    1  1   1
   1   1    11
   1   1     1
  1    1   1
 1     1   1
       1  1
       1 1
        1

       1
      1
    11
 111




     1111111
   11      11
  11        11
  111       11
          111
        111
        11
        1



       11
       1
      1111
       11
       1

答案：

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int main()
{
    printf("%.0f", pow(9, 9));
    return 0;
}

蓝桥杯2018初赛乘积尾零

作者: heky
时间: 2025-02-23
分类: 刷题
暂无评论

url: http://oj.ecustacm.cn/problem.php?id=1361

tag:
数学

思路：
计算末尾零可以求每个因子中有多少对因子5和因子2，因为2 * 5 = 10，又因为2出现的次数会比5多，因为只要是偶数的情况就会出现因子2.所以只要计算这100个数中，每个数中因子5的个数，然后累加最后输出即可。

对于求阶乘来说，如果是某个数的阶乘，求这个数除以5，25，125……5^k之后累加。例如100除以5之后等于20，那么对于1到20来说每个数乘以5后都会变成一个贡献5因子的数，除以25之后等于4说明1到4中每个数乘25都可以变成一个贡献25因子的数，而25 = 5 5，则是在原来贡献了5因子基础上多贡献一个5，为了避免重复，以及避免漏算，只需要将4 加上 20，即为答案。说明对于100！（1 2 3 …… * 100）来说，一共可以贡献出24个因子5，就是有24个末尾0.这种求阶乘末尾0的方式实际上和本题有出路。

代码：

// 乘积尾零
#include <iostream>
using namespace std;
int main()
{
    int n = 10;
    int cnt = 0;
    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < n; j ++)
        {
            int a;
            cin >> a;
            while (a && a % 5 == 0)
            {
                if (a % 5 == 0)
                {
                    a /= 5;
                    cnt ++;
                }
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

答案：

#include <iostream>
using namespace std;
int main()
{
    cout << 31 << endl;
    return 0;
}

蓝桥杯 2018 省 B 测试次数

作者: heky
时间: 2025-02-22
分类: 刷题
暂无评论

url: http://oj.ecustacm.cn/problem.php?id=1370

tag:
动态规划

思路：
使用动态规划的思想，令 f[i][j] 表示在i层楼内，使用j部手机，在使用最佳策略下，最多的测试次数，换句话说就是在i层楼内，使用j部手机最少需要花费的最大的测试次数。对于只有1部手机的情况来说，有几层就要测试几次。对于0层来说，不管几部手机都是0次。因为不知道从那一层开始掉落可以得到最优的答案，所以可以枚举对于每一个i都枚举从1开始到i层，表示从第k层开始掉落得到的结果。而对于每一个k来说，需要取一个最大值一共只有两种情况一种是摔坏，那么可以是 dp[k - 1][j - 1] 表示从k - 1层内用j - 1部手机测试次数，如果没有摔坏就是 dp[i - k][j] 即，剩余的i - k层内使用j部手机测试次数，之后两者取max再加上第k层的1次，对每种k的结果取min就是最后答案。最后输出 dp[1000][3] 表示1000层内，3部手机测试次数。

代码：

// 测试次数
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n = 1000;
int dp[1001][4];
int main()
{
    memset(dp, 0x3f, sizeof dp);
    for (int i = 1; i <= n; i ++) dp[i][1] = i;
    for (int i = 1; i <= 3; i ++) dp[0][i] = 0;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= 3; j ++)
            for (int k = 1; k <= i; k ++)
                dp[i][j] = min(dp[i][j], max(dp[k - 1][j - 1], dp[i - k][j]) + 1);
    cout << dp[1000][3];
    return 0;
}