主页 / 问题 / 1605575
Accepted
Stanislav Volodarskiy
Asked:2025-01-26 01:36:23 +0000 UTC2025-01-26 01:36:23 +0000 UTC

以零分隔的数字对的数量

  • 772

给出了n 个非负整数的序列。需要计算序列中元素对的数量：

  • 该对中的第一个元素位于第二个元素之前的序列中，
  • 两个元素都是正的，
  • 它们的和是偶数，
  • 序列中它们之间至少有一个零。

输入数据：
第一行包含一个非负整数n——序列中的数字的数量。接下来的n行包含序列中包含的数字，每行一个。

输出数据：
程序应该输出一个数字——找到的对的数量。

输入数据示例：

11
1
2
3
0
4
5
6
0
7
8
9

示例输出：

13

解决方案的示例。它很慢，我们需要更快地解决它：

n = int(input())
a = [int(input()) for _ in range(n)]

c = 0
for i in range(n):
    if a[i] > 0:
        for j in range(i, n):
            if a[j] > 0 and (a[i] + a[j]) % 2 == 0:
                if any(a[k] == 0 for k in range(i + 1, j)):
                    c += 1
print(c)
python

1 个回答

  1. Best Answer

    我们将记住直到最后一个零以及其后的偶数和奇数的数量。

    如果遇到零，那么我们将“之后”计数器转移到“之前”。

    如果是偶数，则我们将等于偶数个数的对数相加，直到最后一个零，对于奇数也类似。

    1 2 3 0 4 5 6 0 7 8 9
            ^           здесь счётчик чётных "до" равен 1, 
                    образуется одна новая пара с двойкой, четвёрка не учитывается.

    同时我们增加相应的。 “之后” 计数器。

    c = 0
n = int(input())
counts_after_zero = [0, 0]
counts_before_zero = [0, 0]

for _ in range(n):
    x = int(input())
    if x > 0:
        c += counts_before_zero[x%2]
        counts_after_zero[x%2] += 1
    else:
        counts_before_zero[0] += counts_after_zero[0]
        counts_before_zero[1] += counts_after_zero[1]
        counts_after_zero = [0, 0]

print(c)
    • 2

相关问题