CSDN编程竞赛报名地址：https://edu.csdn.net/contest/detail/24

1. 圆小艺

题目

最近小艺酱渐渐变成了一个圆滑的形状-球！ ！
小艺酱开始变得喜欢上球！
小艺酱得到n个同心圆。
小艺酱对着n个同心圆进行染色。
相邻的圆范围内不能有相同的颜色。 相隔一层的圆颜色相同。
小艺酱想知道圆最外层的那种颜色全部染了多少？

输入描述：

第一行输入整数n.(1<=n<=1000)表示圆的数量。
第二行输入n个圆的半径。(1<=r<=1000)

输出描述：

输出染色面积，保留小数点后3位。

输入样例：

3
1 2 3

输出样例：

18.849

解题报告

模拟，先从大到小排序，然后遍历累加（偶数次）或累减（奇数次）面积即可

import mathclass Solution:def __init__(self) -> None:passdef solution(self, n, arr):arr = sorted(arr, reverse=True)s = 0for i, a in enumerate(arr):if i % 2 == 0:s += a * aelse:s -= a * aresult = math.pi * sreturn '{:.3f}'.format(result)if __name__ == "__main__":n = int(input().strip())arr = [int(item) for item in input().strip().split()]sol = Solution()result = sol.solution(n, arr)print(result)

2. K皇把妹

题目

存在n个节点， 目标节点在m。
每个节点有自己的权值a。
在权值k内（含k值） 选择一个权值非0节点且与目标节点距离最近。
节点i与节点j的距离为abs(i-j)。

输入描述：

第一行输入整数n,m,k.(1<=n,m,k<=100)
第二行输入n个整数的权值。(1<=a<=1000)

输出描述：

输出最小距离

输入样例：

7 3 50
62 0 0 0 99 33 22

输出样例：

3

解题报告

模拟，遍历判断权值 k 内、非 0 且非目标节点，维护最小值即可

class Solution:def __init__(self) -> None:passdef solution(self, n, m, k, arr):s = n + 1m -= 1for i in range(n):if arr[i] <= k and arr[i] > 0 and i != m:s = min(s, m - i)return sif __name__ == "__main__":arr_temp = [int(item) for item in input().strip().split()]n = int(arr_temp[0])m = int(arr_temp[1])k = int(arr_temp[2])arr = [int(item) for item in input().strip().split()]sol = Solution()result = sol.solution(n, m, k, arr)print(result)

3. 筛选宝物

题目

已知存在n个宝物， 每个宝物都有自己的质量m和价值v， 在考虑选择宝物时只能选择总质量小于等于M的方案， 请问在最优方案下选择宝物， 能获取到最大价值V是多少？

输入描述：

第一行输入宝物的数量n(1 以下n行每行输入两个数m和v（1

输出描述：

输出最优方案下能获取的最大价值V。
说明：

v代表每个宝物自己的价值

m代表每个宝物的质量

V代表最大价值

M代表总质量

输入样例：

5 10
2 3
5 3
4 5
6 2
4 2

输出样例：

10

解题报告

动态规划。经典背包问题

class Solution:def __init__(self) -> None:passdef solution(self, n, M, vector):f = [0 for j in range(M + 1)]for v in vector:for j in range(M, v[0] - 1, -1):f[j] = max(f[j], [j - v[0]] + v[1])return f[M]if __name__ == "__main__":arr_temp = [int(item) for item in input().strip().split()]n = int(arr_temp[0])M = int(arr_temp[1])vector = []for i in range(n):vector.append([int(item) for item in input().strip().split()])sol = Solution()result = sol.solution(n, M, vector)print(result)

4. 圆桌

题目

有N个客人与足够多张的圆桌。 主人安排每位客人坐在一个圆桌边， 但是每位客人希望自己左右边上分别有一些空座位，不然会觉得害羞。 注意， 如果一个客人所在的圆桌只有他一个人， 那么他左边的空座位数量就是他右边的空座位数量。
试问主人需要准备多少个座位， 才能让每个客人舒适的坐下。

输入描述：

第一行输入一个整数N，(1<=N<=10000),代表客人的数量
接下来N行，每行两个整数li与ri，(1<=i<=N,1<=li<=ri<=1000000000)
代表第i位客人希望左边有li个空座位，右边有ri个空座位。

输出描述：

输出一个整数，代表主人需要准备的最少座位数量。

输入样例：

3
1 1
1 1
1 1

输出样例：

6

解题报告

贪心，椅子数最少即尽可能使两人之间公用的座位最多。
故对 l[i] 和 r[i] 分别进行排序，由于每个人本身还需要一个座位，故答案为 n + max{l[i], r[i]}

class Solution:def __init__(self) -> None:passdef solution(self, n, vector):l = sorted([v[0] for v in vector])r = sorted([v[1] for v in vector])s = nfor i in range(n):s += max(l[i], r[i])return sif __name__ == "__main__":n = int(input().strip())vector = []for i in range(n):vector.append([int(item) for item in input().strip().split()])sol = Solution()result = sol.solution(n, vector)print(result)