一年一度的爆搜杯如期而至，300RMB 四小时上机可还行，此次蓝桥杯不多做评价，上午脑力，下午体力，双倍快乐.....oh好像是三倍快乐...oh或许是四倍快乐...

A 组队（5分）

查数：490

B 年号字串（5分）

image.png

C 数列求值（10分）

数列1，1，1，3，5，9....求其第20190324项的最后四位数字。想到Mod的性质就行。
ans = 4659

#include <iostream>
using namespace std;
int main()
{
    int a = 1;
    int b = 1;
    int c = 1;
    int s = 0;
    for (int i = 4; i <= 20190324; i++)
    {
        s = (a + b + c) % 10000;
        a = b;
        b = c;
        c = s;
    }
    cout << s;
    return 0;
}

D 数的分解（10分）

把2019分解为3个不同的正整数之和，要求每个数字的每一位都不包含2或者4，求共有多少种排列方式。(注意看清题目就好)
ans = 40785

#include <iostream>
using namespace std;
bool ok(int x)
{
    while (x)
    {
        if (x % 10 == 2 || x % 10 == 4)
            return 0;
        x /= 10;
    }
    return 1;
}
int main()
{
    int ans = 0;
    for (int i = 1; i <= 2019; i++)
    for (int j = i + 1; j <= 2019; j++)
    for (int k = j + 1; k <= 2019; k++)
        if (ok(i) && ok(j) && ok(k) && i + j + k == 2019)
            ans++;
    cout << ans;
    return 0;
}

E 迷宫（15分）

山师2018结训赛原题，真真的原题，山师的时候我写的dfs直接过了，but这题数据大了一点点，dfs根本跑不出来。考试的时候对bfs记录路径有点生疏没当时就没写bfs，今天随手写了个bfs跑了一波，秒出答案。唉痛失荆州，15分就这样没了...
答案是：DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
长度是186

#include <iostream>
#include <queue>
#include <stack>
using namespace std;
int n, m, ans;
char map[100][100];
int vis[100][100];

char C[10] = {'D', 'L', 'R', 'U'};
int dx[10] = {1, 0, 0, -1};
int dy[10] = {0, -1, 1, 0};
struct father
{
    int x;
    int y;
    char c;
} f[3050];
struct node
{
    int x;
    int y;
    char c;
};
queue<node> Q;
stack<char> S;
bool ok(int x, int y)
{
    if (map[x][y] == '1' || vis[x][y] || (x < 1) || (x > n) || (y < 1) || (y > m))
        return 0;
    return 1;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> map[i][j];
    Q.push((node){1, 1, 'Q'});
    int k;
    vis[1][1] = 1;
    while (!Q.empty())
    {
        node p = Q.front();
        Q.pop();
        //cout << p.x << " " << p.y << endl;
        if (p.x == n && p.y == m)
        {
            S.push(p.c);
            ans = p.x * 100 + p.y;
            cout << "succesfully!" << endl;
            break;
        }
        for (int i = 0; i < 4; i++)
        {
            int xx = p.x + dx[i];
            int yy = p.y + dy[i];
            if (ok(xx, yy))
            {
                int key = xx * 100 + yy;
                Q.push((node){xx, yy, C[i]});
                vis[xx][yy] = 1;
                f[key].x = p.x;
                f[key].y = p.y;
                f[key].c = p.c;
            }
        }
    }
    while (1)
    {
        if (f[ans].x == 1 && f[ans].y == 1)
        {
            S.push(f[ans].c);
            break;
        }
        //cout << f[ans].x << " " << f[ans].y << endl;
        S.push(f[ans].c);
        ans = f[ans].x * 100 + f[ans].y;
    }
    S.pop();
    cout << "the ans's length is " << S.size() << endl;
    while (!S.empty())
    {
        cout << S.top();
        S.pop();
    }
    return 0;
}

另外我提供一波数据，就是原题的数据，用OCR识别出来的，大家可以拿去验证自己的代码：

30 50
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000

F 特别数的和（20分）

在1到n种找出数字种有2，0，1，9 的数来，求出他们的加和。枚举判断加和就行了。

#include <iostream>
using namespace std;
bool ok(int x)
{
    while (x)
    {
        int xx = x % 10;
        if (xx == 2 || xx == 0 || xx == 1 || xx == 9)
            return 1;
        x /= 10;
    }
    return 0;
}
int n;
long long ans;
int main()
{

    cin >> n;
    for (int i = 1; i <= n; i++)
    if (ok(i))
    ans += i;

    cout << ans;
    return 0;
}

G 完全二叉树的权值（20分）

把每一层的都加个和，每当一层加完就随最大值更新一波题目要求的深度即可，因为是完全二叉树，每层的数有2^(n-1)个；

#include <iostream>
using namespace std;
long long maxx;
int ans;
int cnt;
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i; i++)
    {
        long long deep = 0;
        for (int j = 0; j < (1 << (i - 1)); j++)
        {
            int k;
            cin >> k;
            deep += k;
            cnt++;
        }
        if (deep > maxx)
        {
            maxx = deep;
            ans = i;
        }
        if (cnt >= n)
            break;
    }
    cout << ans;
    return 0;
}

H 等差数列

给一组数据，求可能的最短等差数列；此题大家都想到了先排序，然后找相邻公差，然后找最小公差，然后求解。这样其实只对了一半，他们真正的最小公差是这些所有的相邻差的gcd。其实比较好证明，这里不再证明，给个例子，比如说一个数列1 5 11 他们种两个相邻差是4和6，这时候他们的最小公差不是4，而是gcd(4,6) = 2；把数列还原为最短等差数列是1 3 5 7 9 11，自己理解一下，应该还是比较简单的。另外这个题还有一个坑点就是公差是0的情况，也就是一个数列数字全部相同，如果不特判的话，程序会因为除0而崩掉，所以....我不说了（我特判了,逃...）

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int a[100010]; //记录输入的数列
int d[100010]; //记录相邻的差
int gcd(int x, int y)
{
    if (y)
        return gcd(y, x % y);
    return x;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
    for (int i = 1; i < n; i++)
        d[i] = a[i] - a[i - 1];
    int dd = d[1];
    for (int i = 2; i <= n; i++)
        dd = gcd(dd, d[i]);
    if (dd == 0)
        cout << n;
    else
    {
        int ans = 0;
        for (int i = 1; i < n; i++)
            ans += (d[i] / dd - 1);
        cout << ans + n;
    }
    return 0;
}

J 后缀表达式

emm...这题先不想了，我先水为敬，你们随意。这题大概都用一个方法水的吧

#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int a[100010];
long long ans;
int main()
{
    cin >> n >> m;
    for (int i = 0; i <= n + m; i++)
        cin >> a[i];
    sort(a, a + n + m + 1);
    ans = a[n + m]; //先有个初始值，就是当前数列最大值
    for (int i = n + m - 1; i >= 0; i--)
    {
        if (n > 0) //如果还有加号
        {
            ans += a[i];
            n--;
        }
        else
            ans -= a[i]; //剩下的数据都减掉就是了
    }
    cout << ans;
    return 0;
}

J 星际争霸

水到这里已经九个题了，我怎么有种预感，如果前九个题能做好的话，这最后一个题不做也能省一。哈哈问题是我前九个题九白给了啊.....最后一题再研究研究吧...（ps.当时我是用二分，然后check函数随便水了水，当时不如放掉这个题，去拿下迷宫bfs。长记性了，有舍才有得）

下午爬山，双倍快乐：

image.png
image.png
image.png
image.png

还有三倍快乐和四倍快乐，不能随便说了，会挨打...

3月29日更：
出成绩了，大一选手第一年蓝桥，虽然扔了15分，竟然还拿了省一，当然首先这是B组，另外山东也不是很强......总体来说，本次省赛还是比较水吧，期许自己在国赛为校争光（小声bb：我想捧个国一回来）。话说如果报销300rmb的话明年A组再战。最后祝自己北京划水之旅能划出一朵漂亮点的水花。