蓝桥杯算法赛第25场月赛

前言

这些题对于我的难度有点大，大家感兴趣的可以来做一下，看一下，下面给大家展示一下题目

1. 桃花运走向【算法赛】

问题描述

2025 年春节，小明和小红兴致勃勃地去庙会玩耍。庙会上，一个算命先生摆摊算命，吸引了不少人围观。

小明：“大师，大师，请帮我算算今年我的桃花运如何？”

算命先生捋着胡须，神秘兮兮地说：“小伙子，我看你印堂发黑，今年桃花运…嗯…不太旺盛，不过，会有意外之喜！”

小红在一旁插话：“大师，大师，那我的呢？我的桃花运如何？”

算命先生看了看小红，笑着说：“姑娘，你印堂明亮，今年桃花运可是相当不错哦！说不定还能遇到你的真命天子呢！”

小明一听，顿时火冒三丈：“大师，这也太不公平了吧！我辛辛苦苦攒了一年的 RP（人品），怎么桃花运还不如她？你不会是骗子吧！”

算命先生捋了捋胡须，不慌不忙地说：“小伙子，别急着下结论！你属蛇，今年又是蛇年，可不是巧合哦！你今年的桃花运，正是由‘蛇’字的笔画数决定！不信？你数数看！”

小明挠了挠头，一脸懵逼。小红在一旁捂嘴偷笑，她早就偷偷数过“蛇”字的笔画数了。

现在，请你帮小明算算“蛇”字有多少笔画，揭开他今年桃花运的走向！

输入格式

无。

输出格式

一个整数，表示“蛇”字的笔画数。

2. 打花结【算法赛】

问题描述

打花结是一种中国传统手工艺，也被称为“中国结”或“结绳艺术”。它是一种用绳子编织而成的装饰品，常见于节庆、婚礼、生日等重要场合。打花结的形状多样，有圆形、方形、菱形等，每种形状都有其独特的寓意和象征意义。

小蓝最近得到了 N张矩形花纸。每张花纸的长为 li​ ，宽为wi​ 。小蓝想要从中选取一些花纸来制作打花结，但只有经过若干次折叠操作后使花纸的面积变为 X 的花纸才能用于打花结。

折叠操作如下：

将纸准确对折成一半，形成一条与宽度方向平行的水平对折线，长度减半。

将纸准确对折成一半，形成一条与长度方向平行的垂直对折线，宽度减半。

请你判断每张花纸是否适合打花结，如果适合，则输出 Yes；否则输出 No。

输入格式

第一行输入两个整数 N,X(1≤N≤1000,1≤X≤10000),表示花纸数量。
接下来 N 行，每行输入两个整数 li,wi(1≤li,wi≤100)li​ ,wi​(1≤li​,wi​ ≤100) 表示花纸的长宽。

输出格式

输出 N 行，若第 i张花纸适合打花结则输出 Yes，否则输出 No。

样例输入

3 10
2 5
10 8
3 10

样例输出

Yes
Yes
No

3. 过年【算法赛】

问题描述

蓝桥村的村民们正准备迎接新年。他们计划宰杀 N 头猪，以庆祝一整年的辛勤劳作和丰收。每头猪的初始位置位于下标 x i ，所有 xi​ 均为偶数，保证没有两头猪初始位置相同。

当猪意识到人类打算宰杀它们时，并非束手就擒。它们会主动移动以寻找同伴，遵循以下规则：

每头猪以恒定速率朝着最近的另一头猪移动。若有多头猪距离相同，则选择朝着坐标更小的猪移动。所有猪的移动速度相同。
当两只猪相遇在同一坐标时，它们会融合成一个整体，被视为一头猪。
当所有猪聚集在同一坐标点时停止移动。现在村民们想要确定最终猪群聚集的确切坐标位置，请你帮助解决这个问题。

输入格式

第一行输入一个整数 N(2≤N≤105)N(2≤N≤10 5 ) 表示猪的数量。

第二行输入 N 个整数 x1,x2,⋯,xN(−109≤xi≤109)x 1​ ,x 2,⋯,x N​ (−10 9 ≤x i​ ≤10 9 ) 表示每头猪的坐标，保证 x1,x2,⋯xN;x 1​ ,x 2​ ,⋯x N​ 是偶数，且各不相同。

输出格式

输出一个整数表示答案。

样例输入

5
0 -2 -4 10 2

样例输出

3

4. 喜糖摆放【算法赛】

在过年时，蓝桥村的孩子们充满活力，他们化身为捣蛋鬼，挨家挨户寻讨喜糖。他们一共收到了 N 颗糖，每颗的甜度各不相同，第 i颗糖的甜度为 Ai 。

然而，如何分配这些喜糖却成了一个令人困扰的问题，因为糖的数量不能完全平均分给孩子们。

蓝桥村的村长察觉到了这个困难，于是说道：“我有一个问题，只要你们中有小朋友能解决，我就会提供足够的喜糖，使得你们可以均分。”

问题陈述如下：每次可以选择将任意位置的糖果移到最后，求使得糖果按照升序排列所需的最小操作次数。作为蓝桥村最聪明的孩子之一，你能否尝试解决这个问题呢？

输入格式

第一行输入一个整数 N(2≤N≤105)N(2≤N≤10 5 ) 表示糖果数量。

第二行输入 N 个整数 A1,A2,⋯,AN(1≤Ai≤109)A 1​ ,A 2​ ,⋯,A N​ (1≤A i​ ≤10 9 ) 表示糖果的甜度，数据保证 A1,A2,⋯,AN;A 1​ ,A 2​ ,⋯,A N​ 各不相同。

输出格式

输出一个整数表示答案。

样例输入

5
1 3 2 4 5

样例输出

3

5. 舞狮表演【算法赛】

问题描述

春节期间，舞狮表演是必不可少的节目。今年，小蓝所在的村子也组织了一场盛大的舞狮表演。

村里的广场被划分成了一个n×n 大小的网格。每个格子上都放着一个红包，里面装着不同金额的钱。

为了让表演更加精彩，村长决定设计一条特别的舞狮路线。舞狮队伍需要从左上角的格子出发，一路向下或向右移动，最终到达右下角的格子。

然而，“狮子们”很挑剔，它们只会在装着奇数金额钱的格子上表演。因此，如果格子上装着偶数金额的钱，小蓝就需要在舞狮队伍开始移动前，偷偷地往里面塞钱。但为了不引起围观群众的注意，他每次塞钱，必须给一整行的格子里的红包都塞钱（每个红包塞一块钱）。

现在，小蓝想知道，他最少需要塞多少钱，才能让狮子们顺利地完成表演？如果无论如何也无法让狮子们完成表演，则输出 NO!。

输入格式

第一行包含一个整数 t (1≤t≤102)(1≤t≤10 2 )，表示测试用例的数量。

每个测试用例的第一行包含一个正整数 （1≤n≤1031≤n≤10 3 ），表示广场网格的大小。

接下来的 n 行，每行包含 n 个整数 ai,ja i,j​ （1≤ai,j​(下标)≤1051≤a i,j​(下标) ≤10 5 ），表示对应格子的红包金额。

数据保证输入的所有的 n 2 的总和不超过 10 6 。

输出格式

对于每个测试用例，输出一行。如果可以完成表演，输出一个整数，表示小蓝最少需要塞多少钱；否则输出 NO!。

样例输入

2
2
1 1
2 2
3
1 2 3
4 5 6
7 8 9

样例输出

2
NO!

6. 知识考量码【算法赛】

问题描述

爆竹声中一岁除，春风送暖入屠苏。春节将至，家家户户都沉浸在筹备节日的欢乐氛围中，小蓝家也不例外。今年，小蓝负责设计猜灯谜游戏，他要准备
N
N 个灯谜，并为每个灯谜都标上一个“知识考量码”。

“知识考量码”由一个整数表示，范围在0∼K 之间。该整数的二进制表示中，每一位对应一个特定的知识点。若某位为 1，则该灯谜考查相应的知识点；若为 0，则不考查。

为让玩家能循序渐进地参与游戏，后一个灯谜考查的知识点需包含前一个灯谜的所有知识点。

例如，第一个灯谜的“知识考量码”为 3（二进制是 011），考查第 1 个和第 2 个知识点；第二个灯谜的“知识考量码”为 7（二进制是 111），考查第 1、2、3 个知识点。由于第二个灯谜涵盖了第一个灯谜的所有知识点，所以符合要求。但如果，第二个灯谜“知识考量码”为 5（二进制是 101），即考察了第 1 和第 3 个知识点 。则由于第二个灯谜未涵盖了第一个的所有知识点，所以不符合要求。

现在，小蓝想知道满足上述条件的“知识考量码”序列有多少种不同组合（只要有一个灯谜的“知识考量码”不同，就视为不同序列）。由于方案数可能极大，你只需计算出方案数除以 109+7的余数并告知小蓝即可。

输入格式

第一行包含两个整数 N（2≤N≤109） 和 K（1≤K≤109），分别表示灯谜的数量和知识考量码的最大值。

输出格式

输出一个整数，表示满足条件的灯谜“知识考量码”序列的不同组合数，结果对 10 9 +7 取余。

样例输入

2 3

样例输出

9

样例说明

满足条件的序列组合有：[0,0]，[0,1]，[0,2]，[0,3]，[1,1]，[1,3]，[2,2]，[2,3]，[3,3]。