2018年蓝桥杯校内题选讲

|

第2题 矩形面积交，第3题 最小公倍数，第4题 打水问题, 第5题 密码发生器, 第7题 学霸的迷宫

作者：肖锐、吴兆恒

第2题 矩形面积交

问题描述

平面上有两个矩形，它们的边平行于直角坐标系的X轴或Y轴。对于每个矩形，我们给出它的一对相对顶点的坐标，请你编程算出两个矩形的交的面积。

输入格式
输入仅包含两行，每行描述一个矩形。
在每行中，给出矩形的一对相对顶点的坐标，每个点的坐标都用两个绝对值不超过10^7的实数表示。

输出格式
输出仅包含一个实数，为交的面积，保留到小数后两位。

样例输入
1 1 3 3
2 2 4 4

样例输出
1.00
`
题目可提交于HDU2056 Rectangles

解法1

可以看出，两个矩形交叉的部分（如果有）也是一个矩形，只需要知道交叉部分矩形的长和宽，就可以求出交叉部分的面积了。给出的8个数字是两个矩形左下角、右上角共计4个点的坐标，可以用它们求出交叉部分矩形的长和宽。

接着则是求出y和x，那么如何求出y和x呢

现在以求y为例子，我们通过上面的图可以发现，(y2-y1)+(y3-y4)正好等于(y3-y1+y)，于是我们就有

y=(y2-y1)+(y3-y4)-(y3-y1)，因为给出的坐标不确定哪个大哪个小，所以得加上绝对值，于是就有

y=fabs(y2-y1)+fabs(y3-y4)-(y3-y1)。我们可以发现y3为纵坐标中的最大值而y1为纵坐标中的最小值。

通过上面的图，我们发现fabs(y2-y1)+fabs(y3-y4)代表的意义没有变，但是后面不一定是减去y3-y1，而是减去纵坐标中的最大值和纵坐标中的最小值，故有y=fabs(y2-y1)+fabs(y3-y4)-(ymax-ymin)。

x同理。

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
/*
Exe.Time: 31MS
Submit Time: 2018-12-04 17:26:40	
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
    double x[4], y[4];
    double x1, x2, x3, x4, y1, y2, y3, y4;
    while(~scanf("%lf%lf%lf%lf%lf%lf%lf%lf"
         	,&x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4)
    {
        x[0] = x1; x[1] = x2; x[2] = x3; x[3] = x4;
        y[0] = y1; y[1] = y2; y[2] = y3; y[3] = y4;
        sort(x, x + 4);
        sort(y, y + 4);
        double Y = fabs(y2-y1) + fabs(y4-y3) - (y[3]-y[0]);
        double X = fabs(x2-x1) + fabs(x4-x3) - (x[3]-x[0]);
        double ans = Y * X;
        if(Y <= 0 || X <= 0)
            ans = 0.00;
        printf("%0.2lf\n", ans);
    }
    return 0;
}

解法2

手动判断各个矩阵的关系

详情见HDU 2056 Rectangles（计算相交面积）

解法3

暴力枚举各种情况

详情见LeetCode：Rectangle Area - 矩形交叉部分的面积里面的解法2

第3题 最小公倍数

问题描述

为什么1小时有60分钟，而不是100分钟呢？这是历史上的习惯导致。
但也并非纯粹的偶然：60是个优秀的数字，它的因子比较多。事实上，它是1至6的每个数字的倍数。即1,2,3,4,5,6都是可以除尽60。
我们希望寻找到能除尽1至n的的每个数字的最小整数。
不要小看这个数字，它可能十分大，比如n=100, 则该数为：
69720375229712477164533808935312303556800
请编写程序，实现对用户输入的 n （n<100）求出1~n的最小公倍数。
输入格式
输入包含若干行整数：第1行为一个整数m，表示样例的组数；接下来有m行，每行为一个整数n，范围为[1,100],表示求1~n的最小公倍数。
输出格式
输出多行，每行为每个测试用例的最小的公倍数。
样例输入
2
6
10

样例输出
60
2520

两个数的最小公倍数就是不断找到该两个数的公约数并两个数同时除去该两个数，最后该两个数互质；
那么，1到n的最小公倍数，是1到n-1的最小公倍数乘以n的所有素因子中没有被1到n-1包含的素因子。
例如，1到7的最小公倍数是2*3*2*5*7，8=2*2*2,(8中2出现3次，1到7的素因子中只出现2次)那么1到8就是2*3*2*5*7*2

所以，需要将[1, n]的最小公倍数求出，比如6前面如果有2 3就可以用1替代。运用双重循环，如果这个数字可以被前面任意一个数整除，则被替换，后来只需要将这些数字乘起来即可，因为结果会很大，所以我们得用到大数乘法。
现在可以假设模拟一下43*65，假设num数组存储43（因为数字变大顺序是从右到左，故num[0]存储的3），并且乘以13后更新数组。

基本流程是让num每一位去乘以n，然后对结果模10，即取出最后一位，因为有进位，所以将结果/10后就是对于的进位了。
c是代表进位的值


当处理完num时，因为还有进位没有处理完，故还得继续处理进位

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
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 120;
int arr[MAXN];

//初始化，即求出对应的素因子
void init()
{
    for(int i = 1; i <= 101; i++)
        arr[i] = i;
    for(int i = 2; i <= 101; i++)
    {
        for(int j = i + 1; j <= 101; j++)
        {
            if(arr[j] % arr[i] == 0)//能被前面整除时，可以被替代
                arr[j] /= arr[i];
        }
    }
    /*
    for(int i = 1; i <= 101; i++)
        cout << ans[i] << " ";
    */
}
int main()
{
    ios::sync_with_stdio(false);
    init();
    int n;
    while(cin >> n)
    {
        int ans[MAXN] = {0};
        ans[0] = 1;
        for(int i = 2; i <= n; i++)//模拟大数乘法
        {
            int c = 0;
            for(int j = 0; j < i; j++)
            {
                int tmp = ans[j] * arr[i] + c; 
                ans[j] = tmp % 10;
                c = tmp / 10; //进位
            }
        }

        int pos = 0;//因为前面有多余的前导0，故需要找到合适的位置再输出
        for(pos = 100; pos >= 0; pos--)
        {
            if(ans[pos])
                break;
        }
        for(int i = pos; i >= 0; i--) //结果是倒序保存的
           cout << ans[i];
    }
    return 0;
}

第4题 打水问题

题目可提交于XYNUOJ1488

问题描述

　　N个人要打水，有M个水龙头，第i个人打水所需时间为Ti，请安排一个合理的方案使得所有人的等待时间之和尽量小。

输入格式

　　第一行两个正整数N M 接下来一行N个正整数Ti。
　　N,M<=1000，Ti<=1000

输出格式

　　最小的等待时间之和。（不需要输出具体的安排方案）

样例输入

7 3
3 6 1 4 2 5 7

样例输出

11

提示

一种最佳打水方案是，将N个人按照Ti从小到大的顺序依次分配到M个龙头打水。 　　
例如样例中，Ti从小到大排序为1，2，3，4，5，6，7，将他们依次分配到3个龙头，则去龙头一打水的为1，4，7；去龙头二打水的为2,5；去第三个龙头打水的为3,6。 　　
第一个龙头打水的人总等待时间 = 0 + 1 + (1 + 4) = 6 　　
第二个龙头打水的人总等待时间 = 0 + 2 = 2 　　
第三个龙头打水的人总等待时间 = 0 + 3 = 3 　　
所以总的等待时间 = 6 + 2 + 3 = 11

题解

这题只需要把所有人的打水时间排序，然后每个人依次分到每个水龙头. 接着计算时间即可 用一个数组存每个人的打数时间+等待时间. 把所有人的时间加起来即是总时间

下面是无聊写的一大段分析 有兴趣就看 有可能会有说错的地方 有问题请提

根据题目给出第提示可以发现一个规律. 把所有人的打水时间进行一次排序后. 把排序后的每个人按顺序分配给每个水龙头. (这里顺序分配的意思就是 例如有5个人a,b,c,d,e 2个水龙头A,B 并假设5人排序后顺序还是a,b,c,d,e. 那么顺序分配的意思就是 第一个人到A 第二个人到B 接着第三个人又回到A 一个循环直到所有人分配好)

测试发现这样得出的答案是最小等待时间.

不考虑提示. 如果想要M个水龙头 N个人打水等待时间最小. 首先想一下最大时间是怎样算的.

假设 4个人a,b,c,d 打水时间分别为10000,2,3,9999 有1个水龙头

想要算最大时间. 首先已经知道要把所有人放在一个水龙头上. 那么接下来还要怎么做呢. 很明显是把打水时间越长的放越前面. 这样后面的人就要等的越久了.

a d c b 这样的打水顺序

d c b都要等a 于是这里的时间为 T += 10000 * 3

c b 又要等d T += 9999 * 2

b 等c T+= 3

T = 50001

得出想要算最大时间 需要把打水时间越久的人放在越前. 算最小时间于是就是反过来. 因此需要用到的排序

重新整理下 算最小时间 可知顺序为 b c d a

c d a等b T += 2 * 3

d a 等c T += 3 * 2

a等d T += 9999

T = 10011

接下来考虑多个水龙头的情况

如果有多个水龙头的话. 根据前面只有一个水龙头的例子应该可以想出. 打水时间长的人 应该尽量分散到不同到水龙头.

假设还是上面的假设 只是换成两个水龙头

如果要求最小 毫无疑问你最想做的应该就是把9999和10000分开 以成下面这样(竖着看)

1
2
3
4
5
6
水龙头A        水龙头B
b(2)         a(10000)

c(3)

d(9999)

这样的时间T会是

水龙头A = 2*2 + 3 = 7

水龙头B = 0

T = 7

但是好像还不是最优 因为水龙头A有3人 b后面有两人 因此b的时间要算上两倍 而水龙头B上只有1人.

尝试让每个水龙头的人数均匀起来 把c分配到水龙头B

1
2
3
4
水龙头A        水龙头B
b(2)          c(3)

d(9999)       a(10000)

此时的时间T为

水龙头A = 2

水龙头B = 3

T = 5

Code

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int read()
{
    char ch = getchar();
    int f = 1;
    int x = 0;
    while(ch < '0' || ch > '9'){if(ch == '-')f = 0;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return f?x:x*-1;
}
int a[1001];
int b[1001];
int main()  
{  
    int n = read(),m = read();

    for(int i = 0;i < n;i ++)
    {
        a[i] = read();
    }
    
    sort(a,a + n);
    for(int i = 0;i < m;i ++)
    {
        b[i] = a[i];
    }
    for(int i = m;i < n;i ++)
    {
        b[i] = a[i] + b[i - m];
    }

    int sum = 0;
    for(int i = 0;i < n;i ++)
    {
        sum += b[i];
    }

    printf("%d",sum);

    return 0;  
}

第5题 密码发生器

题目可提交于NYOJ519

问题描述

在对银行账户等重要权限设置密码的时候，我们常常遇到这样的烦恼：如果为了好记用生日吧，容易被破解，不安全；如果设置不好记的密码，又担心自己也会忘记；如果写在纸上，担心纸张被别人发现或弄丢了…

这个程序的任务就是把一串拼音字母转换为6位数字（密码）。

我们可以使用任何好记的拼音串(比如名字，王喜明，就写：wangximing)作为输入，程序输出6位数字。

变换的过程如下：

第一步. 把字符串6个一组折叠起来，比如wangximing则变为：

wangxi

ming

第二步. 把所有垂直在同一个位置的字符的ascii码值相加，得出6个数字，如上面的例子，则得出：

228 202 220 206 120 105

第三步. 再把每个数字“缩位”处理：就是把每个位的数字相加，得出的数字如果不是一位数字，就再缩位，直到变成一位数字为止。例如: 228 => 2+2+8=12 => 1+2=3

上面的数字缩位后变为：344836, 这就是程序最终的输出结果！

输入描述

要求程序从键盘输入数据，输入格式为：第一行是一个整数n（0<n<100），表示下边有多少输入行，接下来是n行字符串，就是等待变换的字符串。

输出描述

输出格式为：n行变换后的6位密码。

样例输入

3

zhangfeng

wangximing

jiujingfazi

样例输出

772243

344836

297332

题解

对于这条题目 题意应该很容易明白. 对于大家来说可能难在代码的实现. 其实实现也是很简单的. 下面一步步讲题目的操作实现

  1. “把字符串6个一组折叠起来” 其实这一步可以忽略的. 题目是处理多个字符串. 这里就当做只处理一个了. 首先读入字符串 题目告知字符串是由拼音字母组成 因此不用担心有空格问题. 直接用scanf读字符串即可.
  2. 对于第二步. 相信大部分人卡在第一步上了，总想着怎样把字符串6个6个的折起来. 又或者弄了多个字符串数组. 其实并不用. 要算第二步，其实只需要算字符串的前6个下标. 啥意思呢. 看看下图
  3. 根据上面的方法算出6个数字. 第三步是对每个数字进行缩位处理. 这个嘛 就更加简单了. 可以不断对这个数对10取模和除以10. 得出每一位的数. 然后求出每一位的数字之和就是缩位结果.
  4. 对于答案的输出. 不需要考虑拼接 只需要把每个数的缩位结果依次输出即可.

Code

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
#include <stdio.h>
using namespace std;
int read()
{
	char ch = getchar();
	int f = 1;
	int x = 0;
	while(ch < '0' || ch > '9'){if(ch == '-')f = 0;ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
	return f?x:x*-1;
}
int main()
{
	int n = read();
	for(int l = 0;l < n;l ++)
	{
		string s;
		cin >> s;
		int num[6] = {};
		for(int i = 0;i < 6;i ++)
		{
			int count = 0;
			for(int j = i;j < s.size();j += 6)
			{
				count += s[j];
			}
			num[i] = count;
		}
		
		for(int i = 0;i < 6;i ++)
		{
			int t = num[i];
			while(t / 10 != 0)
			{
				int count = 0;
				int temp = t;
				while(temp > 0)
				{
					count += temp % 10;
					temp /= 10;
				}
				t = count;
			}
			num[i] = t;
			printf("%d",num[i]);
		}
		printf("\n");
	}
	
	return 0;
}

第7题 学霸的迷宫

问题描述

学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰，住在一个城堡里，城堡外面是一个二维的格子迷宫，要进城堡必须得先通过迷宫。因为班长还有妹子要陪，磨刀不误砍柴功，他为了节约时间，从线人那里搞到了迷宫的地图，准备提前计算最短的路线。可是他现在正向妹子解释这件事情，于是就委托你帮他找一条最短的路线。
输入格式
包含若干测试用例，每个测试用例：
第一行两个整数n， m，为迷宫的长宽。 　　
接下来n行，每行m个数，数之间没有间隔，为0或1中的一个。0表示这个格子可以通过，1表示不可以。假设你现在已经在迷宫坐标(1,1)的地方，即左上角，迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证(1,1)，(n,m)可以通过。

输出格式
第一行一个数为需要的最少步数K。
第二行K个字符，每个字符∈{U,D,L,R},分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。
样例输入
3 3
001
100
110

3 3
000
000
000

样例输出
4
RDRD
4
DDRR

数据规模

有20%的数据满足：1<=n,m<=10

有50%的数据满足：1<=n,m<=50

有100%的数据满足：1<=n,m<=500

参考：
http://www.cnblogs.com/chiweiming/p/9406530.html
此题用BFS和DFS都能得出结果，但是用DFS会超时，用BFS一旦找到迷宫出口，即可确定最短径，
而DFS搜索出每一条可达路径，然后需要比较步数才能确定最短路径。
此题需要解决的两个问题：

  1. 字典序列输出
    按照DLRU的访问顺序就能在到达终点时确定字典序最小的最短路径了。
  2. 还原路径
    路径的存储可以另外开辟一个迷宫大小的二维数组，到达每一个点，存储这个点的上一个点到这个点的方向(UDRL其中一个)，这样当到达终点时，可以递归输出最短路径，可以看下图举例。

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/*
Submit Time: 12-07 16:13
Exe.Time: 78ms
Exe.Memory: 15.96MB
*/
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 1100;
int Vis[MAXN][MAXN]; //判断有没有走过了
char Map[MAXN][MAXN]; //步数计数
int Step[MAXN][MAXN];
int Path[MAXN][MAXN];
char str[] = {"DLRU"};

int dir[4][2] = //四个方向,按照字典序
{
    {1,0},
    {0,-1},
    {0,1},
    {-1,0}
};

struct point{
    int x, y; //坐标
}in, out, beg; //入队的值，出队的值，开始的值

int n, m;
int check(int x, int y) //检查边界
{
    if(!Vis[x][y] && x >= 1 && y >= 1 
            && x <= n && y <= m && Map[x][y] != '1')
        return 1;
    return 0;
}

int bfs()
{
    memset(Vis, 0, sizeof(Vis));
    memset(Step, 0, sizeof(Vis));
    Vis[beg.x][beg.y] = 1;  //第一个队列的元素，然后标记为已经访问过了
    Step[beg.x][beg.y] = 0; //还没有开始走，步数为0
    queue<point>q; 
    q.push(beg); //将第一个元素入队
    while(!q.empty())
    {
        out = q.front(); //将第一个元素出队
        q.pop();
        for(int i = 0; i < 4; i++) //四个方向开始走
        {
            in.x = out.x + dir[i][0];
            in.y = out.y + dir[i][1];
            if(check(in.x, in.y))
            {
                Path[in.x][in.y] = i;
                //终点，直接返回步数，因为走到终点，step数组还没有+1，所以要+1
                if(in.x == n && in.y == m)
                    return Step[out.x][out.y] + 1;
                q.push(in);
                Vis[in.x][in.y] = 1;
                Step[in.x][in.y] = Step[out.x][out.y] + 1; //步数累加
            }
        }
    }
    return 0;
}

void printPath(int x, int y) //路径还原
{
    if(x == 1 && y == 1)
        return;
    printPath(x - dir[Path[x][y]][0], y - dir[Path[x][y]][1]);
    printf("%c", str[Path[x][y]]);
}

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        getchar(); //吸收回车符，下面同理
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
                scanf("%c", &Map[i][j]);
            getchar();
        }
        beg.x = 1; //从(1,1)开始
        beg.y = 1;
        printf("%d\n", bfs());
        printPath(n, m);
        printf("\n");
    }
    return 0;
}