2018 蓝桥杯热身赛 (for 16/17) 解题思路参考

以下解题思路仅供参考。

A. WZM 的密文

注意到 a,b 的范围较小,考虑直接枚举 a,b 的值。

如果把 HT 写的 i 个密码记为 p_i ,那么我们只需要验证此时的通项公式是否对于任意整数 1 \leq i \leq t-1 都满足:

p_{i+1}=(a \times (a \times p_i+b) \ \% \ 10001+b) \ \% \ 10001
Code
for (a = 0; a <= 6000; a++)
{
    for (b = 0; b <= 6000; b++)
    {
        flag = 0;
        for (l = 1; l <= n - 1; l++)
        {
            if ((a * ((a * p[l] + b) % 10001) + b) % 10001 != p[l + 1])
            {
                flag = 1;
                break;
            }
        }
        if (flag == 0)
        {
            for (l = 1; l <= n; l++)
                cout << (a * p[l] + b) % 10001 << '\n';
            return;
        }
    }
}

B. LXY 的凑单计划

首先,根据性价比直接贪心是错误的,下面试举一例。

Testcase
5 12
11 300 1
3 80 1
3 80 1
3 80 1
3 80 1

考虑动态规划,分为 X_i=0X_i \neq 0 两种情况讨论,前者就是完全背包问题,后者就是多重背包问题。假设 dp_kk 块钱能给 LXY 的最大满足感,有转移方程:

dp_k = max(dp_k, dp_{k - P_i} + W_i);
Code
for (i = 1; i <= n; i++)
{
    if (X[i] != 0)
    {
        for (j = 1; j <= x[i]; j++)
            for (k = s; k >= p[i]; k--)
                dp[k] = max(dp[k], dp[k - P[i]] + W[i]);
    }
    else
    {
        for (k = p[i]; k <= s; k++)
            dp[k] = max(dp[k], dp[k - P[i]] + W[i]);
    }
}

C. HT 慌了

考虑将字符串首尾相接形成环形序列 s ,假设 s 长度为 l 且恰好有 a 个字符 0b 个子串 00

Code 1
for (i = 0; i < l; i++)
{
    a += (s[i] == '0');
    b += (s[i % l] == '0' && s[(i + 1) % l] == '0');
}

那么:

  • 假设 HT 直接开枪,HT 中枪概率为 \frac{b}{a}
  • 假设 HT 先转轮盘再开枪,HT 中枪概率为 \frac{a}{l}

直接比较两者的值即可。

Code 2
if (a * a > b * l)
    cout << "This is going to panic,the problem is big." << '\n';
else if (a * a < b * l)
    cout << "Don't panic,the problem is not big." << '\n';
else
    cout << "To panic,or not to panic,that is the question." << '\n';

D. HYR 的方向判定

不妨将走第 i 条路时的所面向的方位记做 f_i ,走完前 i 条所花总时间记做 t_i

读入路径的同时,预处理 f,t 两个数组。

下面约定 f_i=0 即面向北, f_i=1 即面向东, f_i=2 即面向南, f_i=3 即面向西。

Code 1
cin >> newf >> newt;
t[i] = t[i - 1] + newt;
f[i] = (f[i - 1] + (newf == 'R') + (newf == 'B') * 2 + (newf == 'L') * 3) % 4;

接下来处理询问,不妨利用 t 数组二分查找所处位置,知道位置自然也就知道方位了。

Code 2
cin >> askf >> askt;
ans = lower_bound(t + 1, t + 1 + n, askt) - t;
askf = ((askf == 'R') + (askf == 'B') * 2 + (askf == 'L') * 3 + f[ans]) % 4;
if (askf == 0) cout << "N" << '\n';
if (askf == 1) cout << "E" << '\n';
if (askf == 2) cout << "S" << '\n';
if (askf == 3) cout << "W" << '\n';

E. CGY 的安排

T 为图 G 的一棵最小生成树,设 L 为树 T 中的一个边权重的有序列表。那么对于图 G 的任何其它最小生成树 T' ,列表 L 也是 T' 中一个边权重的有序列表(证明见《算法导论》练习 23.1-8 )。

这也就意味着,图的最小生成树上的最小边的权值和最大边的权值是固定不变的。

而使用 Kruskal 时,第一次加入的必然是边权最小的边,最小生成树的最大边权又为所有生成树中最小。

故考虑按照边权快排所有边,接下来从图中删除权值最小的若干条边(即枚举最小边),然后跑 Kruskal。

Code 1
ans = INF;
for (i = 0; i < m; i++)
    cin >> edge[i].start >> edge[i].to >> edge[i].val;
sort(edge, edge + m, cmp);
for (i = 0; i < m; i++)
    kruskal(i);
cout << ans == INF ? -1 : ans << '\n';

若存在最小生成树,则尝试更新最优解。

Code 2
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

void kruskal(int i)
{
    minval = INF;
    maxval = -1;
    cnt = 0;
    for (j = 1; j <= n; j++)
        fa[j] = j;
    for (j = i; j < m; j++)
    {
        x = find(edge[j].start);
        y = find(edge[j].to);
        if (x != y)
        {
            fa[x] = y;
            minval = min(minval, edge[j].val);
            maxval = max(maxval, edge[j].val);
            cnt++;
        }
        if (cnt == n - 1)
        {
            ans = min(ans, maxval - minval);
            return;
        }
    }
}

F. 小苏的智力开发

广度优先搜索即可。

Code
while (!q.empty())
{
    a = q.front();
    q.pop();
    for (i = 0; i < 4; i++)
    {
        tx = a.first + dx[i];
        ty = a.second + dy[i];
        if (1 <= tx && tx <= n && 1 <= ty && ty <= m && G[tx][ty] == INF)
        {
            G[tx][ty] = G[x][y] + 1;
            q.push(make_pair(tx, ty));
        }
    }
}
粤 ICP 备 2020080455 号