程序设计竞赛1

题目1

2025年春节期间，DeepSeek作为“AI界的天降紫微星”成为新晋效率神器，热度席卷全球，其团队主创成员也迅速引起了大家的关注。
DeepSeek之所以能在短时间内取得如此不凡成绩，与其团队成员的背景密不可分。团队汇聚了来自清华、北大等顶尖高校的一群杰出毕业生。根据团队成员的已公开履历，8位成员拥有NOI（全国青少年信息学奥林匹克竞赛）奖牌，其中4位为IOI（国际信息学奥林匹克竞赛）金牌得主。他们从信奥赛场起步，一路披荆斩棘，经过多年的积累和实战，最终取得了突破性的成就，让DeepSeek大放异彩。这也正是信息学奥赛魅力与价值的最佳证明。
本题非常简单，就请你直接在屏幕上输出DeepSeek的欢迎词。

输入格式:

本题没有输入。

输出格式:

见输出样例。

输入样例:

无

输出样例:

\^_^DeepSeek^_^\

题目2

对于一份试卷，如果考试结果的及格率不低于75%、良好率不低于25%，则认为该试卷的考题是合适的。这里约定及格成绩是指不低于试卷总分的60%的成绩，良好成绩是指不低于试卷总分的80%的成绩。给你试卷总分m和考生人数n，再告诉你n个考生的成绩，请判断该试卷是否合适并计算及格率和良好率。

输入格式:

第一行输入试卷总分m和考生人数n(0<n≤100)。
第二行输入n个整数，表示考生成绩，第i个考生的成绩为ai​(1≤i≤n)。显然，0≤ai​≤m。

输出格式:

在一行上输出评价、及格率和良好率，数据之间以一个空格间隔。若考题合适评价为Yes，否则评价为No。及格率和良好率都以百分比形式表示，且保留1位小数。

输入样例:

150 5
120 100 75 90 145

输出样例:

Yes 80.0% 40.0%

题目3

岁在龙蛇，自强不息！龙年（2024年）将去，蛇年（2025年）在来。显然，每个年份对应一个生肖。对于给定的若干年份，请输出这些年份中出现次数最多的生肖（以英文单词表示，详见最后的提示）。若有多个生肖出现次数最多，输出字典序最小的那个生肖。

输入格式:

首先输入一个正整数T(T<100)，表示测试数据的组数，然后是T组测试数据。每组测试先输入一个整数n(1<n≤9000)，再输入n个年份year(1000≤year<10000)。

输出格式:

对于每组测试，在一行上输出n个年份相应生肖出现次数最多的那个生肖。若有多个生肖出现次数最多，输出字典序最小的那个生肖。

输入样例:

2
4
2037
2023
2024
2025
5
2022
2023
2024
2025
2012

输出样例:

snake
dragon

提示:

鼠、牛、虎、兔、龙、蛇、马、羊、猴、鸡、狗、猪等十二生肖相应的英文单词如下：
rat、ox、tiger、rabbit、dragon、snake、horse、goat、monkey、rooster、dog、pig

题目4

2025年春节最火的电影是《哪吒之魔童闹海》，电影票房简直跟坐火箭似的，嗖嗖地往上蹿，雄踞全球单一市场、中国影史、中国动画电影票房榜首。2025年2月13日19时许，总票房突破100亿元。

导演饺子按照往常惯例，通过手绘海报的方式官宣破亿情况。据统计，自票房破1亿元开始（包括1亿），饺子导演每破一亿就画一张。网友调侃“饺子的笔快画冒烟了”“这简直是史上最强寒假作业，早知道十亿十亿画了！”。也有多位网友表示要帮饺子导演画破亿海报，甚至提前帮忙画好了破百亿的海报。

输入格式:

输入在一行中给出2个不超过200的正整数n和d，空格分隔。其中n代表票房数量（单位亿元），d代表票房破1亿开始到现在间隔的天数（包括破1亿当天）。

输出格式:

在一行中输出m和t，空格分隔。其中m为一个小数（小数位数为1位），代表饺子平均每天手绘海报的张数，t为一个正整数，代表饺子至少每t个小时就要画一幅海报。

输入样例1:

4 1

输出样例1:

4.0 6

输入样例2:

7 2

输出样例2:

3.5 6

题目5

‌‌五子棋的基本规则为五连胜利‌：当一方在棋盘上横向、竖向或斜向连成五个相同颜色的棋子时，该方即获得胜利。‌小D和小K正在一个15*15的棋盘上下五子棋，小D执白子，小K执黑子，白子先下。为了速战速决，两人一致同意五子决定胜负，请你来判断下他们的对战结果。

输入格式:

输入为一个15*15的矩阵，其中0代表该位置尚未落子，1代表该位置是白子，2代表该位置是黑子。

输出格式:

如果白子或黑子的个数不是5，则判定结果为违规，在第一行输出"ERROR!"，第二行分别输出白子和黑子的个数，中间用空格分隔。
否则，如果白子满足五连胜利‌规则，则首先在第一行首先输出"White Win,Game Over!"，第二行根据白子是横向、竖向还是斜向输出不同信息。"All chess pieces are in the same row."代表白子在同一行；"All chess pieces are in the same column."代表白子在同一列；"All chess pieces are in the same main diagonal."代表白子在同一主对角线（从左上角到右下角）；"All chess pieces are in the same Anti-diagonal."代表白子在同一副对角线（从右上角到左下角）。
否则，如果黑子满足五连胜利‌规则，则首先在第一行首先输出"Black Win,Game Over!"，第二行根据黑子是横向、竖向还是斜向输出不同信息。"All chess pieces are in the same row."代表黑子在同一行；"All chess pieces are in the same column."代表黑子在同一列；"All chess pieces are in the same main diagonal."代表黑子在同一主对角线（从左上角到右下角）；"All chess pieces are in the same Anti-diagonal."代表黑子在同一副对角线（从右上角到左下角）。
如果白子和黑子都不满足五连胜利‌规则，则输出"Again!"。

输入样例1:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 2 2 2 2 2 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

输出样例1:

White Win,Game Over!
All chess pieces are in the same row.

输入样例2:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 1 1 1 2 1 1 0 0 0 0 0
0 0 0 0 0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

输出样例2:

Black Win,Game Over!
All chess pieces are in the same column.

输入样例3:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 1 1 1 2 1 0 0 0 0 0 0
0 0 0 0 0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 2 2 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

输出样例3:

ERROR!
4 6

输入样例4:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 2 1 1 0 0 0 0 0
0 0 0 0 0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 2 2 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

输出样例4:

Again!

题目6

在深度学习任务中，我们有 n 个模型需要训练，每个模型的训练时间已知，记作数组 a[i]（表示第 i 个模型的训练时间）。 现在，我们有 m 张 GPU 可供并行训练。
为了减少训练总时长，我们需要合理地将 n 个模型顺序地分配给 m 张 GPU，使得所有 GPU 训练完成的最长时间尽可能小。
注意：

• 任务必须从左到右连续分配，即某个 GPU 负责的模型必须是数组 a 中的一段连续子序列。
• 每个模型必须且只能被分配给一个 GPU 进行训练。
• GPU 之间可以并行训练，但我们关心的是最晚完成任务的 GPU，即所有 GPU 训练完成的最短可能时间。

输入格式:

第一行：两个整数 n 和 m（1≤m≤n≤105），分别表示模型数和GPU数。
第二行：n 个整数 a[i](1≤a[i]≤109)，表示每个模型的训练时间，每个数之间用一个空格分隔。

输出格式:

一个整数，表示最优任务分配方案下，所有 GPU 训练完成的最短可能时间。

输入样例:

4 2
3 1 4 7

输出样例:

8

样例解释

可能的任务分配方式如下：

• 方案 1：【3】，【1，4，7】，最长时间12。
• 方案 2：【3，1】，【4，7】，最长时间11。
• 方案 3：【3，1，4】，【7】，最长时间8。

最终，最优方案的完成时间为 8。

题目7

任何整数都可以分解成2的整数次幂之和，例如：
6 = 2 + 4
6 = 1 + 1 + 4
6 = 2 + 2 + 2
6 = 1 + 1 + 2 + 2
6 = 1 + 1 + 1 + 1 + 2
6 = 1 + 1 + 1 + 1 + 1 + 1

本题不需要你求出所有分解方案，只需要给出上面第一种分解等式，即等式右边项数最少的分解方案，并且每一项数值从小到大排列。

输入格式:

输入为一个正整数n（n⩽109）。

输出格式:

输出满足题目要求的分解等式。

输入样例:

6

输出样例:

6 = 2 + 4

题目8

小明很热爱学习，他在不断地学习过程中会获得两种知识点。
1.完全掌握的知识点：小明即刻获得所有知识点值。
2.逐渐掌握的知识点：小明在次日获得指定值，然后之后的每一天都额外获得一个知识点值。
但是总有人"关心"他的学习情况，并不时地查看他的知识点值。
给定一条时间线，小明的初始知识点为0，随着他的不断学习，询问他当前知识点。
共有3种操作， 题目保证一定按照时间线顺序给出，同一天内查看知识点一定在掌握知识点之后 。

• 操作 1 ： 输入格式为1 t a ，表示在第 t 天获得 1 个完全掌握的知识点，知识点值为 a (1≤a≤105)。
• 操作 2 ： 输入格式为2 t b ，表示在第 t 天获得 1 个逐渐掌握的知识点，指定值为 b (1≤b≤105)。
• 操作 3 ： 输入格式为3 t ，表示询问第 t 天小明的知识点值。

输入格式:

第一行一个整数 n (1≤n≤1012) 和 q (1≤q≤5∗105) 分别表示时间线长度和操作次数。
随后 q 行，按照题目条件给出操作，其中1≤t≤n。

输出格式:

当执行操作 3 时，在一行中输出小明当前的知识点值。

输入样例:

10 6
1 1 1
3 1
2 2 2
3 2
3 3
3 4

输出样例:

1
1
3
4

题目9

我相信，每个人都写过一个关于心动的剧本。在那个有风的下午，她穿着白T恤和牛仔裤，和你分享一样的食物，或者为你唱首歌，总之，在你心动之前她与你所经历的一切你已经计划过千次万次。
——《一起同过窗》路桥川

故事的开始是在英语课上，男孩第一次遇见了女孩，到后来的相识相知。没有刻意的剧情，也没有矫揉造作，一切自然而然地发生。今天，男孩想写一封英文情书给女孩，但碍于男孩的Poor English，他想求助你的帮助，来帮他完善他的情书。

已知情书是一个长度不超过256个字符的非空字符串s，情书中仅包括字母、数字、空格、可见的半角标点符号。情书中包含若干个句子，每个句子以英文的句号.或叹号!作为结束的标志。!,.这三个英文符号后都会有一个空格。现在要按照如下的要求，来修改这封情书。

• 除了句首的字母要大写外，其他所有字母都是小写。
• 粗心的男孩在情书中混了了奇怪的东西。除了数字、字母、及三个英文符号：叹号!、逗号,和句号.外，帮他把其他的字符直接删去。
• 男孩连数字的英文都不会写，帮他把独立的单个数字换成对应的英文单词。（独立指被空格或标点符号分隔开。）
• 男孩的爱意汹涌，但不敢平铺直叙。帮他把所有独立的"love"（不论大小写）替换成"crush"。
• 喜欢的小心思也要好好隐藏。帮男孩把出现过独立的"like"（不论大小写）的句子进行翻转（表示结束的!或.不翻转）,不论一句话中出现几个独立的"like",都最多翻转1次。

上述操作的顺序： 完成去除其他字符、转换单个数字、替换"love"后，若有"like"反转句子（包括句子中的逗号,）。最后将句首字母大写并加上结尾的句号.或叹号!。

请特别注意行末的句号.或叹号！后也有一个空格。

输入格式

输入一行，字符串 s (∣s∣<=256)。

输出格式

输出一行，输出修改后的字符串s。

输入样例

sO, whEn i f1rst tim/e s@Aw yOu. loveing lovE tHinG. liKe you. 11 1 life. 

输出样例

So, when i f1rst time saw you. Loveing crush thing. Uoy ekil. 11 one life. 

提示

0−zero, 1−one, 2−two, 3−three, 4−four.

5−five, 6−six, 7−seven, 8−eight, 9−nine.

题目10

zjj是漂薄[1]异乡的旅人，他总是一个人踏上旅途。

他在 n 个城市之间游荡，城市之间存在 m 条通路，第 i 条通路的距离为 2i，i 从 1 开始计数。

他想进行一次游览。一次游览被定义为从某城市出发游玩，历经至少三个不同的城市，最终回到出发点。

囿于[2]zjj匮乏的脚力，他希望在这次游览中行走的距离最短。

现在，封你为开国大将军[3]，你可以指定zjj的诞生地与行走路线，请你求出他在游览中的最短距离。

[1] 漂薄：汉语词语，读音piāo báo，意思是漂泊。

[2] 囿于：汉语词语，读音yòu yú，意思是被局限在；受（某种情况）拘束；受束缚。

[3] 开国大将军：古代的一个封号，这里类比神明，可以唯心[4]地指定zjj的诞生地与行走路线。

[4] 唯心：与“唯物”相对。主张人类思想、意识和精神世界是世界的本原和支配者，而物质世界只是精神世界的反映或表现。

更加形式化的题面如下：

给定一个无向图，图中有 n 个顶点和 m 条边，其中第 i 条边的长度为 2i，图中的顶点与边的索引均从 1 开始计算。

请你找出一个长度最小的简单循环。

简单循环是原始图的一个子图，包含 k (3≤k≤n) 个顶点 a1​、a2​、⋯、ak​ 和 k 条边，对于所有的 1≤i≤k，都有一条边连接着子图中的顶点 ai​ 和 a(imodk)+1​。简单循环的长度是这张子图中边的总长度。

输入格式:

有多个测试用例。输入的第一行包含一个整数 T，表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 n 和 m (3≤n≤105, 1≤m≤105)，表示原始图中顶点和边的数量。

接下来 m 行，第 i 行包含两个整数 ui​ 和 vi​ （1≤ui​,vi​≤n），表示连接顶点 ui​ 和 vi​ 的边，其长度为 2i 。保证图中没有重边和自环。请注意，图不一定是连通的。

保证所有测试用例的 n 和 m 之和都不会超过 106。

输出格式:

每个测试用例输出一行。

如果图中没有简单循环，则输出 -1；否则输出 k 个整数，用空格隔开，按递增顺序排列，表示长度最小的简单循环中的边的索引。可以证明最多只有一个答案。

请注意不要在每行末尾输出多余的空格。

输入样例:

<span style="color:#404040"><code class="language-in">2
6 8
1 2
2 3
5 6
3 4
2 5
5 4
5 1
4 2
4 2
1 2
4 3
</code></span>

输出样例:

<span style="color:#404040"><code class="language-out">2 4 5 6
-1
</code></span>

提示：

对于样例中的第一个测试用例：

长度最小的简单循环由边 2, 4, 5 和 6 组成，长度为 22+24+25+26=116。可以证明简单循环的最小长度是 116 。