1 solutions
-
0
该题考察的知识点是回文数判断/数字与数字字符串的转换。 本题题意明确,那就是求一个区间内的回文数,且左右两边的数字向中间的数字严格递减。我们单独对某一个数字x进行讨论。 所以我们要做的就是 ①对当前数字x,检查它是否为回文数。这一步C++就是利用取余运算把这个数字倒过来,然后看一下和原来相同与否。Python比较简单,就是强制转化为数字字符串,然后用切片来翻转,然后与原数字字符串比对收看是否相同。这里用了回文数正反都一样的特性。 ②本题的细节所在就是第二步,那就是判断是否符合“峡谷数”单调的定义。这里有一个细节,那就是比如数字"321123"算不算峡谷数?因为考虑到两个1并非严格递增,但是我们仔细读题,发现题目给出的定义为:以数字中最小的一位数字为分界点(如果有多个数字同时最小,那么每个数字都要满足下列规则),这一位数字左边的数字从左到右严格递减,右边的数字从左到右严格递增。那么显然不论我们以哪一个1为分界,除了它本身以外,它的左边是严格单调递减,右边是严格单调递增的。
(方框中的数字为分界)
但是当我们发现中心有大于等于三个相同的数字之后,它就不符合定义了,因为假设是三个,那么我们任选除中间数字以外的两个数字中的一个为分界点,它总会有一边有另外两个相同的数字,而定义说的是任选一个都能能满足严格单调的性质,所以它不符合定义。
而掌握这个细节之后我们可以开始构思代码。
我们假设这个数字已经是回文数了(第一步已经判断了),那么显然我们只需研究这个数字的一半。现在又有两种情况:- 假设原来的数字有偶数位数,说明中间一定有两个相同的数字,C++就用取余运算把末尾(原来数字位数÷2)的长度的数字取出来,比如321123,我们就取末尾3位(123),python可以先转换成字符串然后切片;
- 假设原来的数字是奇数位数,比如32123,那么我们要取末尾(原来数字位数÷2+1)的长度出来,也就是(123),这一步一定也要把中央数字取出来,因为假设我们不取中央数字,就有可能出现问题,如下图
也就是说中央数字比两边数字大,虽然两边是单调的,并且他也是回文数,但它也不是峡谷数。
所以我们一定要把中间数字也截取下来。
现在我们只需要判断单调性即可。如果你是取的右半部分,那么就可以判断是否严格单调递增,否则判断是否严格单调递减,注意自己在实际操作的时候有没有将取出来的数字翻转。 C++核心代码:
bool check_valley(int x)// 检查x是否是回文数 { int c = x, res = 0; while (x)// 翻转数字,并保存在res中 { res *= 10;//先把临时转换结果扩大十倍 res += (x % 10);// 再把末尾数字拼接到临时结果后面 x /= 10;// 删掉末尾数字 } return res == c;// 翻转之后与原数字相等就是回文 } bool check_dsc(int x)// 检查x是否单调递减 { string k = ""; while (x) { k += (x % 10) ^ 48;//个位数字可以通过^48 转换成对应数字字符,并拼接到k后面 x /= 10; }// 把数字转换成对应的数字字符串 for (size_t i = 1; i <= ((k.size() >> 1) - !(k.size() % 2)); ++i) /* size_t是专门表示长度的整数,这里为了防止 类型提升使用size_t(实际上就是unsigned int), 注意到条件中的i <= ((k.size() >> 1) - !(k.size() % 2)),这里做到了根据奇偶性判断要 不要中间位置的数字。没有理解的可以随便举 两个例子,一奇一偶来手动模拟一下。 */ if (k[i] >= k[i - 1]) //我判断的是左边是否严格单调递减 return 0; return 1; } inline void solve() { int ans = 0; for (int i = 2024; i <= 20232024; ++i) {// 检查范围 if (check_valley(i)) {// 检查对称性 if (check_dsc(i)) {// 检查单调性 // cout << i << '\n'; ++ans; } } } cout << ans; }Python参考代码:
def check(i) -> bool: i = i[0: (len(i) >> 1) - (1 if len(i) % 2 == 0 else 0) + 1] #和上面C++的逻辑一样,根据奇偶性截取不同长度 for j in range(1, len(i)): if int(i[j]) >= int(i[j - 1]): return 0 return 1 ans = 0 for i in range(2024, 20232025): i = str(i) if i == i[:: -1]: ans += 1 if check(i) else 0 print(ans)答案是493。
祝大家一发AC
- 1
Information
- ID
- 15245
- Time
- 60000ms
- Memory
- 256MiB
- Difficulty
- 9
- Tags
- # Submissions
- 39
- Accepted
- 3
- Uploaded By