洛谷 P5728 python
时间: 2023-11-11 17:00:42 浏览: 55
这是一道洛谷的题目,题目描述如下:
给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$,请你求出它的最长上升子序列的长度。
其中 $n\leq 10^5$,$a_i\leq 10^9$。
这是一个经典的动态规划问题,可以使用 $O(n\log n)$ 的时间复杂度解决。具体做法是维护一个数组 $d$,其中 $d_i$ 表示长度为 $i$ 的最长上升子序列的末尾元素的最小值。遍历整个序列,对于每个元素 $a_i$,如果 $a_i$ 大于 $d$ 数组中的最大值,就将其加入 $d$ 数组末尾;否则,在 $d$ 数组中二分查找第一个大于等于 $a_i$ 的元素,并将其替换为 $a_i$。最终,$d$ 数组的长度即为所求的最长上升子序列的长度。
Python 代码如下:
```python
n = int(input())
a = list(map(int, input().split()))
d = [float('inf')] * (n + 1)
d[0] = float('-inf')
for i in range(n):
j = bisect_left(d, a[i])
if d[j-1] < a[i] < d[j]:
d[j] = a[i]
print(bisect_left(d, float('inf')) - 1)
```
其中 `bisect_left` 是 Python 内置的二分查找函数,可以在 `bisect` 模块中找到。
相关问题
洛谷p5728 python
这是一道洛谷的题目,题目描述为:给定一个长度为n的序列a,求其中最长的连续子序列的长度,使得该子序列中任意两个数的差的绝对值都不超过1。
这道题可以使用贪心算法来解决。具体来说,我们可以先将序列a排序,然后从左到右扫描序列,维护当前连续子序列的左右端点l和r,以及当前连续子序列中最小值min_val和最大值max_val。对于当前扫描到的位置i,如果a[i]与min_val和max_val之间的差的绝对值不超过1,则将r右移一位,并更新min_val和max_val;否则,将l右移一位,并重新计算min_val和max_val。在扫描过程中,我们需要记录最长的连续子序列的长度。
下面是Python代码实现:
```python
n = int(input())
a = list(map(int, input().split()))
a.sort()
l, r = 0, 0
min_val, max_val = a[0], a[0]
ans = 1
while r < n:
if a[r] - min_val <= 1 and max_val - a[r] <= 1:
max_val = max(max_val, a[r])
r += 1
ans = max(ans, r - l)
else:
min_val = min(min_val, a[l])
l += 1
print(ans)
```
洛谷p1036python
很抱歉,根据提供的引用内容中没有关于洛谷p1036的Python代码。但是,根据引用和引用中的C++代码,可以将其转换为Python代码。您可以参考以下Python代码实现洛谷p1036的功能:
```python
def isPrime(i):
if i == 2:
return True
for j in range(2, int(i ** 0.5) + 1):
if i % j == 0:
return False
return True
def dfs(start, count, sum):
global ans
if count == k and isPrime(sum):
ans += 1
for i in range(start, n + 1):
dfs(i + 1, count + 1, sum + sz[i])
n, k = map(int, input().split())
sz = list(map(int, input().split()))
ans = 0
dfs(1, 0, 0)
print(ans)
```
```python
def isPrime(x):
if x == 2:
return True
for i in range(2, int(x ** 0.5) + 1):
if x % i == 0:
return False
return True
def cm(k_desc, already_sum, begin, end):
if k_desc == 0:
return isPrime(already_sum)
sum = 0
for i in range(begin, end + 1):
sum += cm(k_desc - 1, already_sum + x[i], i + 1, end)
return sum
n, k = map(int, input().split())
x = list(map(int, input().split()))
print(cm(k, 0, 0, n - 1))
```