第十届蓝桥杯省赛C++B组 迷宫

试题 E：迷宫

本题总分: 15分

[问题描述]

下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可以通行的地方。

1
2
3
4

010000
000100
001001
110000

迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。

对于上面的迷宫，从入口开始，可以按 DRRURRDDD**R 的顺序通过迷宫， 一共 10 步。其中D,U,L,R 分别表示向下、向上、向左、向右走。

对于下面这个更复杂的迷宫（30 行50 列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。 请注意在字典序中D<L<R<U。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

01010101001011001001010110010110100100001000101010
00001001100000101010010000100000001001100110100101
01001011010010001000001101001011100011000000010000
01000000011010100011010000101000001010101011001011
00011111000001101000010010100010100000101100000000
10001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000000110101010111110011000010000111010
00111000001010100001100010000001000101000000001001
11000110100111110010001001010101010101011001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011001001
10000000101100010000101100101101001011111110000100
10101001000000010100100001000100000100011100101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001010110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110101001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001111100000
00111100001000010000000110111000000001000000000011
10000001100111010111010001000111111110001101111000

第九届蓝桥杯 试题D：第几个幸运数

试题 D：第几个幸运数

本题总分: 10分

[问题描述]

到 x 星球旅行的游客都被发给一个整数，作为游客编号。

x 星的国王有个怪癖，他只喜欢数字 3,5 和 7。

国王规定，游客的编号如果只含有因子：3,5,7 就可以获得一份奖品。 前 10 个幸运数字是： 3 5 7 9 15 21 25 27 35 45 ，因而第 11 个幸运数字是：49

小明领到了一个幸运数字 59084709587505。

去领奖的时候，人家要求他准确说出这是第几个幸运数字，否则领不到奖品。

请你帮小明计算一下，59084709587505 是第几个幸运数字。

消息的传递

我们的郭嘉大大在曹操这过得进遙自在, 但是有一天曹操给了他一个任务，在建邮城内有 N 个袁绍的奸细，将他们从 1 到 N 进行 编号, 同时他们之间存在一种传递关系, 即若 C**i,j=1, 则奸细 i 能将消息直接传递给奸细 j。

现在曹操要发布一个假消息, 需要传达给所有奸细，而我们的郭嘉大大则需要传递给尽量少的奸细使所有的奸细都知道这一个消息, 问我们至少要传给几个奸细?

输入格式:

第一行为 N, 第二行至第 N+1 行为 N×N 的矩阵 ( 若第 I 行第 J 列为 1, 则奸细 I 能将消息直接传递给奸细 J, 若第 I 行第 J 列为 0 , 则奸细 I 不能将消息直接传递给奸细 J) 。

输出格式:

只有一行：即我们的郭嘉大大首先至少要传递的奸细个数。

输入样例:

1
2
3
4
5
6
7
8
9

8
0 0 1 0 0 0 0 0
1 0 0 1 0 0 0 0
0 1 0 1 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 1
0 0 0 0 0 0 1 0

输出样例:

1

2

数据范围与提示

N≤1000

洛谷P1464 Function

题目描述

对于一个递归函数w(a,b,c)w(a,b,c)

• 如果a \le 0a≤0 or b \le 0b≤0 or c \le 0c≤0就返回值11.
• 如果a>20a>20 or b>20b>20 or c>20c>20就返回w(20,20,20)w(20,20,20)
• 如果a<ba<b并且b<cb<c 就返回w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)w(a,b,c−1)+w(a,b−1,c−1)−w(a,b−1,c)
• 其它的情况就返回w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)w(a−1,b,c)+w(a−1,b−1,c)+w(a−1,b,c−1)−w(a−1,b−1,c−1)

这是个简单的递归函数，但实现起来可能会有些问题。当a,b,ca,b,c均为15时，调用的次数将非常的多。你要想个办法才行.

absi2011 : 比如 w(30,-1,0)w(30,−1,0)既满足条件1又满足条件2 这种时候我们就按最上面的条件来算 所以答案为1

输入格式

会有若干行。

并以-1,-1,-1−1,−1,−1结束。

保证输入的数在[-9223372036854775808,9223372036854775807][−9223372036854775808,9223372036854775807]之间，并且是整数。

输出格式

输出若干行，每一行格式：

1

w(a, b, c) = ans

注意空格。

题目描述

棋盘上 AA 点有一个过河卒，需要走到目标 BB 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 CC 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，AA 点 (0,0)(0,0)、BB 点 (n,m)(n,m)，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 AA 点能够到达 BB 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

输入格式

一行四个正整数，分别表示 BB 点坐标和马的坐标。

输出格式

一个整数，表示所有的路径条数。

题目背景

kkksc03 的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。

题目描述

这次期末考试，kkksc03 需要考 44 科。因此要开始刷习题集，每科都有一个习题集，分别有 s1,s2,s3,s4s1,s2,s3,s4 道题目，完成每道题目需要一些时间，可能不等（A1,A2,…,As1A1,A2,…,A**s1，B1,B2,…,Bs2B1,B2,…,B**s2，C1,C2,…,Cs3C1,C2,…,C**s3，D1,D2,…,Ds4D1,D2,…,D**s4）。

kkksc03 有一个能力，他的左右两个大脑可以同时计算 22 道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。

由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。

洛谷 p1249 最大乘积

题目大意

将N分解成若干个互不相同数字之和，求乘积的最大值。

思路

利用 lna + lnb = ln(a + b)，将乘积的最大值转换为和的最大值。题目就可以化解为，从1, 2, 3…n中选出一些数是他们的和最大。

相当于是一个01背包问题和一个高精度乘法。

题目描述

一个正整数一般可以分为几个互不相同的自然数的和，如 3=1+23=1+2，4=1+34=1+3，5＝1+4=2+35＝1+4=2+3，6=1+5＝2+46=1+5＝2+4。

现在你的任务是将指定的正整数 nn 分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。

洛谷P1012 [NOIP1998 提高组] 拼数

题目描述

设有 nn 个正整数 a_1 \dots a_na1…a**n，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。

输入格式

第一行有一个整数，表示数字个数 nn。

第二行有 nn 个整数，表示给出的 nn 个整数 a_ia**i。

输出格式

一个正整数，表示最大的整数

输入输出样例

输入 #1

1
2

3
13 312 343

输出 #1

1

34331213

输入 #2

1
2

4
7 13 4 246

输出 #2

1

7424613

说明/提示

对于全部的测试点，保证 1 \leq n \leq 201≤n≤20，1 \leq a_i \leq 10^91≤a**i≤109。

题目有点脑筋急转的意思，刚开始看到有点无从下手，看了题解后才发现这题目很巧妙。几个数字组成一个最大的数字，就相当于结果的字符串，字典序最大，这样一来就可以用排序做了。

STL的比较函数也很有意思

洛谷P1923 求第k小的数

题目描述

输入 nn(n<5000000n<5000000 且 nn 为奇数) 个数字 a_i(0<a_i<10^9)a**i(0<a**i<109) ，输出这些数字的第 kk 小的数。最小的数是第 0 小。

请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。

洛谷 P5461 赦免战俘

自从选拔赛以来就没怎么认真刷题，总是感觉有点累，有点缺少动力。晚上做了到洛谷的基础题，调了1个多小时。。。

明明是一道很简单的递归题，还做了这么久，挺打击的，感觉自己真的是菜。递归可以说是所有算法的基础中的基础了，如果递归都理解的这么吃力，学习其他算法的困难可想而知，感觉自己还差得远，有点迷茫。

题目背景

借助反作弊系统，一些在月赛有抄袭作弊行为的选手被抓出来了！

题目描述

现有 2^n\times 2^n (n\le10)2n×2n(n≤10) 名作弊者站成一个正方形方阵等候 kkksc03 的发落。kkksc03 决定赦免一些作弊者。他将正方形矩阵均分为 4 个更小的正方形矩阵，每个更小的矩阵的边长是原矩阵的一半。其中左上角那一个矩阵的所有作弊者都将得到赦免，剩下 3 个小矩阵中，每一个矩阵继续分为 4 个更小的矩阵，然后通过同样的方式赦免作弊者……直到矩阵无法再分下去为止。所有没有被赦免的作弊者都将被处以棕名处罚。

给出 nn，请输出每名作弊者的命运，其中 0 代表被赦免，1 代表不被赦免。

题目很简单，但是数据的值很大，需要高精度，c++的话需要自己写一个高精度运算。

题目描述

用高精度计算出 S=1!+2!+3!+⋯+n!S=1!+2!+3!+⋯+n!（n≤50n≤50）。

其中“!”表示阶乘，例如：5!=5×4×3×2×15!=5×4×3×2×1。

输入格式

一个正整数 nn。

输出格式

一个正整数 SS，表示计算结果。

7-1 Is It An AVL Tree (25 point(s))

In computer science, an AVL tree (Georgy Adelson-Velsky and Evgenii Landis’ tree, named after the inventors) is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. (Quoted from wikipedia)

For each given binary search tree, you are supposed to tell if it is an AVL tree.

Input Specification:

Each input file contains several test cases. The first line gives a positive integer K (≤10) which is the total number of cases. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary search tree. The second line gives the preorder traversal sequence of the tree with all the keys being distinct. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in a line “Yes” if the given tree is an AVL tree, or “No” if not.

Sample Input:

1
2
3
4
5
6
7

3
7
50 40 36 48 46 62 77
8
50 40 36 48 46 62 77 88
6
50 40 36 48 46 62

Sample Output:

1
2
3

Yes
No
No

题目给出前序遍历的序列，可以利用这个序列一个一个插入来生成一棵树。之后再逐个计算节点因子判断是否为AVL树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

#include <iostream>
#include <algorithm>
using namespace std;

struct Node
{
    int value;
    Node *Left;
    Node *Right;
    Node(int _value): value(_value), Left(NULL), Right(NULL) {}
};

Node* insert(Node *p, int value);
int getHeight(Node *p);
bool AVLJudge(Node *p);

int main(int argc, const char *argv[])
{
    int K;
    cin >> K;
    while(K--)
    {
        int N;
        cin >> N;
        Node *Tree = NULL;
        for(int i = 0; i < N; i++)
        {
            int tmp;
            cin >> tmp;
            Tree = insert(Tree, tmp);
        }
        cout << (AVLJudge(Tree) ? "Yes" : "No") << endl;
    }

    return 0;
}


Node* insert(Node *p, int value)
{
    if(p == NULL)
        p = new Node(value);
    else
    {
        if(value < p->value)
            p->Left = insert(p->Left, value);
        else
            p->Right = insert(p->Right, value);
    }
    return p;
}


int getHeight(Node *p)
{
    if(p == NULL)
        return 0;
    else
        return max(getHeight(p->Left), getHeight(p->Right)) + 1;
}

bool AVLJudge(Node *p)
{
    if(p == NULL)
        return true;
    else
    {
        if(abs(getHeight(p->Left) - getHeight(p->Right)) > 1)
            return false;
        return AVLJudge(p->Left) && AVLJudge(p->Right);
    }
}

代码参考了https://www.cnblogs.com/littlepage/p/13194704.html

这代码写得挺妙的，每一步都有利用递归。

树结点的插入：

1
2
3
4
5
6
7
8
9
10
11
12
13

Node* insert(Node *p, int value)
{
    if(p == NULL)
        p = new Node(value);
    else
    {
        if(value < p->value)
            p->Left = insert(p->Left, value);
        else
            p->Right = insert(p->Right, value);
    }
    return p;
}

利用函数的返回值来修改原值，避免了修改传入参数导致原值没有被修改。调用时记得要赋值Tree = insert(Tree, tmp);

判断结点：

1
2
3
4
5
6
7
8
9
10
11

bool AVLJudge(Node *p)
{
    if(p == NULL)
        return true;
    else
    {
        if(abs(getHeight(p->Left) - getHeight(p->Right)) > 1)
            return false;
        return AVLJudge(p->Left) && AVLJudge(p->Right);
    }
}

利用了尾递归将判断结果传回。