学习笔记_25_03_17

P11003 [蓝桥杯 2024 省 Python B] 蓝桥村的真相

题目描述

在风景如画的蓝桥村，$n$ 名村民围坐在一张古老的圆桌旁，参与一场思想
的较量。这些村民，每一位都有着鲜明的身份：要么是誉满乡野的诚实者，要么是无可救药的说谎者。

当会议的钟声敲响，一场关于真理与谬误的辩论随之展开。每位村民轮流发言，编号为 $i$ 的村民提出了这样的断言：坐在他之后的两位村民——也就是
编号 $i + 1$ 和 $i + 2$（注意，编号是环形的，所以如果 $i$ 是最后一个，则 $i + 1$ 是
第一个，以此类推）之中，一个说的是真话，而另一个说的是假话。

在所有摇曳不定的陈述中，有多少真言隐藏在谎言的面纱之后？

请你探索每一种可能的真假排列组合，并计算在所有可能的真假组合中，
说谎者的总数。

输入格式

输入的第一行包含一个整数 $T$，表示每次输入包含 $T$ 组数据。

接下来依次描述 $T$ 组数据。

每个数据一行包含一个整数 $n$，表示村落的人数。

输出格式

输出 $T$ 行，每行包含一个整数，依次表示每组数据的答案。

输入输出样例 #1

输入 #1

2
3
3

输出 #1

6
6

说明/提示

对于 $10\%$ 的评测用例，$T = 1，3 \le n \le 10$。

对于 $40\%$ 的评测用例，$1 \le T \le 10^2，3 \le n \le 3 \times10^3$。

对于所有评测用例，$1 \le T \le 10^5，3 \le n \le 10^{18}$。

样例解释

在样例中，可能的组合有「假，假，假」「真，真，假」「真，假，真」「假，
真，真」，说谎者的总数为 $3 + 1 + 1 + 1 = 6$。

解决方案

和P10900 [蓝桥杯 2024 省 C] 数字诗意类似，这也是一道数据规模巨大无比的题，达到10的18次方。根据笔者截至目前的经验，这种数据规模的题目在蓝桥杯中考察的并不是对时间复杂度的优化，而是暗示这道题目中一定隐藏着某种十分简单的数学规律，足以使得做题家们秒杀。

以此题为例：

不难发现，除了第三种情况之外，其它三种情况均为以一个含有两个1一个0的最小单位进行循环的。即。有三种情况每三位中都有一个说谎话的村民，count = n / 3，而另一种下所有人都在说谎, count = n。

故在题目要求考虑所有情况的情况下，总数为(n / 3) * 3 + n = 2n。

此外，如果串的长度不为3的倍数的时候，例如为1011的时候，按照题目首尾相连的要求，不难发现这个串是不合法的，其它情况同样如此，因此当n不为3的倍数的时候，所有人都是说谎者。

因此，解决代码如下：

t = int(input())
for i in range(t):
    n = int(input())
    if n%3 == 0:
        print(n * 2)
    else:
        print(n)

P11002 [蓝桥杯 2024 省 Python B] 神奇闹钟

题目描述

小蓝发现了一个神奇的闹钟，从纪元时间（$1970$ 年 $1$ 月 $1$ 日 $00:00:00$）开始，每经过 $x$ 分钟，这个闹钟便会触发一次闹铃（纪元时间也会响铃）。这引起了小蓝的兴趣，他想要好好研究下这个闹钟。

对于给出的任意一个格式为 yyyy-MM-dd HH:mm:ss 的时间，小蓝想要知道在这个时间点之前（包含这个时间点）的最近的一次闹铃时间是哪个时间？

注意，你不必考虑时区问题。

输入格式

输入的第一行包含一个整数 $T$，表示每次输入包含 $T$ 组数据。

接下来依次描述 $T$ 组数据。

每组数据一行，包含一个时间（格式为 yyyy-MM-dd HH:mm:ss）和一
个整数 $x$，其中 $x$ 表示闹铃时间间隔（单位为分钟）。

输出格式

输出 $T$ 行，每行包含一个时间（格式为 yyyy-MM-dd HH:mm:ss），依
次表示每组数据的答案。

输入输出样例 #1

输入 #1

2
2016-09-07 18:24:33 10
2037-01-05 01:40:43 30

输出 #1

2016-09-07 18:20:00
2037-01-05 01:30:00

说明/提示

对于所有评测用例，$1 \le T \le 10，1 \le x \le 1000$，保证所有的时间格式都是合法的。

解决方案

收录这个题主要是想要记录一下Python中datetime库的使用：

from datetime import datetime, timedelta

if __name__ == "__main__":
    t = int(input())
    for i in range(t):
        date, time, x = input().split()
        year, month, day = map(int, date.split('-'))
        hour, minute, second = map(int, time.split(':'))

        # 使用datetime创建日期，其中年月日三个变量是必填的，时分秒如果不填则默认为0
        date_begin = datetime(1970, 1, 1)
        date_now = datetime(year, month, day, hour, minute, second)

        # 要善用取模，进而得到已经经过的周期数
        counts = int((date_now - date_begin).total_seconds()) // 60 // int(x)

        # 使用timedelta进行日期之间的运算
        ans = date_begin + timedelta(minutes=int(x)*counts)
        print(ans)

P10901 [蓝桥杯 2024 省 C] 封闭图形个数

题目描述

在蓝桥王国，数字的大小不仅仅取决于它们的数值大小，还取决于它们所形成的“封闭图形”的个数。

封闭图形是指数字中完全封闭的空间，例如数字$1$、$2$、$3$、$5$、$7$ 都没有形成封闭图形，而数字 $0$、$4$、$6$、$9$ 分别形成了 $1$ 个封闭图形，数字 $8$ 则形成了 $2$ 个封闭图形。值得注意的是，封闭图形的个数是可以累加的。例如，对于数字 $68$，由于 $6$ 形成了 $1$ 个封闭图形，而 $8$ 形成了 $2$ 个，所以 $68$ 形成的封闭图形的个数总共为 $3$。

在比较两个数的大小时，如果它们的封闭图形个数不同，那么封闭图形个数较多的数更大。例如，数字 $41$ 和数字 $18$，它们对应的封闭图形的个数分别为 $1$ 和 $2$，因此数字 $41$ 小于数组 $18$。如果两个数的封闭图形个数相同，那么数值较大的数更大。例如，数字 $14$ 和数字 $41$，它们的封闭图形的个数都是 $1$，但 $14 < 41$，所以数字 $14$ 小于数字 $41$。如果两个数字的封闭图形个数和数值都相同，那么这两个数字被认为是相等的。

小蓝对蓝桥王国的数字大小规则十分感兴趣。现在，他将给定你 $n$ 个数 $a_1, a_2,\cdots, a_n$，请你按照蓝桥王国的数字大小规则，将这 $n$ 数从小到大排序，并输出排序后结果。

输入格式

输入的第一行包含一个整数 $n$，表示给定的数字个数。

第二行包含 $n$ 个整数 $a_1, a_2,\cdots, a_n$，相邻整数之间使用一个空格分隔，表示待排序的数字。

输出格式

输出一行包含 $n$ 个整数，相邻整数之间使用一个空格分隔，表示按照蓝桥王国的数字大小规则从小到大排序后的结果。

输入输出样例 #1

输入 #1

3
18 29 6

输出 #1

6 29 18

说明/提示

【样例说明】

对于给定的数字序列 $[18, 29, 6]$，数字 $18$ 的封闭图形个数为 $2$，数字 $29$ 的封闭图形个数为 $1$，数字 $6$ 的封闭图形个数为 $1$。按照封闭图形个数从小到大排序后，得到 $[29, 6, 18]$。

由于数字 $29$ 和数字 $6$ 的封闭图形个数相同，因此需要进一步按照数值大小对它们进行排序，最终得到 $[6, 29, 18]$。

【评测用例规模与约定】

对于 $50\%$ 的评测用例，$1\le n \le 2 \times 10^3$，$1 \le a_i \le 10^5$。
对于所有评测用例，$1 \le n\le 2 \times 10^5$，$1 \le a_i \le 10^9$。

解决方案

这道题的思路挺明确的，可以使用一个字典来存储一个数字本身的值和其对应的封闭图形个数，然后分别作为第一关键字和第二关键字进行排序输出即可。

def main():
    length = int(input())
    nums = list(map(int, input().split()))

    count_1 = ["0", "4", "6", "9"]
    count_2 = ["8"]

    # 尝试用字典写这道题
    nums_dic = dict()
    for num in nums:
        count = 0
        for n in str(num):
            if n in count_1:
                count += 1
            elif n in count_2:
                count += 2
            nums_dic[num] = count

    print(nums_dic)

    nums_order = sorted(nums_dic.items(), key=lambda x:(x[1], x[0]), reverse=False)
    # 这里边主要想记录的就是在sorted()函数中使用lambda匿名函数。
    # 首先nums_dic.items()返回的是字典中的键值对集合(以样例输入为例)：
    # [(18, 2), (29, 1), (6, 1)]
    # 而sorted()函数会遍历这其中的每一个元组
    # 对于每一个元组，sorted()函数会将其作为参数传递给key参数
    # 而key参数又指定了匿名函数lambda x: (x[1], x[0])
    # 因此sorted()函数就会根据元组中具体的某一个值作为key进行排序
    # 此外，sorted()函数支持多关键字排序，使得上述写法可以实现多关键字排序
    print(nums_order)

    for num in nums_order:
        print(num[0], end=' ')

if __name__ == "__main__":
    main()

但是结果是这道题爆红了，主播喜提0分…

由于没有参考数据可以检查，使用deepseek得出的结论是：

1.字典去重问题：字典的键是数字本身，当输入中存在重复数字时，后续相同数字的计算会覆盖之前的记录。例如，输入 18 18 会被存储为 {18: 2}，导致输出时只保留一个 18。
2.排序结果缺失元素：最终输出基于字典的键（去重后的数字），而非原始输入的所有元素，导致输出数量与输入不一致。

因此解决方案就应该是动态地进行排序，使每一个输入都有一个对应的输出：

def main():
    length = int(input())
    nums = list(map(int, input().split()))

    # 定义每个字符对应的封闭图形个数
    holes = {'0': 1, '4': 1, '6': 1, '9': 1, '8': 2}

    # 直接排序原列表，动态计算封闭数作为排序依据
    nums.sort(key=lambda x: (sum(holes.get(i, 0) for i in str(x)), x))
    # 这里也是在lambda函数中定义了两个关键字
    # 第一关键字是x中的封闭图形个数之和，第二关键字是x本身
    # 突然觉得Python里的一行流也是浪漫之至啊

    print(' '.join(map(str, nums)))

if __name__ == "__main__":
    main()

最后成功AC！