111qqz的小窝

老年咸鱼冲锋!

whust #0.2 I Incognito

I
17
Incognito
Spies use attributes to disguise themselves to make sure that
they are not recognized. For example, when putting on sun-
glasses, a spy suddenly looks completely different and cannot
be recognized anymore. Every combination of attributes gives
a different appearance, but not all combinations are possible.
For example, a hat and a turban are both headgear and cannot
be used at the same time. Given the list of available attributes,
compute how many distinct disguises can be made.
Input
On the first line one positive number: the number of test cases,
at most 100. After that per test case:
• one line with an integer n (0 ≤ n ≤ 30): the number of
available attributes.
• n lines with two space-separated strings: the name and
the category of the attribute.
All strings consist of at least 1 and at most 20 lowercase letters. Within a test case all names
are distinct.
Output
Per test case:
• one line with an integer: the number of possible distinct disguises that can be made
with the given attributes, such that at most one attribute from each category is used.
Sample in- and output
Input 
2
3
hat headgear
sunglasses eyewear
turban headgear
3
mask face
sunglasses face
makeup face

Output

5
3

 

数学题.

由于每一种只能最多选一种

那么对于第i类,如果有a[i]个,可能的选择就是a[i]+1 (不选,选1,选2….选a[i]-1,选a[i]),

然后乘法原理,把每一类所有可能的选择数相乘.

但是有一种不满足题意,就是没一类恰好都没选,那么整体就没没选,所以要-1.

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz
粤ICP备18103363