题解 | #数字的情绪#
题目链接
题目描述
给定一个正整数 n，设其十进制表示中出现过的数字集合为 S。我们按照下面的规则将 n 划分为三种情绪：
- 开心数 (H): 若存在某些
d属于S使得n % d == 0，且存在某些d'属于S使得n % d' != 0。 - 沮丧数 (S): 若对所有
d属于S，均有n % d != 0。 - 极棒数 (G): 若对所有
d属于S，均有n % d == 0。
解题思路
这是一个根据数字自身属性进行分类的问题。解题的核心在于提取出给定数字 n 的所有不同的非零数字，然后逐一检查 n 是否能被这些数字整除，最后根据整除情况进行分类。
-
提取数字：
- 最简便的方法是将数字
n转换为字符串。 - 遍历字符串的每一个字符，并将其转换回数字。
- 为了处理重复的数字（例如 224），我们可以使用一个集合（Set）来存储所有出现过的非零数字，这样可以自动去重。
- 最简便的方法是将数字
-
分类判断：
- 初始化两个布尔标志位：
can_divide(记录是否存在可整除的数字) 和cannot_divide(记录是否存在不可整除的数字)，初始值都设为false。 - 遍历集合中的每一个数字
d：- 如果
n % d == 0，则将can_divide设为true。 - 如果
n % d != 0，则将cannot_divide设为true。
- 如果
- 初始化两个布尔标志位：
-
输出结果：
- 遍历集合中的所有数字后，根据两个标志位的最终状态来判断情绪类型：
- 如果
can_divide和cannot_divide都为true，说明既有能整除的数字，也有不能整除的，是开心数 (H)。 - 如果
can_divide为true而cannot_divide为false，说明所有数字都能整除，是极棒数 (G)。 - 如果
can_divide为false而cannot_divide为true，说明所有数字都不能整除，是沮丧数 (S)。
- 如果
- 一个正整数至少有一个非零数字，所以
can_divide和cannot_divide不可能同时为false。
- 遍历集合中的所有数字后，根据两个标志位的最终状态来判断情绪类型：
代码
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <set>
using namespace std;
void solve() {
long long n;
cin >> n;
string s = to_string(n);
set<int> digits;
for (char c : s) {
digits.insert(c - '0');
}
if (digits.empty()) {
return;
}
bool can_divide = false;
bool cannot_divide = false;
for (int d : digits) {
if (d == 0) {
can_divide = true;
continue;
}
if (n % d == 0) {
can_divide = true;
} else {
cannot_divide = true;
}
}
if (can_divide && cannot_divide) {
cout << "H\n";
} else if (can_divide) {
cout << "G\n";
} else {
cout << "S\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
long n = sc.nextLong();
String s = String.valueOf(n);
Set<Integer> digits = new HashSet<>();
for (char c : s.toCharArray()) {
digits.add(c - '0');
}
if (digits.isEmpty()) {
continue;
}
boolean canDivide = false;
boolean cannotDivide = false;
for (int d : digits) {
if (d == 0) {
canDivide = true;
continue;
}
if (n % d == 0) {
canDivide = true;
} else {
cannotDivide = true;
}
}
if (canDivide && cannotDivide) {
System.out.println("H");
} else if (canDivide) {
System.out.println("G");
} else {
System.out.println("S");
}
}
}
}
t = int(input())
for _ in range(t):
n_str = input()
n = int(n_str)
# 提取所有唯一数字，包括0
digits = {int(d) for d in n_str}
if not digits:
continue
can_divide = False
cannot_divide = False
for d in digits:
# 特殊规则：0总是可整除
if d == 0:
can_divide = True
continue
if n % d == 0:
can_divide = True
else:
cannot_divide = True
if can_divide and cannot_divide:
print("H")
elif can_divide:
print("G")
else: # cannot_divide must be true
print("S")
算法及复杂度
- 算法：模拟、数学
- 时间复杂度：
。对于每个测试用例
n，我们需要遍历它的所有数字。一个数n的位数大约是。提取数字和检查可除性都与位数成正比。
- 空间复杂度：
。我们需要存储
n的非零数字，最多只有 9 个 (1-9)，因此空间复杂度可以视为常数。
