物理 算法初赛真题
题目：给定一个长度为 $ n $ 的整数数组，找出其中第 $ k $ 小的元素。
输入格式：
```
第一行包含两个整数 n 和 k。
第二行包含 n 个整数，表示数组元素。
```
输出格式：
```
输出第 k 小的元素。
```
样例输入：
```
5 2
3 1 4 2 5
```
样例输出：
```
2. 贪心算法
题目：有 $ n $ 个任务，每个任务有一个开始时间和结束时间。你只能执行不重叠的任务。求最多可以执行多少个任务。
输入格式：
```
第一行一个整数 n。
接下来 n 行，每行两个整数 s_i, e_i，表示任务 i 的开始和结束时间。
```
输出格式：
```
最大可执行任务数。
```
样例输入：
```
4
1 3
2 4
3 5
4 6
```
样例输出：
```
2
```
动态规划
题目：斐波那契数列定义为：
$$
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)
$$
求 $ F(n) mod 10^9+7 $。
输入格式：
```
一个整数 n (0 ≤ n ≤ 10^6)
```
输出格式：
```
F(n) mod (10^9+7)
```
样例输入：
```
10
```
样例输出：
```
55
```
[
F(n) =
egin{cases}
0 & ext{if } n = 0
1 & ext{if } n = 1
F(n-1) + F(n-2) mod (10^9+7) & ext{otherwise}
end{cases}
递归与分治
题目：给定一个正整数 $ n $，将其分解为若干个正整数之和，要求这些数互不相同。问有多少种不同的分解方式？
输入格式：
```
一个整数 n (1 ≤ n ≤ 100)
```
输出格式：
```
分解方式总数。
```
样例输入：
```
4
```
样例输出：
```
2
```
解释：4 = 1+3 = 4（但4不能拆成不同数的和？注意：4本身是一个数，但“分解”通常指多个数）
实际上，若允许单个数，则 4 是一种；1+3 是另一种 → 共 2 种。
提示
[
ext{dp}[i][j] = ext{用大于等于 } j ext{ 的数划分 } i ext{ 的方案数}
]
图论基础
题目：给定一个无向图，判断是否存在从节点 1 到节点 n 的路径。
输入格式：
```
第一行两个整数 n, m，表示节点数和边数。
接下来 m 行，每行两个整数 u, v，表示一条边。
```
输出格式：
```
如果存在路径，输出 "YES"，否则输出 "NO"。
```
样例输入：
```
4 3
1 2
2 3
3 4
```
样例输出：
```
YES
```
提示：
[
ext{reachable}(1) cap {n} eq emptyset Rightarrow ext{YES}
]/
6. 字符串处理
题目：给定一个字符串 $ s $，判断它是否是回文串（忽略大小写和非字母数字字符）。
输入格式：
```
一行字符串 s（长度 ≤ 1000）
```
输出格式：
```
如果是回文，输出 "YES"，否则 "NO"。
```
样例输入：
```
A man a plan a canal Panama
```
样例输出：
```
YES
```
共1条回复
时间正序