首页 > 试题广场 >

四个选项

[编程题]四个选项

热度指数：6 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

众所周知，高考数学中有一个题目是给出12个单项选择，每一个选择的答案是 A，B，C，D 中的一个。

网上盛传答案存在某种规律，使得蒙对的可能性大大增加。于是今年老师想让你安排这12个题的答案。但是他有一些条件，首先四个选项的数量必须分别为 na，nb，nc，nd。其次有 m 个额外条件，分别给出两个数字 x，y，代表第 x 个题和第 y 个题的答案相同。现在你的老师想知道，有多少种可行的方案安排答案。

输入描述:

第一行五个非负整数na，nb，nc，nd，m，保证na+nb+nc+nd=12，0≤m≤1000。

接下来m行每行两个整数x，y（1≤ x,y ≤12）代表第x个题和第y个题答案必须一样。

输出描述:

仅一行一个整数，代表可行的方案数。

示例1

输入

3 3 3 3 0

输出

算法知识视频讲解

未命名的字符串

发表于 2020-04-10 22:45:49

思路：因为最近在练并查集所以看到这题条件反射想到了并查集，通过并查集可以将答案必须相同的题目绑到一起变成若干组题目，同时可以得到每组题目的数量。显然，如果某选项的总数目小于某组题目的数量，这些题目的数量就不能是这个选项，比如A选项共有3个，而这组答案相同的题目有4题，这些题的答案就肯定不是A了，明白展开全文

Meul

发表于 2020-04-11 01:46:49

题意总共12道题，以A,B,C,D为答案的有na，nb，nc，nd个，且有一些题目答案要一致。思路答案一致想到并查集合并到一起，然后我就很蠢的开始想排列组合了，后来发现排列组合的情况很多，不好写，遂开始思考dp，发现还是不会，这时候瞟了一眼数据，这个数据范围很小，直接暴力模拟利用stl中的ne 展开全文

天色已黄昏

发表于 2020-04-23 00:27:27

我刚开始想了好久，看看能不能想出贪心算法，简单的把这题给解决了，但是可能是我太笨的缘故，我想不到怎么做。然后便试着暴力dfs枚举所有情况，改了一会，果然成功了。思路：题目是要输入a,b,c,d四个选项的数量，然后输入满足条件的数量，输入哪些题目的答案是相同的，输出方案总数。1.在dfs找出所有满足展开全文