1 solutions

  • 0
    @ 2024-1-9 14:41:30

    该题考察的知识点是回文数判断/数字与数字字符串的转换。 本题题意明确,那就是求一个区间内的回文数,且左右两边的数字向中间的数字严格递减。我们单独对某一个数字x进行讨论。 所以我们要做的就是 ①对当前数字x,检查它是否为回文数。这一步C++就是利用取余运算把这个数字倒过来,然后看一下和原来相同与否。Python比较简单,就是强制转化为数字字符串,然后用切片来翻转,然后与原数字字符串比对收看是否相同。这里用了回文数正反都一样的特性。 ②本题的细节所在就是第二步,那就是判断是否符合“峡谷数”单调的定义。这里有一个细节,那就是比如数字"321123"算不算峡谷数?因为考虑到两个1并非严格递增,但是我们仔细读题,发现题目给出的定义为:以数字中最小的一位数字为分界点(如果有多个数字同时最小,那么每个数字都要满足下列规则),这一位数字左边的数字从左到右严格递减,右边的数字从左到右严格递增。那么显然不论我们以哪一个1为分界,除了它本身以外,它的左边是严格单调递减,右边是严格单调递增的。image (方框中的数字为分界) 但是当我们发现中心有大于等于三个相同的数字之后,它就不符合定义了,因为假设是三个,那么我们任选除中间数字以外的两个数字中的一个为分界点,它总会有一边有另外两个相同的数字,而定义说的是任选一个都能能满足严格单调的性质,所以它不符合定义。image 而掌握这个细节之后我们可以开始构思代码。 我们假设这个数字已经是回文数了(第一步已经判断了),那么显然我们只需研究这个数字的一半。现在又有两种情况:

    1. 假设原来的数字有偶数位数,说明中间一定有两个相同的数字,C++就用取余运算把末尾(原来数字位数÷2)的长度的数字取出来,比如321123,我们就取末尾3位(123),python可以先转换成字符串然后切片;
    2. 假设原来的数字是奇数位数,比如32123,那么我们要取末尾(原来数字位数÷2+1)的长度出来,也就是(123),这一步一定也要把中央数字取出来,因为假设我们不取中央数字,就有可能出现问题,如下图image 也就是说中央数字比两边数字大,虽然两边是单调的,并且他也是回文数,但它也不是峡谷数。 所以我们一定要把中间数字也截取下来。

    现在我们只需要判断单调性即可。如果你是取的右半部分,那么就可以判断是否严格单调递增,否则判断是否严格单调递减,注意自己在实际操作的时候有没有将取出来的数字翻转。 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