集装箱运输货物时，我们必须特别小心，不能把不相容的货物装在一只箱子里。比如氧化剂绝对不能跟易燃液体同箱，否则很容易造成爆炸。

本题给定一张不相容物品的清单，需要你检查每一张集装箱货品清单，判断它们是否能装在同一只箱子里。

输入格式：

输入第一行给出两个正整数：N (≤104) 是成对的不相容物品的对数；M (≤100) 是集装箱货品清单的单数。

随后数据分两大块给出。第一块有 N 行，每行给出一对不相容的物品。第二块有 M 行，每行给出一箱货物的清单，格式如下：

K G[1] G[2] ... G[K]

其中 K (≤1000) 是物品件数，G[i] 是物品的编号。简单起见，每件物品用一个 5 位数的编号代表。两个数字之间用空格分隔。

输出格式：

对每箱货物清单，判断是否可以安全运输。如果没有不相容物品，则在一行中输出 Yes，否则输出 No。

输入样例：

6 3
20001 20002
20003 20004
20005 20006
20003 20001
20005 20004
20004 20006
4 00001 20004 00002 20003
5 98823 20002 20003 20006 10010
3 12345 67890 23333

输出样例：

No
Yes
Yes

编程语言：Python

解题思想：

PAT的题解到目前为止，很明显的感觉到时间复杂度是非常重要的因素，与CCF-CSP有明显不同，CCF-CSP会给定足够长的时间，即使是比较差的算法也可以满分通过。但是PAT并不会针对不同语言设定不同的时间限制，所以使用Python解题，就要尽可能降低时间复杂度，但仍然会有部分题必须改用别的语言才能通过时间限制

1.创建字典，用来存放不相容的货物，其中一个键可以对应多个值，所以用列表来存放值

2.遍历每次输入的货物清单，判断是否存在对应的键，如果存在，再判断该键对应的值是否与整个货物清单有交集

放出之前的代码，代码量差不多，甚至思路更清晰，但是最后一个测试点超时

N, M = map(int, input().split())
Incompatible = [['0', '0'] for i in range(N)]  # 创建不相容列表，存放每一对不相容的物品
 
for i in range(N):
    Incompatible[i] = list(input().split())
 
for i in range(M):
    Information = set(list(input().split())[1:])
    Judge = True  # 标记该箱货物是否可以安全运输，默认为是
    for j in range(N):  # 遍历不相容列表
        if set(Incompatible[j]).issubset(Information):  # 该清单中存在不相容物品(至少存在一对不相容物品为该清单的子集)
            print("No")
            Judge = False  # 改变标记
            break
    if Judge:
        print("Yes")

时间复杂度：O(N^2)，最坏情况下：10^6

代码如下：

N, M = map(int, input().split())
Incompatible = {}  # 创建不相容字典
 
for i in range(N):
    Information = input().split()
    Incompatible.setdefault(Information[0], []).append(Information[1])  # 以列表的方式存放值，这样一个键就可以对应多个值
 
for i in range(M):
    Information = input().split()[1:]  # 只保留货物清单，剔除最先输入的货物数
    Judge = True  # 标记该箱货物是否可以安全运输，默认为是
    for j in range(len(Information)):  # 遍历货物清单
        if Information[j] in Incompatible:  # 不相容字典中存在该键
            if len(set(Incompatible[Information[j]]).intersection(set(Information))) > 0:  # 该键对应的值与货物清单存在交集
                Judge = False
                print("No")
                break
    if Judge:
        print("Yes")

< >

评论板

共有 12 条评论

fruinly

buy cialis online without a prescription The Working Group noted the inadequate number of animals per group

2023-02-22 17:44 回复
engarma

2 cells per epithelium, n 9 epithelia cialis 5mg

2023-04-22 14:25 回复
louis vuitton outlet online

I just wanted to thank you for the fast service. as they look great. I received them a day earlier than expected. the same as the I will definitely continue to buy from this site. either way I will recommend this site to my friends. Thanks!
louis vuitton outlet online https://www.bestlouisvuittonoutlet.com/

2023-04-30 16:50 回复
louis vuitton outlet

I just wanted to thank you for the fast service. or to they look great. I received them a day earlier than expected. cherish the I will definitely continue to buy from this site. either way I will recommend this site to my friends. Thanks!
louis vuitton outlet https://www.louisvuittonsoutletstore.com/

2023-04-30 19:55 回复
cheap jordan shoes

I just wanted to thank you for the fast service. or else they look great. I received them a day earlier than expected. choose to I will definitely continue to buy from this site. blue jays I will recommend this site to my friends. Thanks!
cheap jordan shoes https://www.realcheapretrojordanshoes.com/

2023-04-30 23:36 回复
louis vuitton outlet sale online

Read reviews and was a little hesitant since I had already inputted my order. in addition but thank god, I had no issues. much received item in a timely matter, they are in new condition. in either case so happy I made the purchase. Will be definitely be purchasing again.
louis vuitton outlet sale online https://www.louisvuittonsoutletonline.com/

2023-05-16 15:15 回复
Preliaf

Notably, the authors 4 found that about half the patients had previous knowledge about the relevance of CYP2D6 genotypes for tamoxifen therapy, with the source of this knowledge being their nurses or clinicians, the medical literature or the general media internet, TV and newspapers buy levitra

2023-05-25 11:18 回复
Preliaf

Furthermore, studies comparing higher and lower doses of initial treatment demonstrated that by using the higher doses, no difference in the outcomes of patients with severe and moderate CH is detectable emla cream and priligy tablets

2023-06-06 11:37 回复
vintage gucci bags ebay

Genuine leather label logos all have their own characteristics, so you can remember them.

2023-06-10 19:15 回复
cheap air jordans online

Cheap Jordans 12 The Master

2023-06-10 19:45 回复
handbags from gucci

NO.1Gucci GG Marmont mini ￥6900 This GG Marmont series mini handbag is the maximum capacity among all minis. The body of the bag is made of quilted leather, the version is soft and firm, and there are the iconic double G elements of this series, not only the high usage rate of going out, but also the unique white is also very fashionable.

2023-06-13 19:01 回复
cheap air jordans

$ 86.18 Cheap Jordans XI (11) Retro Space Jam

2023-06-15 07:14 回复

PAT乙级:1090 危险品装箱