一、实操题
1、儒略日（julian）
【题目描述】
为了简便计算，天文学家们使用儒略日（Julian day）来表达时间。所谓儒略日，其定义为从公元前 4713 年 1 月 1 日正午 12 点到此后某一时刻间所经过的天数，不满一天者用小数表达。若利用这一天文学历法，则每一个时刻都将被均匀的映射到数轴上，从而得以很方便的计算它们的差值。
现在，给定一个不含小数部分的儒略日，请你帮忙计算出该儒略日（一定是某一天的中午 12 点）所对应的公历日期。
我们现行的公历为格里高利历（Gregorian calendar），它是在公元 1582 年由教皇格里高利十三世在原有的儒略历（Julian calendar）的基础上修改得到的（注：儒略历与儒略日并无直接关系）。具体而言，现行的公历日期按照以下规则计算：
1. 公元 1582 年 10 月 15 日（含）以后：适用格里高利历，每年一月 31 天、二月 28 天或 29 天、三月 31 天、四月 30 天、五月 31 天、六月 30 天、七月 31 天、八月 31 天、九月 30 天、十月 31 天、十一月 30 天、十二月 31天。其中，闰年的二月为 29 天，平年为 28 天。当年份是 400 的倍数，或日期年份是 4 的倍数但不是 100 的倍数时，该年为闰年。
2. 公元 1582 年 10 月 5 日（含）至 10 月 14 日（含）：不存在，这些日期被删除，该年 10 月 4 日之后为 10 月 15 日。
3. 公元 1582 年 10 月 4 日（含）以前：适用儒略历，每月天数与格里高利历相同，但只要年份是 4 的倍数就是闰年。
4. 尽管儒略历于公元前 45 年才开始实行，且初期经过若干次调整，但今天人类习惯于按照儒略历最终的规则反推一切 1582 年 10 月 4 日之前的时间。
注意，公元零年并不存在，即公元前 1 年的下一年是公元 1 年。因此公元前 1 年、前 5 年、前 9 年、前 13 年……以此类推的年份应视为闰年。
【输入格式】
输入文件名为 julian.in。
第一行一个整数 Q，表示询问的组数。
接下来 Q 行，每行一个非负整数 ri，表示一个儒略日。
【输出格式】
输出文件名为 julian.out。
对于每一个儒略日 ri，输出一行表示日期的字符串 si。共计 Q 行。
si 的格式如下：
1.若年份为公元后，输出格式为 Day Month Year。其中日（Day）、月（Month）、年（Year）均不含前导零，中间用一个空格隔开。
例如：公元2020 年 11 月 7 日正午 12 点，输出为 7 11 2020。
2. 若年份为公元前，输出格式为 Day Month Year BC。其中年（Year）输出该年份的数值，其余与公元后相同。例如：公元前 841 年 2 月 1 日正午 12点，输出为 1 2 841 BC。
【样例 1 输入】
3
10
100
1000
【样例 1 输出】
11 1 4713 BC
10 4 4713 BC
27 9 4711 BC
【样例 2 输入】
3
2000000
3000000
4000000
【样例 2 输出】
14 9 763
15 8 3501
12 7 6239
【数据范围与提示】
参考答案：对于每个儒略日 ri，我们需要根据儒略日与公历的转换规则，计算出对应的公历日期。首先，我们需要判断儒略日 ri 是否小于 0，如果小于 0，表示该日期在公元前，需要输出格式为 Day Month Year BC。否则，表示该日期在公元后，需要输出格式为 Day Month Year。然后，我们需要判断儒略日 ri 是否大于等于 2440588，即 1582 年 10 月 5 日的儒略日，如果是，则按照格里高利历的规则进行计算，否则按照儒略历的规则进行计算。具体的计算过程如下：1. 如果儒略日 ri 小于 0，则年份为 -ri，月份为 12，日期为 30 - (-ri) mod 30 + 1。2. 如果儒略日 ri 大于等于 2440588，则年份为 ri - 2440587，月份和日期需要根据年份和儒略日 ri 的值进行计算。3. 如果儒略日 ri 小于 2440588，则年份为 4713 - (ri - 1) / 365.25，月份和日期需要根据年份和儒略日 ri 的值进行计算。最后，根据计算出的年份、月份和日期，输出对应的公历日期。
解析：【喵呜刷题小喵解析】：
本题是一道关于儒略日与公历日期转换的题目，需要我们根据儒略日与公历的转换规则，计算出对应的公历日期。
首先，我们需要了解儒略日与公历的转换规则。儒略日是从公元前 4713 年 1 月 1 日正午 12 点到此后某一时刻间所经过的天数，不满一天者用小数表达。而公历日期则按照格里高利历的规则进行计算，其中闰年的判断规则为：年份是 400 的倍数，或日期年份是 4 的倍数但不是 100 的倍数。同时，我们还需要注意儒略历与儒略日并无直接关系，儒略历与公历的转换规则比较复杂。
根据题目要求，我们需要对输入的儒略日进行转换，计算出对应的公历日期。具体的计算过程需要根据儒略日与公历的转换规则进行，包括判断儒略日是否小于 0、是否大于等于 2440588 等情况，然后按照不同的规则进行计算。
最后，根据计算出的年份、月份和日期，输出对应的公历日期。在输出时，需要注意日期的格式，即公元前的日期格式为 Day Month Year BC，公元后的日期格式为 Day Month Year。
需要注意的是，由于儒略历与儒略日并无直接关系，因此我们在计算时需要按照儒略历的规则反推一切 1582 年 10 月 4 日之前的时间。同时，由于儒略历于公元前 45 年才开始实行，且初期经过若干次调整，因此在计算时需要按照儒略历最终的规则进行计算。
2、动物园（zoo）
【题目描述】
动物园里饲养了很多动物，饲养员小 A 会根据饲养动物的情况，按照《饲养指南》购买不同种类的饲料，并将购买清单发给采购员小 B。
具体而言，动物世界里存在 2k 种不同的动物，它们被编号为 0 ∼ 2^k −1。动物园里饲养了其中的 n 种，其中第 i 种动物的编号为 ai。
《饲养指南》中共有 m 条要求，第 j 条要求形如“如果动物园中饲养着某种动物，满足其编号的二进制表示的第 pj 位为 1，则必须购买第 qj 种饲料”。其中饲料共有 c 种，它们从 1 ∼ c 编号。本题中我们将动物编号的二进制表示视为一个 k 位 01 串，第 0 位是最低位，第 k − 1 位是最高位。
根据《饲养指南》，小 A 将会制定饲料清单交给小 B，由小 B 购买饲料。清单形如一个 c 位 01 串，第 i 位为 1 时，表示需要购买第 i 种饲料；第 i 位为 0 时，表示不需要购买第 i 种饲料。
实际上根据购买到的饲料，动物园可能可以饲养更多的动物。更具体地，如果将当前未被饲养的编号为 x 的动物加入动物园饲养后，饲料清单没有变化，那么我们认为动物园当前还能饲养编号为 x 的动物。
现在小 B 想请你帮忙算算，动物园目前还能饲养多少种动物。
【输入格式】
输入文件名为 zoo.in。
第一行包含四个以空格分隔的整数 n、m、c、k。分别表示动物园中动物数量、《饲养指南》要求数、饲料种数与动物编号的二进制表示位数。
. 第二行 n 个以空格分隔的整数，其中第 i 个整数表示 ai。
接下来 m 行，每行两个整数 pi，qi表示一条要求。
数据保证所有 ai 互不相同，所有的 qi 互不相同。
【输出格式】
输出文件名为 zoo.out。
仅一行一个整数表示答案。
【样例 1 输入】
3 3 5 4
1 4 6
0 3
2 4
2 5
【样例 1 输出】
13
【样例 1 解释】
动物园里饲养了编号为 1、4、6 的三种动物，《饲养指南》上 3 条要求为：
1. 若饲养的某种动物的编号的第 0 个二进制位为 1，则需购买第 3 种饲料。
2. 若饲养的某种动物的编号的第 2 个二进制位为 1，则需购买第 4 种饲料。
3. 若饲养的某种动物的编号的第 2 个二进制位为 1，则需购买第 5 种饲料。
饲料购买情况为：
1. 编号为 1 的动物的第 0 个二进制位为 1，因此需要购买第 3 种饲料；
2. 编号为 4、6 的动物的第 2 个二进制位为 1，因此需要购买第 4、5 种饲料。
由于在当前动物园中加入一种编号为 0,2,3,5,7,8, ⋯ ,15 之一的动物，购物清单都不会改变，因此答案为 13。
【样例 2 输入】
2 2 4 3
1 2
1 3
2 4
【样例 2 输出】
2
【数据范围与提示】
对于 20%的数据：k ≤ n ≤ 5，m ≤ 10，c ≤ 10，所有的 pi 互不相同。
对于 40%的数据：n ≤ 15，k ≤ 20，m ≤ 20，c ≤ 20。
对于 60%的数据：n ≤ 30，k ≤ 30，m ≤ 1000。
对于 100%的数据：0 ≤ n, m ≤ 10^6，0 ≤ k ≤ 64，1 ≤ c ≤ 10^8。
参考答案：对于每个动物，我们可以根据《饲养指南》判断它是否需要购买某种饲料。如果不需要，那么该动物可以被饲养。我们可以使用位运算来快速判断动物编号的二进制表示的第pj位是否为1。如果为1，则需要购买第qj种饲料，否则不需要。对于每个动物，我们可以使用位运算来快速判断它是否满足《饲养指南》的所有要求。如果满足，则该动物可以被饲养。我们可以遍历所有可能的动物编号，判断它们是否满足要求，并统计能被饲养的动物数量。
解析：【喵呜刷题小喵解析】：
本题是一道关于位运算和集合运算的题目。首先，我们需要根据《饲养指南》判断动物是否需要购买某种饲料，然后根据判断结果确定哪些动物可以被饲养。
具体来说，我们可以遍历所有可能的动物编号，对于每个编号，我们根据《饲养指南》判断它是否需要购买某种饲料。如果不需要，那么该动物可以被饲养。
我们可以使用位运算来快速判断动物编号的二进制表示的第pj位是否为1。如果为1，则需要购买第qj种饲料，否则不需要。我们可以使用按位与运算符&来判断动物编号的二进制表示的第pj位是否为1。
接下来，我们需要遍历所有可能的动物编号，对于每个编号，我们可以使用位运算来快速判断它是否满足《饲养指南》的所有要求。如果满足，则该动物可以被饲养。
具体地，我们可以遍历《饲养指南》中的每条要求，对于每条要求，我们可以使用按位或运算符|来判断动物编号的二进制表示的第pj位是否为1。如果所有要求都满足，则该动物可以被饲养。
最后，我们可以统计能被饲养的动物数量，即为答案。
需要注意的是，由于动物编号的二进制表示位数较大，我们可能需要使用高精度算法来存储和计算。此外，由于数据量较大，我们可能需要使用高效的算法来遍历和判断。
3、函数调用（call）
【题目描述】
函数是各种编程语言中一项重要的概念，借助函数，我们总可以将复杂的任务分解成一个个相对简单的子任务，直到细化为十分简单的基础操作，从而使代码的组织更加严密、更加有条理。然而，过多的函数调用也会导致额外的开销，影响程序的运行效率。
某数据库应用程序提供了若干函数用以维护数据。已知这些函数的功能可分为三类：
1. 将数据中的指定元素加上一个值；
2. 将数据中的每一个元素乘以一个相同值；
3. 依次执行若干次函数调用，保证不会出现递归（即不会直接或间接地调用本身）。
在使用该数据库应用时，用户可一次性输入要调用的函数序列（一个函数可能被调用多次），在依次执行完序列中的函数后，系统中的数据被加以更新。某一天，小 A 在应用该数据库程序处理数据时遇到了困难：由于频繁而低效的函数调用，系统在执行操作时进入了无响应的状态，他只好强制结束了数据库程序。为了计算出正确数据，小 A 查阅了软件的文档，了解到每个函数的具体功能信息，现在他想请你根据这些信息帮他计算出更新后的数据应该是多少。
【输入格式】
输入文件名为 call.in。
第 1 行一个正整数 n，表示数据的个数。
第 2 行 n 个整数，第 i 个整数表示下标为 i 的数据的初始值为 ai。
第 3 行一个正整数 m，表示数据库应用程序提供的函数个数。函数从 1 ∼m 编号。
接下来 m 行中，第 j（1 ≤ j ≤ m）行的第一个整数为 Tj，表示 j 号函数的类型：
1. 若 Tj = 1，接下来两个整数 Pj, Vj 分别表示要执行加法的元素的下标及其增加的值；
2. 若 Tj = 2，接下来一个整数 Vj 表示所有元素所乘的值；
3. 若 Tj = 3，接下来一个正整数 Cj 表示 j 号函数要调用的函数个数，随后 Cj个整数 g1(j), g2(j), ⋯ , gCj(j) 依次表示其所调用的函数的编号。
第 m + 4 行一个正整数 Q，表示输入的函数操作序列长度。
第 m+ 5 行 Q 个整数 fi，第 i 个整数表示第 i 个执行的函数的编号。
【输出格式】
输出文件名为 call.out。
一行 n 个用空格隔开的整数，按照下标 1 ∼ n 的顺序，分别输出在执行完输入的函数序列后，数据库中每一个元素的值。答案对 998244353 取模。
【样例 1 输入】
3
1 2 3
3
1 1 1
2 2
3 2 1 2
2
2 3
【样例 1 输出】
6 8 12
【样例 1 解释】
1 号函数功能为将 a1 的值加一。2 号函数功能为所有元素乘 2。3 号函数将先调用 1 号函数，再调用 2 号函数。
最终的函数序列先执行 2 号函数，所有元素的值变为 2,4,6。
再执行 3 号函数时，先调用 1 号函数，所有元素的值变为 3,4,6。再调用 2号函数，所有元素的值变为 6,8,12。
【样例 2 输入】
10
1 2 3 4 5 6 7 8 9 10
8
3 2 2 3
3 2 4 5
3 2 5 8
2 2
3 2 6 7
1 2 5
1 7 6
2 3
3
1 2 3
【样例 2 输出】
36 282 108 144 180 216 504 288 324 360
【数据范围与提示】
对于所有数据：0 ≤ ai ≤ 10^4，Tj ∈ {1,2,3}，1 ≤ Pj ≤ n，0 ≤ Vj ≤ 10^4，1 ≤
≤ m，1 ≤fi ≤ m。
参考答案：对于每个函数调用，我们需要根据函数类型进行相应的操作。对于类型为1的函数，我们需要找到指定的元素并加上一个值；对于类型为2的函数，我们需要将每个元素乘以一个值；对于类型为3的函数，我们需要递归地执行它所调用的函数。为了解决这个问题，我们可以使用模拟的方法。首先，我们读入初始的数据和函数列表。然后，按照输入的函数序列，依次执行每个函数。对于每个函数，我们根据函数类型进行相应的操作，并更新数据。最后，我们输出更新后的数据。由于数据量较大，我们需要注意模运算，以避免溢出。在本题中，我们需要对答案取模998244353。
解析：【喵呜刷题小喵解析】：
本题是一道涉及函数调用和模拟的问题。首先，我们需要理解函数的类型和功能，并根据函数的类型进行相应的操作。
对于类型为1的函数，我们需要找到指定的元素并加上一个值。我们可以使用一个数组来存储数据，并根据函数中的下标和增加的值来更新相应的元素。
对于类型为2的函数，我们需要将每个元素乘以一个值。我们可以遍历数组中的每个元素，并将其乘以函数中的值。
对于类型为3的函数，我们需要递归地执行它所调用的函数。我们可以使用一个栈来模拟函数的调用过程。首先，将当前函数压入栈中，然后依次执行它所调用的函数，直到没有函数可调用为止。然后，从栈中弹出函数，并执行相应的操作。
在模拟过程中，我们需要注意模运算，以避免溢出。在本题中，我们需要对答案取模998244353。
最后，我们按照下标顺序输出更新后的数据。
需要注意的是，本题中函数调用的顺序可能比较复杂，需要仔细处理。同时，由于数据量较大，我们需要使用高效的数据结构和算法来解决问题。
4、贪吃蛇（snakes）
【题目描述】
草原上有 n 条蛇，编号分别为 1,2, ⋯ , n。初始时每条蛇有一个体力值ai，我们称编号为 x 的蛇实力比编号为 y 的蛇强当且仅当它们当前的体力值满足 ax > ay，或者 ax = ay 且 x > y。
接下来这些蛇将进行决斗，决斗将持续若干轮，每一轮实力最强的蛇拥有选择权，可以选择吃或者不吃掉实力最弱的蛇：
1. 如果选择吃，那么实力最强的蛇的体力值将减去实力最弱的蛇的体力值，实力最弱的蛇被吃掉，退出接下来的决斗。之后开始下一轮决斗。
2. 如果选择不吃，决斗立刻结束。
每条蛇希望在自己不被吃的前提下在决斗中尽可能多吃别的蛇（显然，蛇不会选择吃自己）。
现在假设每条蛇都足够聪明，请你求出决斗结束后会剩几条蛇。
本题有多组数据，对于第一组数据，每条蛇体力会全部由输入给出，之后的每一组数据，会相对于上一组的数据，修改一部分蛇的体力作为新的输入。
【输入格式】
输入文件名为 snakes.in。
第一行一个正整数 T，表示数据组数。
接下来有 T 组数据，对于第 1 组数据，第一行一个正整数 n，第二行 n个非负整数表示 ai。
对于第 2 组到第 T 组数据，每组数据：
第一行第一个非负整数 k 表示体力修改的蛇的个数。
第二行 2k 个整数，每两个整数组成一个二元组 (x, y)，表示依次将 ax的值改为 y。一个位置可能被修改多次，以最后一次修改为准。
【输出格式】
输入文件名为 snakes.out。
输出 T 行，每行一个整数表示最终存活的蛇的条数。
【样例 1 输入】
2
3
11 14 14
3
1 5 2 6 3 25
【样例 1 输出】
3
1
【样例 1 解释】
第一组数据，第一轮中 3 号蛇最强，1 号蛇最弱。若 3 号蛇选择吃，那么它将在第二轮被 2 号蛇吃掉。因此 3 号蛇第一轮选择不吃，3 条蛇都将存活。
对于第二组数据，3 条蛇体力变为 5,6,25。第一轮中 3 号蛇最强，1 号蛇最弱，若它选择吃，那么 3 号蛇体力值变为 20，在第二轮中依然是最强蛇并能吃掉 2 号蛇，因此 3 号蛇会选择两轮都吃，最终只有 1 条蛇存活。
【样例 2 输入】
2
5
13 31 33 39 42
5
1 7 2 10 3 24 4 48 5 50
【样例 2 输出】
5
3
【数据范围与提示】
对于 20%的数据：n = 3。
对于 40%的数据：n ≤ 10。
对于 55%的数据：n ≤ 2000。
对于 70%的数据：n ≤ 5 × 10^4。
对于 100%的数据：3 ≤ n ≤ 10^6，1 ≤ T ≤ 10，0 ≤ k ≤ 10^5，0 ≤ ai, y ≤10^9。
保证每组数据（包括所有修改完成后的）的 ai 以不降顺序排列。
参考答案：对于每组数据，我们需要模拟蛇的决斗过程，直到只剩下一条蛇为止。首先，我们读入蛇的数量n和初始的体力值数组a。然后，对于每一组数据，读入修改蛇体力的个数k和修改后的体力值。在模拟过程中，我们维护一个指针i指向当前最强蛇的位置，和一个指针j指向当前最弱蛇的位置。在每一轮决斗中，如果最强蛇的体力值大于最弱蛇的体力值，则最强蛇选择吃，体力值减去最弱蛇的体力值，最弱蛇被吃掉，退出决斗。否则，最强蛇选择不吃，决斗结束。最后，当只剩下一条蛇时，输出存活的蛇的数量。
解析：【喵呜刷题小喵解析】：
本题是一道模拟题，需要模拟蛇的决斗过程。由于蛇的数量n较大，我们需要使用高效的算法来模拟决斗过程。
在模拟过程中，我们可以使用双指针i和j来维护当前最强蛇和最弱蛇的位置。在每一轮决斗中，如果最强蛇的体力值大于最弱蛇的体力值，则最强蛇选择吃，体力值减去最弱蛇的体力值，最弱蛇被吃掉，退出决斗。否则，最强蛇选择不吃，决斗结束。
在模拟过程中，我们需要及时更新指针i和j的位置，以保证在每一轮决斗中选取最强和最弱的蛇。由于体力值数组a是以不降顺序排列的，因此我们可以直接通过指针i和j的位置来选取最强和最弱的蛇，而不需要遍历整个数组。
最后，当只剩下一条蛇时，输出存活的蛇的数量即可。
需要注意的是，由于蛇的数量n较大，我们需要使用高效的算法来模拟决斗过程，以避免超时。在本题中，我们可以使用双指针i和j来维护当前最强蛇和最弱蛇的位置，从而避免遍历整个数组，提高算法的效率。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
