20201008 算法培训

海明校验码

请大家写出算法求出信息码海明码校验过的序列(提示:2^k-1 >= n+k,k为校验码位数,n为信息码位数)

输入描述:

输入一行,只有01组成的字符串代表 Dn - D1

输出描述:

输出一行,为海明码校验过的序列 P(n+k) - P1

示例 1:
输入:

10101011

输出:

101001011111

示例 2:
输入:

1010

输出:

1010010

子序列

来源:牛客网
给定一个小写字母字符串T
求有多少长度为m的小写字母字符串S满足,T是S的一个子序列(不需要连续)

输入描述:

第一行一个字符串T
第二行一个正整数m

输出描述:

输出答案对10^9+7取模的值

示例 1:
输入:

a
2

输出:

51

喝雪碧

来源:第二届蓝桥杯校赛
K个空雪碧罐可以换一罐雪碧。小明手上有N罐雪碧,他最多可以喝几罐雪碧?

输入描述:

输入两个正整数,用空格隔开,代表K和N,且K大于1

输出描述:

一个正整数,代表喝了几罐雪碧

示例 1:
输入:

3 10

输出:

15

算法训练 最小乘积(基本型)

来源:蓝桥杯练习系统
给两组数,各n个。
请调整每组数的排列顺序,使得两组数据相同下标元素对应相乘,然后相加的和最小。要求程序输出这个最小值。

输入描述:

第一个行一个数T表示数据组数。后面每组数据,先读入一个n,接下来两行每行n个数,每个数的绝对值小于等于1000。
n<=8,T<=1000

输出描述:

一个数表示答案。

示例 1:
输入:

2
3
1 3 -5
-2 4 1
5
1 2 3 4 5
1 0 1 0 1

输出:

-25
6

全球变暖

来源:第九届蓝桥杯省赛C++B组 第9题
你有一张某海域NxN像素的照片,"."表示海洋、"#"表示陆地,如下所示:
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。
例如上图中的海域未来会变成如下样子:
.......
.......
.......
.......
....#..
.......
.......
请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。
输入描述:

第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。

输出描述:

一个整数表示答案。

示例 1:
输入:

7
.......
.##....
.##....
....##.
..####.
...###.
.......

输出:

1

堆的计算

来源:第九届蓝桥杯省赛JavaB组 第10题
我们知道包含N个元素的堆可以看成是一棵包含N个节点的完全二叉树。
每个节点有一个权值。对于小根堆来说,父节点的权值一定小于其子节点的权值。
假设N个节点的权值分别是1~N,你能求出一共有多少种不同的小根堆吗?
例如对于N=4有如下3种:
1
/ \
2 3
/
4
1
/ \
3 2
/
4
1
/ \
2 4
/
3

输入描述:

一个整数N。
对于40%的数据,1 <= N <= 1000
对于70%的数据,1 <= N <= 10000
对于100%的数据,1 <= N <= 100000

输出描述:

一个整数表示答案。

示例 1:
输入:

4

输出:

3

解方程

来源:牛客网
给出n个整数和x,请问这n个整数中是否存在三个数a,b,c使得ax^2+bx+c=0,数字可以重复使用。

输入描述:

第一行两个整数n,x
第二行n个整数a[i]表示可以用的数
1 <= n <= 1000, -1000 <= a[i], x <= 1000

输出描述:

YES表示可以
NO表示不可以

示例 1:
输入:

2 1
1 -2

输出:

YES

发表评论

电子邮件地址不会被公开。 必填项已用*标注