对于一个元素为数字1-9的集合A(每个数字的数量不超过4个,集合中元素的数量不超过14个),判断其是否满足如下规则: 集合A可以分割为若干个由3个数字组成的集合Bo...Bn和一个由2个数字组成的集合C。其中Bo...Bn需要满足每个集合中的数字均相等或者依次递增一(例如5 5 5以及4 5 6均满足条件);C中的两个数字相等 显然,当集合中的元素个数等于3n+2(n=0,1..4)时才有可能满足上述条件,我们将元素个数不为3n+2的集合称为“相公”的集合,满足上述条件的集合称为能够“胡”的集合,否则则是“不胡”的集合, 输入的每一行包括一组测试数据,测试数据的开头为0表示测试结束;每一组数据由若干个1-9的数字组成,数字之间用空格隔开。每一行输出对应一行输入的结果,对于“相公”的集合输出“XIANGGONG”;对于满足“胡”的集合,输出“HU”;否则输出“BUHU”
时间: 2024-03-12 22:49:37 浏览: 145
以下是使用C++编写的解法:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool is_hu(vector<int>& nums) {
int n = nums.size();
if (n % 3 != 2) { // 不是3n+2个数字
return false;
}
sort(nums.begin(), nums.end()); // 排序
int i = 0;
while (i < n-2) {
if (nums[i] == nums[i+1] && nums[i+1] == nums[i+2]) { // 找到一组三个相同的数
nums.erase(nums.begin()+i, nums.begin()+i+3); // 从集合中删除这三个数
n -= 3;
i = 0; // 重新从头开始查找
} else if (nums[i]+1 == nums[i+1] && nums[i+1]+1 == nums[i+2]) { // 找到一组递增的数
nums.erase(nums.begin()+i, nums.begin()+i+3);
n -= 3;
i = 0;
} else {
i++;
}
}
if (n == 2 && nums[0] == nums[1]) { // 剩下两个相同的数
return true;
} else {
return false;
}
}
int main() {
int num;
while (cin >> num && num != 0) {
vector<int> nums;
nums.push_back(num);
for (int i = 1; i < 14; i++) {
cin >> num;
nums.push_back(num);
}
bool is_xianggong = true;
for (int i = 1; i <= 9; i++) {
if (count(nums.begin(), nums.end(), i) > 4) { // 每个数字的数量不能超过4个
is_xianggong = false;
break;
}
}
if (is_xianggong) {
cout << "XIANGGONG" << endl;
} else if (is_hu(nums)) {
cout << "HU" << endl;
} else {
cout << "BUHU" << endl;
}
}
return 0;
}
```
对于每组输入的集合,我们先判断是否为“相公”的集合,然后再判断是否为“胡”的集合,最后判断是否为“不胡”的集合。其中,“相公”集合中每个数字的数量不能超过4个,我们可以使用count函数来统计每个数字出现的次数。对于“胡”的集合,我们可以使用贪心的思想,每次找到一组三个相同的数或者一组递增的三个数,然后将这三个数从集合中删除,直到集合中剩下两个相同的数或者为空。如果最终集合中剩下两个相同的数,则说明这是一个“胡”的集合,否则说明这是一个“不胡”的集合。
阅读全文