输入样例#1：

4

3 12 9 9

输出样例#1：

4

1

2

2

输入样例#2：

3

3 9 6

输出样例#2：

3

1

2

输入样例#3：

4

100 100 100 100

输出样例#3：

1

1

1

1

补充说明

【样例说明】

样例一：1号同学第4名，2号同学第1名，3号和4号同学并列第二名。

【数据范围】

对于 100% 的数据，n<=100, a[i]<=100。

时间限制：1s 空间限制：512M

2.宝藏(treasure)

题目描述

在遥远的古代，有一个隐藏在密林深处的宝藏。宝藏的入口处有两块古老的石碑，每块石碑上面各刻着一组神秘的数字序列。只有从小到大输入两块石碑都有的数字（重复的数字也需要输出），才能打开宝藏的大门。

聪明的探险家们，你们能解开这个谜题，找到宝藏吗？

输入输出格式

输入格式：

第一行两个正整数 n,m 分别表示两块石碑上数字序列的长度。

第二行 n 个整数表示第一块石碑上的数字序列 A。

第三行 m 个整数表示第二块石碑上的数字序列 B。

输出格式：

一行，从小到大输出两块石碑都有的数字（重复的数字也要输出）。

数据保证至少存在一个数字在两块石碑的数字序列中均出现。

输入输出样例

输入样例#1：

4 5

4 2 5 2

2 1 9 2 4

输出样例#1：

2 2 4

输入样例#2：

5 5

1 2 3 4 5

1 1 1 1 1

输出样例#2：

1

补充说明

【样例说明】

样例一：两个序列均出现了 2 个 2, 1 个 4，故输出 2 2 4。

样例二：两个序列均出现了 1 个 1，故输出 1。

【数据范围】

对于 30% 的数据，n,m<=10，1<=a[i],b[i]<=10;

对于 60% 的数据，n,m<=1000, 1<=a[i],b[i]<=1000;

对于 100% 的数据，n,m<=1e5, 1<=a[i],b[i]<=1e9。

时间限制：1s 空间限制：512M

3.破损的石板铭文(stone)

题目描述

考古队在遗迹中发现了一块刻有 n 个数字的古老石板。据文献记载，这块石板原本是一句 "回文神谕"(即正着读和反着读都一样的序列)

然而由于风化，石板上混入了一些杂质数字。好在这些杂质数字非常特殊：它们全部都是同一种数字 x， 你可以选择这种数字 x ，并将石板上任意数量(零个、部分或全部)的该数字清除。

如果清除掉这些杂质后，剩下的数字能组成一句回文神谕，这块石板就被称为“圣物”。

例如:[3,1,2,3,1]这块石板就是圣物。把里面的3全部删除，剩下的数[1,2,1]就是一个"回文神谕";

[1,4,4,4,1]这块石板也是圣物。可以选择只删除中间的 4，剩下的[1,4,4,1]组成一个“回文神谕”;

[1,2,1]也是圣物。它本身就是一个回文数组;

[1,2,3]不是圣物。

请你判断，眼前的这块刻有 n 个数字石板 a 是否是传说中的圣物?

输入输出格式

输入格式：

输入共 2 行。

第一行一个数字 n，表示序列的长度。

第二行 n 个数字，表示石板 a 上刻的 n 个数字。

输出格式：

如果 a 是圣物，输出YES;否则，输出 NO.

输入输出样例

输入样例#1：

5

1 4 4 1 4

输出样例#1：

YES

输入样例#2：

6

1 5 3 2 4 1

输出样例#2：

NO

补充说明

【样例说明】

样例一中，可以选择 4，并删除数组最后一个 4，剩下的数组成[1,4,4,1]，是回文数组。因此[1,4,4,1,4]是圣物。

样例二中，找不到方案使得数组变成回文数组。

【数据范围】

对于 40% 的数据，1 ≤ n ≤ 2000,1 ≤ ai ≤ n;

对于 100%的数据，1 ≤ n ≤ 2*105,1 ≤ ai ≤ n.

时间限制：1s 空间限制：512M

4.巧克力礼盒(chocolate)

题目描述

甜品店老板有 n 块印有小写字母的巧克力，现在他想选择一些巧克力分装到 k 个精美的礼盒中送给顾客(不必将 n 个巧克力全部分装到 k 个盒子中)。

老板是个完美主义者，他要求：

每个礼盒里的巧克力字母经过排列后，必须是一个回文串。

所有的 k 个礼盒都必须至少分到一块巧克力。

为了公平起见，老板希望这 k 个礼盒中，含巧克力块数最少的礼盒，其数量也要尽可能地多。

你能帮老板算出，这个“最少块数”的最大值是多少吗?

补充说明：回文串是正读和反读都一样的字符串。比如：abcba 是回文串，abc 不是。

输入输出格式

输入格式：

输入共 2 行。

第一行两个数字 n 和 k，表示印有小写字母的巧克力的块数和礼盒个数。

第二行一个长度为 n 的字符串，该字符串只包含小写字母，表示 n 个印有小写字母的巧克力。

输出格式：

一行一个整数，表示含巧克力块数最少的礼盒的最多数量。

输入输出样例

输入样例#1：

8 2

bxyaxzay

输出样例#1：

3

输入样例#2：

6 3

wwfyfy

输出样例#2：

2

补充说明

【样例说明】

在样例一中，s="bxyaxzay"，k = 2。一种可行的分配方案如下:bxyaxzay(字母z的巧克力没有被装到盒子里)。染色后:

交换第一个盒子的两个字符(下标1和4)，得到 axybxzay;

交换第二个盒子的两个字符(下标5和8)，得到 axybyzax.

现在，对于每个盒子，从左到右写出对应的字符，得到两个字符串 aba 和 xyyx。它们都是回文串，最短的长度为 3。可以证明，最短回文串的最大长度无法超过 3。

【数据范围】

对于 10% 的数据，k=1;

另外存在 10% 的数据，k=n;

另外存在 10% 的数据，保证 n 个巧克力只印有一种字母;

对于 100% 的数据，1 ≤ k ≤ n ≤ 2*105，字符串只有小写字母组成。

时间限制：1s 空间限制：512M

5.自习室的节能灯(light)

题目描述

小明在自习室看书，自习室的灯被系统设定为在0时开启， m时准时关闭。系统还预设了n 个自动切换状态的时间点。

小明发现，只有在灯亮着的时候他才能专注看书。

幸运的是，控制面板出了一个小故障，允许小明在剩余的空闲时间点中，额外手动按下一次开关（最多只能一次）。当然，小明也可以选择不按下开关。

这一按会改变之后所有的灯光状态。

小明想尽可能多地争取看书时间。请你计算，如果小明采取最佳策略，最多能让灯亮多长时间？

输入输出格式

输入格式：

第一行两个整数, n,m;

以下一行有 n 个整数，即改变时间点

输出格式：

一个整数，即最大亮着的时间

输入输出样例

输入样例#1：

3 10

4 6 7

输出样例#1：

8

输入样例#2：

2 12

1 10

输出样例#2：

9

补充说明

【样例说明】

样例一中，在 5 时刻改变一次灯的状态，此时灯在0-4,5-6,7-10 这三个时间段是开着的，总时长是4+1+3=8;

样例二中，在 2 时刻改变一次灯的状态，此时灯在0-1,2-10 这两个时间段是开着的，总时长是1+8=9;

【数据范围】

对于 30% 的数据，1 ≤ n ≤ 1000;

对于 100% 的数据，1 ≤ n ≤ 105,1 ≤ m ≤ 109，字符串只有小写字母组成。

时间限制：1s 空间限制：512M

6.外卖员的电量管理(energy)

题目描述

外卖员 小Z 接到了一个长街任务，街上有 n 个配送点。第 i 个配送点会消耗电动车 ai 的电量。小Z 可以选择从第 l 个点开始工作，一直到第 r 个点结束。

车的电瓶有一个特殊的“自动过热保护”机制：初始过热值 g = 0。

每经过一个配送点，过热值g增加 ai。

如果 g 严格大于 安全阈值 x，保护系统会强制关机冷却，过热值 g 瞬间重置为 0。

为了保证效率，小Z 希望工作结束时，车子仍处于“热机“状态(即 g > 0) 以便继续前往下一条街。

请问有多少种 [l, r] 段落，能让他在完成任务后过热值g不为0?

输入输出格式

输入格式：

第一行包括两个整数n, x, 分别表示有 n 个配送点和安全阈值 x;

第二行包括 n 个整数，依次表示 a1,a2,...,an 。

输出格式：

对于每个测试用例，输出一个整数，即符合题目条件的方案数。

输入输出样例

输入样例#1：

4 2

1 1 1 1

输出样例#1：

8

输入样例#2：

6 3

1 2 1 4 3 8

输出样例#2：

10

补充说明

【样例说明】

样例一中，满足条件的(l,r)有(1,1),(1,2),(1,4),(2,2),(2,3),(3,3),(3,4),(4,4);

【数据范围】

对于 30% 的数据，1 ≤ n ≤ 100;

对于 100% 的数据,1 ≤ n ≤ 2 x 105,1 ≤ x ≤ 109,1 ≤ ai ≤ 109

时间限制：1s 空间限制：512M

少儿编程全部资源获取：（红字文章）

获取方式：付费获取（私信个人微信号：LEGO-robot-studio），送永久会员（后续全部更新内容可获取）。

加入乐高和

少儿编程交流群一起学习成长