2018 蓝桥杯省赛 B 组模拟赛（五）

惨案

理性分析>>盲目乱写

递归求快速幂

藏宝图

题意

蒜头君得到一张藏宝图。藏宝图是一个

整个图只有一个地方可以出入，即是入口也是出口。蒜头君是一个贪心的人，他规划要获得所有宝藏以后才从出口离开。

藏宝图上从一个方格到相邻的上下左右的方格需要

分析

bfs只能算出一个点到另一个点的最短距离

针对这个题，我们不知道宝藏的访问顺序是造成这个问题最大的麻烦

解决这个问题，我们可以将宝藏的访问顺序进行全排列，然后bfs找出相邻点的距离，求和即可

由于bfs找最短距离和全排列在一起，可以n^2预处理出所有的最短距离

蒜头君下棋

题意

分析

分情况暴力

加分二叉树

题意

分析

合并数字

题意

给出

分析

由于每次删除一个数，考虑用栈维护这个过程即可

时间复杂度：由于每个数最多遍历两次，所以 O(n)

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

const int maxn = 1e5+7;

stack<int>q;

int a[maxn];
int n;
int maxx;

int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d", &a[i]);
    }
    q.push(a[1]);
    for(int i=2;i<=n;i++)
    {
        if((!q.empty())&&abs(a[i]-q.top())==1)
        {
            maxx++;
            if(a[i]>q.top())
            {
                continue;
            }
            else
            {
                q.pop();
                i--;
            }
        }
        else
        {
            q.push(a[i]);
        }
    }
    printf("%d",maxx);
    return 0;
}

View Code

蒜头君的数轴

题意

分析

两个线段可以整除的最大距离就是他们的gcd，预处理gcd，枚举不相同线段，去最优即可