2021 蓝桥杯热身赛 & 天梯赛选拔赛题解

你好天梯(5分)

Prepared by : Pony

题意:

给出不超过 3 个字符串,排序输出。

解题思路:

简单签到题,排序或手动比较均可。

简单提一下有同学出现的问题,就是字符数组开的不够大,对于长度为 n 的字符串来说,字符数组至少要开到 char[n+1] ,只开 char[n] 的数字的话会爆掉。

有同学没用排序,仅用 if-else 语句来做这道题的话,要注意能否包含到所有情况。

对于 strcmp 这个函数, C 语言只规定了参数 1 大于参数 2 返回正数,参数 1 小于参数 2 返回负数。所以对于不同的编译器,当参数 1 大于参数 2 只保证返回正数,并不保证一定返回 1 ,同样的,参数1小于参数 2 时也不一定返回 -1

代码如下:

#include<bits/stdc++.h>
using namespace std;
int main()
{

    int n;
    cin>>n;
    string s[10];
    for(int i=0;i<n;i++)cin>>s[i];//输入
    sort(s,s+n);//排序
    for(int i=0;i<n;i++)cout<<s[i]<<endl;//输出
    return 0;
}

乖乖站好(10分)

Prepared by : Pony

题意:

给定若干个数字 1,2,12,21 ,可以将部分或全部连接起来,要求相邻两个数字不能相同,求能连成数字段的最长长度。

解题思路:

为了解释方便,设组合 1,2,12,21 的数量分别为 a,b,c,d

首先如果 a,b 都为 0 的话,组合 12,21 就不能连在一起,那答案就是 max(2\times c,2\times d)

否则如果 a,b 数量相等的话,所有人都可以排上队,那答案就是 a+b+2\times c+2\times d

发现由于要求同性不能站在一起,所以排成的队伍之间的男女数量最多相差1,所以其他情况,即 ab 相差大于等于 1 时,答案就是 2\times min(a,b)+1+2\times c+2\times d

注意事项:

未考虑到所有情况,或者全 0 ,部分 0 之类的特例。

代码如下:

#include<bits/stdc++.h>
using namespace std;
int main()
{

    int a,b,c,d;
    cin>>a>>b>>c>>d;
    //情况一
    if(a==0&&b==0)
    {
        cout<<max(2*c,2*d);
    }
    //情况二
    else if(a==b)
    {
        cout<<a+b+2*c+2*d;
    }
    //否则
    else
    {
        cout<<2*min(a,b)+1+2*c+2*d;
    }
    return 0;
}

伟大的新概念(10分)

Prepared by : Daniel

题意:

给定两个整数 l, r ,找出 [l,r] 之间的回文质数

解题思路:

数据范围比较小,直接枚举 [l,r] 即可所有数,判断其是否为质数,是否为回文即可。

思考:

如果数据范围开到 10^8 应该怎么做呢?

代码如下:

#include <iostream>
#include <algorithm>

using namespace std;

int l, r;

// 判断是否为质数
bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}

// 判断是否为回文
bool is_palindrome(int x)
{
    string s;
    while (x)
    {
        s += (char)(x % 10 + '0');
        x /= 10;
    }
    string t = s;
    reverse(t.begin(), t.end());
    return s == t;
}

int main()
{
    cin >> l >> r;
    while (l <= r) 
    {
        if (is_prime(l) && is_palindrome(l)) cout << l << '\n';
        l ++ ;
    }
    return 0;
}

调整缩进(15分)

Prepared by : Pony

题意:

给定若干行字符,每次遇到一对 beginend ,就将它们以及它们中间的所有行缩进两个空格。

解题思路:

首先要说声抱歉,因为数据出锅了,现场改数据,不过幸好是 IOI 赛制,不是 ACM 赛制,影响没这么大。

首先对于一行来说,除了前面的空格多少,是不需要改其他东西,原样输出就行,所以对于以下一行字符(字符中间有空格):

a a a a

应该输出:

a a a a

而不是:

a

a

a

a

因此为了处理方便,读入字符串的时候推荐整行读入。

此外,没有仔细理解样例,每行开始的空格应该直接忽略掉,只输出当前需要缩进的空格。

代码如下:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int suojin=0;
    string str;
    while(getline(cin,str))//输入
    {
        int len=str.length();
        bool firb=1;
        for(int i=0;i<len;i++)
        {
            if(firb)//消前置空格,为缩进添加空格和判断begin和end
            {
                while(str[i]==' ')i++;
                if(i+5==len&&str.substr(i,5)=="begin")
                {
                    suojin+=2;
                }
                for(int j=0;j<suojin;j++)cout<<' ';
                if(i+3==len&&str.substr(i,3)=="end")
                {
                    suojin-=2;
                }
                firb=0;
            }
            cout<<str[i];
        }
        cout<<endl;
//    }

    }
}

破解序列锁(15分)

Prepared by : Daniel

题意:

给定一个序列,最多只有三种数,每次操作可以调换任意两个数的位置,问最少操作多少次,可以使得序列变为非降序。

解题思路:

首先统计最小值的个数 cnt1 ,次小值个数 cnt2 ,最大值个数 cnt3

枚举 [1,cnt1] 位置,若当前数 a_i 不为最小值,那么这个数一定要进行交换,且这个位置应该得到最小值,分两种情况:

  • 如果 a_i 为最大值,它最后应该放在 [n-cnt3+1,n] 的某个位置上,若这些位置现在存在一个最小值,那么可以直接换过来,因此应该从后往前找。
  • 如果 a_i 为次小值,它最后应该放在 [cnt1+1,cnt1+cnt2] 的某个位置上,若这些位置现在存在一个最小值,那么可以直接换过来,因此应该从前往后找。

做完以上步骤之后, [1,cnt1] 上全是最小值,因此只需检查 [cnt1+1,cnt1+cnt2] 上的数是否全都是次小值,如果发现某个位置上是最大值,那就需要进行一次交换。

代码如下:

#include <iostream>

using namespace std;

const int N = 1010;

int n;
int a[N];

int main()
{
    cin >> n;
    // 统计出现次数
    int cnt1 = 0, cnt2 = 0, cnt3 = 0;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        if (a[i] < 0) cnt1 ++ ;
        else if (a[i] == 0) cnt2 ++ ;
        else cnt3 ++ ;
    }
    // 将 [1,cnt1] 的位置整理成全为最小值
    int res = 0;
    for (int i = 1; i <= cnt1; i ++ )
        if (a[i] == 0)
        {
            for (int j = cnt1 + 1; j <= n; j ++ )
                if (a[j] < 0)
                {
                    res ++ ;
                    swap(a[i], a[j]);
                    break;
                }
        }
        else if (a[i] > 0)
        {
            for (int j = n; j > cnt1; j -- )
                if (a[j] < 0)
                {
                    res ++ ;
                    swap(a[i], a[j]);
                    break;
                }
        }
    // 检查 [cnt1+1,cnt1+cnt2] 位置是否全为次小值
    for (int i = cnt1 + 1; i <= cnt1 + cnt2; i ++ )
        res += (int)(a[i] != 0);
    cout << res << '\n';
    return 0;
}

植树造林(20分)

Prepared by : Pony

题意:

给定二叉树的前序遍历和后序遍历,求符合条件的二叉树的数量。

解题思路:

对于二叉树来说,前序遍历的顺序是根左右,后序遍历的顺序是左右根。

为了解释方便,我们不妨后序遍历的输出倒过来,那这样对应字符串的遍历顺序就是根右左了。那么对于一个代表根的结点,如果在前序遍历和后序遍历中其后的一个结点是相同的,就代表在输出根结点后,之后无论是先遍历左子树还是右子数,下一个结点是相同的。

而这就表示这个根结点只有一个子树,而这个子树可以作为左子树存在,也可以作为右子树存在,所以遇到这种情况,符合题意的二叉树的数量就要乘 2

可以用递归的思路对每个子树用如上的方式计算,也可以不考虑是否为根结点,直接判断相同结点后是否有相同结点,因为如果相同的是叶子结点,之后是不可能有相同结点的。

方法一:

#include<bits/stdc++.h>
using namespace std;
int qian[100005];
int hou[100005];
int qtip[100005];
int htip[100005];

long long ans=1;

void fen(int qb,int hb,int len)
{
    while(len>0)
    {
        if(qian[qb]==hou[hb])//发现前序遍历和后序遍历对应位置相同时
        {
            ans*=2;
            ans%=1000000007;
        }
        else
        {
            //分治
            fen(qb+1,qtip[qian[qb]]+1,htip[hou[hb]]-qb-1);
            fen(htip[hou[hb]]+1,hb+1,qtip[qian[qb]]-hb-1);
            return;
        }
        qb++;
        hb++;
        len--;
    }
}

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>qian[i];
        htip[qian[i]]=i;//预处理某个结点在前序遍历的对应哪个位置
    }
    for(int i=n-1;i>=0;i--)
    {
        cin>>hou[i];
        qtip[hou[i]]=i;
    }
    fen(1,1,n-1);
    cout<<ans;

    }
}

方法二:

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
const long long M = 1000000007;
int a[N], b[N], pos[N];

int main()
{
	int n;
	cin >> n;
	long long ans = 1;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	for(int i = 0; i < n; i++) {
		cin >> b[i];
		pos[b[i]] = i;//预处理结点在后序遍历的哪个位置
	}
	for(int i = 0; i < n-1; i++) {
		if(a[i+1] == b[pos[a[i]]-1])
			ans = ans * 2 % M;
	}
	cout << ans << endl;
	return 0;
}

破解矩阵锁(20分)

Prepared by : Daniel

题意:

给定两个 n\times n 的矩阵,以及 7 种转换方式:

  1. 将矩阵顺时针旋转 90 度;
  2. 将矩阵顺时针旋转 180 度;
  3. 将矩阵顺时针旋转 270 度;
  4. 将矩阵沿着图片的中间垂直线翻转,使其变为自身的镜像;
  5. 先进行 4 操作,再进行 1\sim 3 的一种操作;
  6. 不作任何改变;
  7. 以上所有方式都无效。

问第一个矩阵通过哪种方式转换到第二个矩阵,如果有多种方式,则输出编号较小的序号。

解题思路:

纯模拟,只要会旋转矩阵以及镜像翻转就行,然后按照序号从小到大顺序转换矩阵,每次转换完检查是否与目标矩阵相同即可。

String数组:

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 15;

int n;

// 将矩阵翻转 90 度
void turn90(vector<string> &g)
{
    vector<string> t = g;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            t[j][n - i - 1] = g[i][j];
    g = t;
}

// 将矩阵镜像翻转
void mirror(vector<string> &g)
{
    vector<string> t = g;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            t[i][j] = g[i][n - j - 1];
    g = t;
}

int main()
{
    cin >> n;
    vector<string> a(n), b(n);
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    for (int i = 0; i < n; i ++ ) cin >> b[i];

    vector<string> g = a;
    turn90(g);
    if (g == b)
    {
        cout << "1\n";
        return 0;
    }
    turn90(g);
    if (g == b)
    {
        cout << "2\n";
        return 0;
    }
    turn90(g);
    if (g == b)
    {
        cout << "3\n";
        return 0;
    }
    turn90(g);
    mirror(g);
    if (g == b)
    {
        cout << "4\n";
        return 0;
    }
    for (int i = 0; i < 3; i ++ )
    {
        turn90(g);
        if (g == b)
        {
            cout << "5\n";
            return 0;
        }
    }
    if (a == b)
    {
        cout << "6\n";
        return 0;
    }
    cout << "7\n";
    return 0;
}

字符数组:

#include <cstring>
#include <iostream>

using namespace std;

const int N = 15;

int n;
char pre[N][N], now[N][N], temp[N][N], g[N][N];

// 将矩阵翻转 90 度
void turn90(char g[][N])
{
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            temp[j][n - i - 1] = g[i][j];
    memcpy(g, temp, sizeof temp);
}

// 将矩阵镜像翻转
void mirror(char g[][N])
{
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            temp[i][j] = g[i][n - j - 1];
    memcpy(g, temp, sizeof temp);
}

bool check(char a[][N], char b[][N])
{
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            if (a[i][j] != b[i][j])
                return false;
    return true;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> pre[i];
    for (int i = 0; i < n; i ++ ) cin >> now[i];

    memcpy(g, pre, sizeof pre);
    turn90(g);
    if (check(g, now))
    {
        cout << "1\n";
        return 0;
    }
    turn90(g);
    if (check(g, now))
    {
        cout << "2\n";
        return 0;
    }
    turn90(g);
    if (check(g, now))
    {
        cout << "3\n";
        return 0;
    }
    turn90(g);
    mirror(g);
    if (check(g, now))
    {
        cout << "4\n";
        return 0;
    }
    for (int i = 0; i < 3; i ++ )
    {
        turn90(g);
        if (check(g, now))
        {
            cout << "5\n";
            return 0;
        }
    }
    if (check(pre, now))
    {
        cout << "6\n";
        return 0;
    }
    cout << "7\n";
    return 0;
}

周游山区(25分)

Prepared by : Daniel

题意:

n 个加油站形成一个环形,第 i 个油站有 p_i 升油,每升油可以使汽车行驶一公里,第 i 个油站和它顺时针下一个油站距离为 d_i

一辆汽车(初始时没有油)从其中一个点出发,每经过一个油站就将油站中所有油都取走(包括起点),问是否能沿着顺时针 逆时针环行一周。

解题思路:

如果暴力枚举每个加油站判断的话可以拿到 10 分的部分分,而正解也有多种方法,以下标程使用的是单调队列优化 DP 。

单调队列是一个常用的数据结构,它的作用主要是求长度为 k 的区间最值。

对于环形问题,为了降低思考难度,可以将其“破环成链”,即将序列转化为两倍,如下图:

以顺时针为例,从 i 点能走到 i+1 点,意味着 p_i\geq d_i ,转换一下就是 (p_i-d_i)\geq 0 。从 i 点能走到 i+2 点,意味着 (p_i-d_i)+(p_{i+1}-d_{i+1})\geq 0 (p_i-d_i)\geq 0

以此类推,从 i 点能顺时针走完一圈,就意味着以下条件同时满足:

  • (p_i-d_i) \geq 0
  • (p_i-d_i)+(p_{i+1}-d_{i+1}) \geq 0
  • \dots
  • (p_i-d_i)+(p_{i+1}-d_{i+1}) \dots + (p_{i+n-2}-d_{i+n-2}) \geq 0
  • (p_i-d_i)+(p_{i+1}-d_{i+1}) \dots + (p_{i+n-1}-d_{i+n-1}) \geq 0

因此就可以求一个 s_i=p_i-d_i 的前缀和来快速判断某段是否大于等于 0

我们可以从上图的最后一个数开始枚举,利用单调队列维护 [i,i+n-1] 的前缀和 最小值 ,如果这个最小值都是大于等于 s_{i-1} 的话,那么 i(1\leq i\leq n) 就满足能走完一圈的条件了。

逆时针也是同样的思路,但是细节要改变一下。

比如从 i 点能走到 i-1 意味着 p_i\geq d_{i-1} ,因此从 i-n 点(也相当于是从 i 点)逆时针走一圈意味着满足以下条件:

  • (p_i-d_{i-1})\geq 0
  • (p_i-d_{i-1})+(p_{i-1}-d_{i-2})\geq 0
  • \dots
  • (p_i-d_{i-1})+(p_{i-1}-d_{i-2})+\dots +(p_{i-n+1}-d_{i-n})\geq 0

因此这时前缀和应该是 s_i=p_i-d_{i-1} ,且因为以上公式的下标计算是减法,从前往后枚举序列会更方便。因此从 i-n 点能够逆时针走一圈的条件就是 s_i 大于等于 [i-n+1,i-1] 的前缀和 最大值

代码如下:

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 2000010;

int n;
int p[N], d[N];
int q[N];
LL s[N];
bool st[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> p[i] >> d[i];

    for (int i = 1; i <= n; i ++ ) s[i] = s[i + n] = p[i] - d[i];
    for (int i = 1; i <= 2 * n; i ++ ) s[i] += s[i - 1];
    int hh = 0, tt = -1;
    for (int i = 2 * n; i; i -- )
    {
        while (hh <= tt && q[hh] - i >= n) hh ++ ;
        while (hh <= tt && s[q[tt]] >= s[i]) tt -- ;
        q[ ++ tt] = i;
        if (i <= n && s[q[hh]] >= s[i - 1]) st[i] = true;
    }

    // 因为会用到 d[1-1] ,为了方便直接将 d[0]=d[n]
    d[0] = d[n];
    for (int i = 1; i <= n; i ++ ) s[i] = s[i + n] = p[i] - d[i - 1];
    for (int i = 1; i <= 2 * n; i ++ ) s[i] += s[i - 1];
    hh = 0, tt = -1;
    for (int i = 1; i <= 2 * n; i ++ )
    {
        while (hh <= tt && i - q[hh] >= n) hh ++ ;
        if (i > n && s[q[hh]] <= s[i]) st[i - n] = true;
        while (hh <= tt && s[q[tt]] <= s[i]) tt -- ;
        q[ ++ tt] = i;
    }
    
    for (int i = 1; i <= n; i ++ ) cout << (st[i] ? "YES\n" : "NO\n");
    return 0;
}

房屋面积(25分)

Prepared by : Daniel

题意:

给定 n 个矩形,求它们的并集形成的多边形周长。

解题思路:

扫描线裸题,而且数据范围并不大,直接暴力做就行。将和平行于 X 轴与平行与 Y 轴的边分开考虑,先求平行于 X 轴的所有边的长度之和,然后将每个矩形的横纵坐标调换,同样的方法就可以求出平行于 Y 轴的所有边的长度之和,二者之和即为所求。

扫描线算法的思路如下(以求平行于 X 轴的所有边的长度之和为例):

  1. 如下图,将所有出现过的 X 轴坐标存下来,在这些坐标上画一条垂线,将矩形分割,横坐标上被分割的每一段的长度为 x_{i+1}-x_i ,红色为分割线,黄色为所求。

  2. 分别处理被分割出来的区间,在 Y 轴上看,将出现在这个区间上的每个矩形的上下纵坐标构成一段线段,然后进行一个区间合并的处理,求出有多少段没有任何重叠的线段,再乘以 X 轴上分割出来的区间长度,因为有上下两条边,因此再乘以 2 。下图以上图的中间部分的区间合并为例,黑色为矩形纵坐标形成的线段。

代码如下:

#include <vector>
#include <iostream>
#include <algorithm>

#define F first
#define S second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 5010, INF = 0x3f3f3f3f;

int n;
struct Rec
{
    PII a, b;
} rec[N];

LL get()
{
    // 找出所有 x 坐标
    vector<int> xs;
    for (int i = 0; i < n; i ++ )
    {
        xs.emplace_back(rec[i].a.F);
        xs.emplace_back(rec[i].b.F);
    }
    sort(xs.begin(), xs.end());
    LL res = 0;
    for (int i = 0; i < xs.size() - 1; i ++ )
    {
        // [l, r] 为 x 轴分割出来的区间
        int l = xs[i], r = xs[i + 1];
        // 在 y 轴上找出所有出现的矩形的竖边
        vector<PII> seg;
        for (int j = 0; j < n; j ++ )
        {
            if (rec[j].a.F <= l && rec[j].b.F >= r)
                seg.emplace_back(rec[j].a.S, rec[j].b.S);
        }
        // 区间合并问题,求区间数
        sort(seg.begin(), seg.end());
        int cnt = 0, L = -INF, R = -INF;
        for (auto [x, y] : seg)
            if (x > R)
            {
                cnt ++ ;
                L = x, R = y;
            }
            else R = max(R, y);
        res += 2LL * cnt * (r - l);
    }
    return res;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        PII a, b;
        cin >> a.F >> a.S >> b.F >> b.S;
        rec[i] = {a, b};
    }
    LL res = get();
    // 将横纵坐标交换
    for (int i = 0; i < n; i ++ )
    {
        swap(rec[i].a.F, rec[i].a.S);
        swap(rec[i].b.F, rec[i].b.S);
    }
    res += get();
    cout << res << '\n';
    return 0;
}

U 型锁(30分)

Prepared by : Pony

题意:

请直接浏览 原题

解题思路:

可以直接用 O(n^3) 的方法暴力算出 b,c ,并且检验是否符合题意,不过要考虑是否爆 long long 或者精度问题。

此外,可以将U型锁对应公式变个形式: y-x^2=bx+c ,然后将点坐标的y坐标统一变为 y-x^2 。这样原来的二次函数就变成了直线形式的一次函数,原来的问题就变成了典型的求上凸包问题了。求上凸包用 O(nlgn) 的方法就可以解决。

代码如下:

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

struct Po
{
    long long x,y;
    Po()
    {

    }
    Po(long long xx,long long yy)
    {
        x=xx;
        y=yy;
    }
    bool operator <(const Po& po)
    {
        if(x==po.x)
        {
            return y>po.y;
        }
        else return x<po.x;
    }
    Po operator -(const Po& a)
    {
        return Po(x-a.x,y-a.y);
    }
    long long operator *(const Po& a)
    {
        return x*a.y-y*a.x;
    }
};
int main()
{
    int n;
    cin>>n;
    long long x,y;
    Po po[1005];
    Po sta[1005];
    for(int i=0;i<n;i++)
    {
        cin>>x>>y;
        po[i]=Po(x,y-x*x);//对y坐标进行处理
    }
    //以下就是求上凸包的方法
    sort(po,po+n);
    int tot=0;
    for(int i=0;i<n;i++)
    {
        if(i>0&&po[i].x!=po[i-1].x||i==0)//避免x坐标相同的情况
        {
            while(tot>1&&Po(sta[tot-1]-sta[tot-2])*Po(po[i]-sta[tot-2])>=0)
            {
                tot--;
            }
            sta[tot++]=po[i];
        }
    }
    cout<<tot-1;
    return 0;
}
6赞

回文质数 范围1~10^8


#include <bits/stdc++.h>

using namespace std;


bool is_prime(int x)
{
    if (x < 2)
        return false;
    for(int i = 2; i <= x / i; ++i)
        if (x % i == 0)
            return false;
    return true;
}

int solve(int l, int r, vector<int>&vc)
{
    int res = 0;
    for(int i = 1; i <= 9; ++i)
    {
        if (l <= i && i <= r && is_prime(i))
            vc.push_back(i);
    }


    for(int j = 1; j < 10000; ++j)
    {
        string s = to_string(j);
        string t = s;
        reverse(t.begin(), t.end());
        int x = stoi(s + t);
        if (l <= x && x <= r && is_prime(x))
            vc.push_back(x);



        for(int k = 0; k <= 9; ++k)
        {
            int x = stoi(s + to_string(k) + t);
            if (l <= x && x <= r && is_prime(x))
                vc.push_back(x);
        }
    }

    return res;
}

int main()
{
    int l, r;
    cin >> l >> r;

    vector<int>vc;
    solve(l, r, vc);
    sort(vc.begin(), vc.end());
    for(int &x : vc)
    {
        cout << x << endl;
    }
    return 0;
}
1赞
粤 ICP 备 2020080455 号