找了连贯的两个小时试了下去年面向 16/17 级的蓝桥杯预选赛题目,面向 18 级的题没法合练就划水算了...

16/17:http://47.103.1.213:5000/contest/14/problems
18:http://47.103.1.213:5000/contest/13/problems

感觉还是太匆忙,而且是从头怂到尾... 实际上六道题能读题的也就五道,能敲出个程序的也就四道,能 AC 的才三道。哪怕给多半小时奇迹估计也不会发生...

A

按理来说时间复杂度学完对自己的程序应该有底才对,结果 A 题立刻想到的 O(n²) 暴力枚举都不敢写,看了一下提交记录发现俩一九级的才敢放心交。

HT 写的第 k 个密码和第 k+1 个密码有啥关系呢,(((a[k] * i + j) % 10001) * i + j) % 10001 == a[k + 1],那就枚举 i 和 j,找到满足上面式子的情况就可以了。

AC 代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < 6000; i++)
    {
        for (int j = 0; j < 6000; j++)
        {
            int flag = 0;
            for (int k = 0; k < n - 1; k++)
            {

                if ((((a[k] * i + j) % 10001) * i + j) % 10001 != a[k + 1])
                {
                    flag = 1;
                    break;
                }
            }
            if (flag == 0)
            {
                for (int l = 0; l < n; l++)
                {
                    cout << (a[l] * i + j) % 10001 << endl;
                }
                return 0;
            }
        }
    }

    return 0;
}

B

B 题写贪心直到 AC 还是莫名其妙不知道为啥贪心是正解,总感觉会出现一路贪心下来会有存在多余的钱啥吃的都买不到的情况。结果后来被告知是因为数据太水了。

突击了 DP 的 0/1 背包问题,再回头看其实这就是一道模板题。要特别注意的是有些菜的数量说是为零实际上是可以任点的,处理方法很简单,用自己的钱除以菜品的价格得到的数量向上取整把零换掉就行。

AC 代码:贪心(非正解)

#include <bits/stdc++.h>
using namespace std;

struct food
{
    int p, w, x;
} a[40];

bool cmp(food a, food b)
{
    return (a.w * 1.0 / a.p) > (b.w * 1.0 / b.p);
}

int main()
{
    int n, s, ans = 0;
    cin >> n >> s;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i].p >> a[i].w >> a[i].x;
    }
    sort(a, a + n, cmp);
    for (int i = 0; i < n; i++)
    {
        int tmp = a[i].x;
        while (s >= a[i].p)
        {
            if (tmp == 0)
            {
                ans += a[i].w;
                s -= a[i].p;
            }
            else if (a[i].x > 0)
            {
                ans += a[i].w;
                a[i].x--;
                s -= a[i].p;
            }
            else
                break;
            //cout << ans << endl;
        }
    }
    cout << ans << endl;
    return 0;
}

AC 代码:DP(正解)

#include <bits/stdc++.h>
using namespace std;

int N, S, dp[510];

struct
{
    int p, w, x;
} food[40];

int main()
{
    cin >> N >> S;
    for (int i = 1; i <= N; i++)
    {
        cin >> food[i].p >> food[i].w >> food[i].x;
        if (!food[i].x)
            food[i].x = ceil(S * 1.0 / food[i].p);
    }
    for (int i = 1; i <= N; i++)
    {
        while (food[i].x--)
        {
            for (int j = S; j >= food[i].p; j--)
                dp[j] = max(dp[j], dp[j - food[i].p] + food[i].w);
        }
    }
    cout << dp[S] << endl;
    return 0;
}

C

C 题就是初中就会的条件概率,比洛谷月赛都不知道友好了多少,结果交了一发 WA 后脑抽觉得应该考虑一下精度的问题(一定是洪水那题害的),就两边同乘了两个分母想避免这种问题,结果改了一处又忘记改另一处,罚了好多时。

简单来说,就是对于读入的字符串,统计一下零的数量,再统计一下连续两个零的数量。如果如果我转转盘,不中枪的概率就是零的数量除以字符串的长度。如果我不转转盘,不中枪的概率就是连续两个零的数量除以字符串中零的数量。两个概率比较一下即可。

AC 代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string a;
    while (cin >> a)
    {
        int ans = 0, zero = 0;
        int l = a.size();
        for (int i = 0; i < l; i++)
        {
            if (a[i] == '0')
                zero++;
            if (i < l - 1 && a[i] == '0' && a[i + 1] == '0')
                ans++;
        }
        if (a[l - 1] == '0' && a[0] == '0')
            ans++;
        if (zero * zero > ans * l)
            cout << "This is going to panic,the problem is big." << endl;
        else if (zero * zero < ans * l)
            cout << "Don't panic,the problem is not big." << endl;
        else
            cout << "To panic,or not to panic,that is the question." << endl;
    }
}

D

D 其实应该先做的,目测也就模拟几下... 只是看样例的时候看后面的 M 行有点晕就跳了(后来再看也很好懂啊)。

实际上这道题可以用前缀和的思想来解,包括已经行走的总时间和方位。我们可以用 0 来表示北,1 为东,2 为南,3 为西。向右转就加一,向后转就加二,以此类推。最后的数字对四取模就好了。至于最后报出行走时间求方位,怎样定位我这个时间位于那条路呢,STL 有一个 lower_bound 的二分查找函数可以使用。

AC 代码

#include <bits/stdc++.h>
using namespace std;

// 0 - N
// 1 - E
// 2 - S
// 3 - W

int roadf[100005] = {0}, roadt[100005] = {0};

int n, m, tmpt;
char tmpf;
int main()
{
    scanf("%d\n", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%c %d\n", &tmpf, &tmpt);
        roadt[i] = roadt[i - 1] + tmpt;
        if (tmpf == 'R')
            roadf[i] = roadf[i - 1] + 1;
        if (tmpf == 'L')
            roadf[i] = roadf[i - 1] + 3;
        if (tmpf == 'B')
            roadf[i] = roadf[i - 1] + 2;
        if (tmpf == 'F')
            roadf[i] = roadf[i - 1];
        roadf[i] %= 4;
    }
    scanf("%d\n", &m);
    for (int i = 0; i < m; i++)
    {
        scanf("%c %d\n", &tmpf, &tmpt);
        int ans = lower_bound(roadt + 1, roadt + 1 + n, tmpt) - roadt;
        if (tmpf == 'R')
            tmpf = 1;
        if (tmpf == 'L')
            tmpf = 3;
        if (tmpf == 'B')
            tmpf = 2;
        if (tmpf == 'F')
            tmpf = 0;
        tmpf = (tmpf + roadf[ans]) % 4;
        if (tmpf == 0)
            cout << "N" << endl;
        if (tmpf == 1)
            cout << "E" << endl;
        if (tmpf == 2)
            cout << "S" << endl;
        if (tmpf == 3)
            cout << "W" << endl;
    }
    return 0;
}

E

E 就没仔细看,暂时不在能力范围之内。

F

F 其实有点想像找 NPY 那题一样分几种情况坐标一减排个序就完事,但又是怕 TLE。直接搞了个地图,按照单位时间模拟,脑洞扩散到的就标记一下。然后看技能点坐标有没有被标记。但新标记的脑洞和原有的脑洞还得区分开,又多加了一种标记想着每个单位时间过了再改回来,结果遍历太多次还是得 TLE。

后来 SLF 提示这道题正解的时间复杂度为 O(mn),后来自己优化了一下也 AC 了。依然是按照单位时间模拟,不同的是我们除了维护一个地图之外,又维护了两个队列,分别放置新增标记的横纵坐标,每个单位时间过去,旧的坐标出队,新的坐标入队。地图本身存放脑洞扩赛到每个点的时间。

TLE 代码(1)

#include <bits/stdc++.h>
using namespace std;

int n, m, a, b, mp[502][502], t = 1;
int jnn[502], jnm[502], jnt[502];

void f()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (mp[i][j] == 1)
            {
                if (j + 1 <= m && mp[i][j + 1] != 1)
                    mp[i][j + 1] = 2;
                if (j - 1 >= 1 && mp[i][j - 1] != 1)
                    mp[i][j - 1] = 2;
                if (i - 1 >= 1 && mp[i - 1][j] != 1)
                    mp[i - 1][j] = 2;
                if (i + 1 <= n && mp[i + 1][j] != 1)
                    mp[i + 1][j] = 2;
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (mp[i][j] == 2)
                mp[i][j] = 1;
            // cout << mp[i][j] << " ";
        }
        // cout << endl;
    }

    for (int k = 0; k < b; k++)
    {
        if (mp[jnn[k]][jnm[k]] == 1 && jnt[k] == -1)
        {
            jnt[k] = t;
        }
    }

    t++;
}

int main()
{
    cin >> n >> m >> a >> b;
    memset(mp, 0, sizeof(mp));
    for (int i = 0; i < a; i++)
    {
        int tempm, tempn;
        cin >> tempm >> tempn;
        mp[tempm][tempn] = 1;
    }

    memset(jnt, -1, sizeof(jnt));
    for (int i = 0; i < b; i++)
    {
        cin >> jnn[i] >> jnm[i];
        if (mp[jnn[i]][jnm[i]] == 1)
            jnt[i] = 0;
    }
    while (1)
    {
        int flag = 0;
        for (int i = 0; i < b; i++)
        {
            if (jnt[i] == -1)
            {
                f();
                flag = 1;
            }
        }
        if (flag == 0)
            goto end;
    }
end:
    for (int i = 0; i < b; i++)
    {
        cout << jnt[i] << endl;
    }

    return 0;
}

TLE 代码(2)

#include <bits/stdc++.h>
using namespace std;
int n, m, a, b, bcurrent, mp[502][502], t = 1;
int jnn[502], jnm[502], jnt[502], done = 0;
vector<int> onen, onem;
void mark(int q, int w)
{
    if (q <= n && q > 0 && w <= m && w > 0 && mp[q][w] != 1)
    {
        mp[q][w] = 1;
        onen.push_back(q);
        onem.push_back(w);
    }
}
int main()
{
    cin >> n >> m >> a >> b;
    bcurrent = b;
    memset(mp, 0, sizeof(mp));
    for (int i = 0; i < a; i++)
    {
        int tempm, tempn;
        scanf("%d %d", &tempn, &tempm);
        mark(tempn, tempm);
    }
    memset(jnt, -1, sizeof(jnt));
    for (int i = 0; i < b; i++)
    {
        scanf("%d %d", &jnn[i], &jnm[i]);
        if (mp[jnn[i]][jnm[i]] == 1)
        {
            jnt[i] = 0;
            bcurrent--;
        }
    }
    while (1)
    {
        int big = onen.size();
        for (int k = done; k < big; k++)
        {
            mark(onen[k], onem[k] + 1);
            mark(onen[k], onem[k] - 1);
            mark(onen[k] + 1, onem[k]);
            mark(onen[k] - 1, onem[k]);
        }
        for (int k = 0; k < b; k++)
        {
            if (mp[jnn[k]][jnm[k]] == 1 && jnt[k] == -1)
            {
                jnt[k] = t;
                bcurrent--;
                if (bcurrent == 0)
                {
                    for (int i = 0; i < b; i++)
                        cout << jnt[i] << endl;
                    return 0;
                }
            }
        }
        t++;
        done = big;
    }
    return 0;
}

AC 代码

#include <bits/stdc++.h>
using namespace std;
int n, m, a, b, sum, mp[502][502], t = 0;
int tpn, tpm;
queue<int> onen, onem;
void mark(int q, int w)
{
    if (q <= n && q > 0 && w <= m && w > 0 && mp[q][w] == -1)
    {
        mp[q][w] = t;
        onen.push(q);
        onem.push(w);
    }
}
int main()
{
    cin >> n >> m >> a >> b;
    sum = m + n;
    memset(mp, -1, sizeof(mp));
    for (int i = 0; i < a; i++)
    {
        scanf("%d %d", &tpn, &tpm);
        mark(tpn, tpm);
    }
    while (sum--)
    {
        t++;
        int big = onen.size();
        for (int k = 0; k < big; k++)
        {
            mark(onen.front(), onem.front() + 1);
            mark(onen.front(), onem.front() - 1);
            mark(onen.front() + 1, onem.front());
            mark(onen.front() - 1, onem.front());
            onen.pop();
            onem.pop();
        }
    }
    for (int i = 0; i < b; i++)
    {
        scanf("%d %d", &tpn, &tpm);
        cout << mp[tpn][tpm] << endl;
    }
    return 0;
}

不过惊讶的是至少这五题都没有很劝退... 每次看洛谷月赛点开一题,哦是考树形数据结构的,就下一题下一题了...

按去年的情况是 5-12 名?今年三个年级神犇混战怕是凉凉...

最后修改:2019 年 11 月 20 日 05 : 09 PM
如果觉得我的文章对你有用,请随意赞赏