优化Python代码快4秒

您可以更有效地利用集合操作,特别是子集检查,可以使用issubset()进行改进。

您还可以通过一次读取所有输入并对其进行处理来避免冗余的输入调用。

这样地:

```
notConstraint = set()
mustConstraint = set()
violated = 0
satisfied = 0 

import sys
input = sys.stdin.read
data = input().splitlines()

# Read constraints
index = 0
for i in range(int(data[index])):
    index += 1
    constraint = data[index]
    mustConstraint.add(frozenset(constraint.split()))

index += 1
for i in range(int(data[index])):
    index += 1
    constraint = data[index]
    notConstraint.add(frozenset(constraint.split()))

# Process groups
index += 1
for i in range(int(data[index])):
    index += 1
    group = set(data[index].split())

    for x in mustConstraint:
        if x.issubset(group):
            satisfied += 1
        
    for y in notConstraint:
        if y.issubset(group):
            violated += 1

violated += len(mustConstraint) - satisfied

print(violated)
```

使用sys.stdin.read一次读取所有输入,并将其拆分为行以加快处理速度。 并使用issubset()进行更有效的子集检查。

这减少了迭代次数,并显著提高了性能。

您可以在以下网址找到有关复杂常见操作的更多帮助 Big-O Cheat Sheet . 而且 Python's Time Complexity 很好地解释了Python内置数据类型的性能特征。

祝你好运

两种解决方案,都很容易通过所有测试。

解决方案1:最小变化

将你的大内环替换为该组三对上的小环,即改变

    for x in mustConstraint:
        if x & group == x:
            satisfied +=1
        
    for y in notConstraint:
        if y & group == y:
            violated += 1

对此:

    a, b, c = group
    for pair in {a, b}, {a, c}, {b, c}:
        if pair in mustConstraint:
            satisfied += 1
        if pair in notConstraint:
            violated += 1

解决方案2:只需两组操作

所有三个部分都指定了一组配对。有助于将其转化为函数。然后查找/统计违规行为:

• 必须是但不是的配对。
• 一定不是,而是。

from itertools import combinations

def pairs():
    return {
        frozenset(pair)
        for _ in range(int(input()))
        for pair in combinations(input().split(), 2)
    }

must = pairs()
must_not = pairs()
are = pairs()

print(len(must - are) + len(must_not & are))