洛谷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代码实现：

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)

相关问题

洛谷 P5728 python

这是一道洛谷的题目，题目描述如下：

给定一个长度为 $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 代码如下：

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` 模块中找到。

洛谷p1036python

很抱歉，根据提供的引用内容中没有关于洛谷p1036的Python代码。但是，根据引用和引用中的C++代码，可以将其转换为Python代码。您可以参考以下Python代码实现洛谷p1036的功能：

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)

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))