CSDN编程竞赛报名地址：https://edu.csdn.net/contest/detail/32
1. 单链表排序
题目
单链表的节点定义如下（C++）： class Node { public: int element; Node * next; } 实现如下函数：Node * sort(Node * head)，排序以 head 为头结点的单链表，返回排序后列表的 head 节点；只能修改 next 指针，要求时间复杂度和空间复杂度尽可能优化。
解题报告
模拟，排序输出即可
class Solution:
def __init__(self) -> None:
pass
def solution(self, n, arr):
result = sorted(arr)
return [str(_) for _ in result]
if __name__ == "__main__":
n = int(input().strip())
arr = [int(item) for item in input().strip().split()]
sol = Solution()
result = sol.solution(arr)
print(" ".join(result))
2. 合并二叉树
题目
已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。例如： 两颗二叉树是: Tree 1 1 / 3 2 / 5 Tree 2 2 / 1 3 4 7 合并后的树为 3 / 4 5 / 5 4 7
示例1
输入
{1,3,2,5},{2,1,3,#,4,#,7}
返回值
{3,4,5,5,4,#,7}
解题报告
模拟，按顺序相加即可，注意判断 null 的情况
class Solution:
def __init__(self) -> None:
pass
def get(self, x):
if x == 'null':
return 0
return int(x)
def solution(self, n, m, arr1, arr2):
k = min(n, m)
a = []
for i in range(k):
x = self.get(arr1[i])
y = self.get(arr2[i])
a.append(str(x + y))
if n < m:
a += arr2[n:]
elif n > m:
a += arr1[m:]
return a
if __name__ == "__main__":
arr_temp = [int(item) for item in input().strip().split()]
n = int(arr_temp[0])
m = int(arr_temp[1])
arr1 = [item for item in input().strip().split()]
arr2 = [item for item in input().strip().split()]
sol = Solution()
result = sol.solution(n, m, arr1, arr2)
print(" ".join(result))
3. n边形划分
题目
已知存在n多边形， 连接多边形所有对角线。 能形成多少区域。
输入描述：
给定整数n。(1<=n<=1e9)
输出描述：
输出区域数，对1e9+7取模
输入样例：
5
输出样例：
11
解题报告
数学
参考 https://zhuanlan.zhihu.com/p/92069094
n 边形（非正）的完全图有多少条线（不包括边）：
e
(
n
)
=
C
n
2
e(n) = C_n^2
e(n)=Cn2，即 n 个点中取 2 个点连成一线
n 边形（非正）的完全图有多少个点：
V
(
n
)
=
C
n
4
+
n
V(n) = C_n^4 + n
V(n)=Cn4+n，两线交于一点，再加上原来的 n 个点
n 边形（非正）的完全图有多少条边：
E
(
n
)
=
C
n
2
+
2
C
n
4
E(n) = C_n^2 + 2C_n^4
E(n)=Cn2+2Cn4
由欧拉示性数公式，n 边形（非正）的完全图有多少个区域：
F
(
n
)
=
E
(
n
)
−
V
(
n
)
+
2
=
C
n
2
+
C
n
4
−
n
+
2
F(n) = E(n) - V(n) + 2 = C_n^2 + C_n^4 - n + 2
F(n)=E(n)−V(n)+2=Cn2+Cn4−n+2
即
F
(
n
)
=
n
4
−
6
n
3
+
23
n
2
−
42
n
+
48
24
F(n) = \frac{n^4 - 6n^3 + 23n^2 - 42n + 48}{24}
F(n)=24n4−6n3+23n2−42n+48
class Solution:
def __init__(self) -> None:
pass
def solution(self, n):
result = n**4 - 6 * n**3 + 23 * n**2 - 42 * n + 24
return (result // 24) % 1000000007
if __name__ == "__main__":
n = int(input().strip())
sol = Solution()
result = sol.solution(n)
print(result)
4. 开心的金明
题目
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 N 元钱就行”。
今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 N 元。
于是，他把每件物品规定了一个重要度，分为 5 等：用整数 1-5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第 j 件物品的价格为 ##v_[j] ##，重要度为 ##w_[j] ##，共选中了 k 件物品，编号依次为 ##j_1,j_2,…,j_k## ，则所求的总和为： ##v_[j_1] imes w_[j_1]+v_[j_2] imes w_[j_2]+ …+v_[j_k] imes w_[j_k] ##。请你帮助金明设计一个满足要求的购物单。
输入描述：
输入的第1 行，为两个正整数， N m （其中N<30000 ）表示总钱数，m<25 ）为希望购买物品的个数。）
从第2 行到第m+1 行，第j 行给出了编号为j−1 的物品的基本数据，每行有2 个非负整数 v p （其中v 表示该物品的价格(v<=10000) ，p表示该物品的重要度(1 ~5) )
输出描述：
输出只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（）（<100000000）。
输入样例：
10 5
8 2
4 5
3 5
4 3
2 2
输出样例：
39
解题报告
动态规划，背包问题，设 f[i][j] 表示前 i 件物品不超过 n 元时所求总和最大值，则
f[i][j] = max{f[i - 1][j - vector[i][0]] + vector[i][0] * vector[i][1]}，其中 j >= vector[i][0]
答案为 f[N][m]
class Solution:
def __init__(self) -> None:
pass
def solution(self, N, m, vector):
f = [0] * (N + 1)
for x, y in vector:
for j in range(N, x - 1, -1):
f[j] = max(f[j], f[j - x] + x * y)
return f[N]
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(m):
vector.append([int(item) for item in input().strip().split()])
sol = Solution()
result = sol.solution(N, m, vector)
print(result)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
