洛谷基础题练习2

1. 最长连号

题目描述

输入长度为 n 的一个正整数序列，要求输出序列中最长连号的长度。

连号指在序列中，从小到大的连续自然数。

输入格式

第一行，一个整数 n（1 ≤ n ≤ 10⁴）。

第二行，n 个整数 a_i（1 ≤ a_i ≤ 10⁹），之间用空格隔开。

输出格式

一个数，最长连号的个数。

样例输入

10
1 5 6 2 3 4 5 6 8 9
1
2

样例输出

5
1

class Solution:
    def __init__(self) -> None:
        pass

    def solution(self, n, arr):
        ans = 0
        for i in range(n-1):
            count = 1
            for j in range(i+1, n):
                if arr[j] == (arr[j - 1] + 1):
                    count += 1
                else:
                    break
            ans = max(ans, count)
        return ans


if __name__ == "__main__":
    n = int(input().strip())
    arr = [int(item) for item in input().strip().split()]
    s = Solution()
    result = s.solution(n, arr)
    print(result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2. 梦中的统计

题目描述

Bessie 的大脑反应灵敏，仿佛真实地看到了她数过的一个又一个数。她开始注意每一个数码（0~ 9）：每一个数码在计数的过程中出现过多少次？

给出两个整数 M 和 N，求在序列 [M, M + 1, M + 2, …, N - 1, N] 中每一个数码出现了多少次。

输入格式

第 1 行: 两个用空格分开的整数 M 和 N（1 ≤ M ≤ N ≤ 2×10⁹，N −M ≤ 5×10⁵）。

输出格式

第 1 行: 十个用空格分开的整数，分别表示数码 0 ~ 9 在序列中出现的次数。

样例输入

129 137
1

样例输出

1 10 2 9 1 1 1 1 0 1
1

m, n = map(int, input().strip().split())
dict_nums = {str(i): 0 for i in range(10)}
for num in range(m, n+1):
    for i in str(num):
        dict_nums[i] += 1
# print(dict_nums)
print(' '.join(map(str, list(dict_nums.values()))))
1
2
3
4
5
6
7

3. 买铅笔

题目描述

P 老师需要去商店买 n 支铅笔作为小朋友们参加 NOIP 的礼物。她发现商店一共有 3 种包装的铅笔，不同包装内的铅笔数量有可能不同，价格也有可能不同。为了公平起 见，P 老师决定只买同一种包装的铅笔。

商店不允许将铅笔的包装拆开，因此 P 老师可能需要购买超过 n 支铅笔才够给小朋友们发礼物。

现在 P 老师想知道，在商店每种包装的数量都足够的情况下，要买够至少 n 支铅笔最少需要花费多少钱。

输入格式

第一行包含一个正整数 n，表示需要的铅笔数量。

接下来三行，每行用 2 个正整数描述一种包装的铅笔：其中第 1 个整数表示这种包装内铅笔的数量，第 2 个整数表示这种包装的价格。

保证所有的 7 个数都是不超过 10000 的正整数。

输出格式

1 个整数，表示 P 老师最少需要花费的钱。

样例输入 #1

57
2 2
50 30
30 27
1
2
3
4

样例输出 #1

54
1

样例输入 #2

9998
128 233
128 2333
128 666
1
2
3
4

样例输出 #2

18407
1

样例输入 #3

9999
101 1111
1 9999
1111 9999
1
2
3
4

样例输出 #3

89991
1

import math

n = int(input().strip())
money = []
for i in range(3):
    pens, price = map(int, input().strip().split())
    # 需购买该包装数量：需要购买的数量除以每一包装的数量，结果向上取整
    money.append(math.ceil(n / pens) * price)
print(sorted(money)[0])
1
2
3
4
5
6
7
8
9

4. 凯撒密码

题目描述

蒟蒻虽然忘记密码，但他还记得密码是由一个字符串组成。密码是由原文字符串（由不超过 50 个小写字母组成）中每个字母向后移动 n 位形成的。z 的下一个字母是 a，如此循环。他现在找到了移动前的原文字符串及 n，请你求出密码。

输入格式

第一行：n。第二行：未移动前的一串字母。

输出格式

一行，是此蒟蒻的密码。

样例输入

1
qwe
1
2

样例输出

rxf
1

n = int(input().strip())
str1 = input().strip()
new_str = ""
for i in str1:
    num = (ord(i) - ord('a') + n) % 26 + ord('a')
    new_str += chr(num)

print(new_str)
1
2
3
4
5
6
7
8

5. 计数问题

题目描述

试计算在区间 1 到 n 的所有整数中，数字 x（0 ≤ x ≤ 9）共出现了多少次？例如，在 1 到 11 中，即在 1,2,3,4,5,6,7,8,9,10,11 中，数字 1 出现了 4 次。

输入格式

2个整数 n,x（1 ≤ n ≤ 10⁶，0 ≤ x ≤ 9），之间用一个空格隔开。

输出格式

1 个整数，表示 x 出现的次数。

样例输入

11 1
1

样例输出

4
1

#include 

int main()
{
	int n, x;
	scanf("%d %d", &n, &x);
	int count = 0;
	for (int i=1; i<=n; i++)
	{
		int temp = i;
		while (temp != 0)
		{
			if (temp % 10 == x)
				count++;
			temp /= 10;
		}
	}
	printf("%d", count);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

6. 校门外的树

题目描述

某校大门外长度为 l 的马路上有一排树，每两棵相邻的树之间的间隔都是 1 米。我们可以把马路看成一个数轴，马路的一端在数轴 0 的位置，另一端在 l 的位置；数轴上的每个整数点，即 0,1,2,…,l，都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

输入格式

第一行有两个整数，分别表示马路的长度 l （1 ≤ l ≤ 10⁴）和区域的数目 m（1 ≤ m ≤ 100）。

接下来 m 行，每行两个整数 u, v（0 ≤ u ≤ v ≤ l），表示一个区域的起始点和终止点的坐标。

输出格式

输出一行一个整数，表示将这些树都移走后，马路上剩余的树木数量。

样例输入

500 3
150 300
100 200
470 471
1
2
3
4

样例输出

298
1

l, m = map(int, input().strip().split())
list_num = [0 for _ in range(l+1)]
for i in range(m):
    u, v = map(int, input().strip().split())
    for j in range(u, v+1):
        list_num[j] = -1

new_list = [i for i in list_num if i != -1]
print(len(new_list))
1
2
3
4
5
6
7
8
9