有无难度 or 做法鉴赏
2026-10-03 18:09:13
发布于:湖北
求大致难度以及做法
T827753 [模拟赛 #1] 百鸟朝凤
题目描述
群鸟和鸣,百鸟来朝。为了迎接凤凰,山林中的鸟儿正在演练朝凤阵列。
山林中有 群鸟从左到右依次排列。我们用一个正整数序列 表示当前的鸟群排列,其中第 个数 表示从左到右第 群鸟的数量。我们称这样的序列为一个鸟群序列。初始鸟群序列为 。
你可以按任意顺序指挥鸟群进行若干次合并。每次操作可以选择当前鸟群序列中两个相邻且鸟数相同的鸟群,将它们合并为一群,合并后的鸟数为原来两群鸟数之和,其余鸟群的相对顺序保持不变。例如,鸟群序列 可以经过一次合并变为 ,还可以继续合并为 。每进行一次合并,鸟群序列的长度减少 。你可以进行任意次合并,也可以一次都不合并。
从初始鸟群序列出发,通过若干次合并,可以得到若干种不同的鸟群序列。同一个鸟群序列可能由不同的合并顺序得到,但只计算一次。两个鸟群序列相同,当且仅当它们的长度相同,并且对应位置上的鸟数全部相同;否则认为它们不同。
请你求出,从初始鸟群序列出发,一共能够得到多少种不同的鸟群序列。由于答案可能很大,请输出答案对 取模后的结果。
输入格式
第一行一个正整数 ,表示初始鸟群序列的长度。
第二行 个正整数 ,依次表示初始鸟群序列中从左到右各群鸟的鸟数,相邻两个数之间用一个空格隔开。
输出格式
输出一行一个整数,表示能够得到的不同鸟群序列的数量对 取模后的结果。
输入输出样例 #1
输入 #1
1 6
1 1 1 1 1 1
输出 #1
18
输入输出样例 #2
输入 #2
15
2 3 3 6 1 1 2 4 4 4 4 8 5 5 5 5
输出 #2
522
输入输出样例 #3
输入 #3
见下发文件
输出 #3
输入输出样例 #4
输入 #4
见下发文件
输出 #4
说明/提示
样例解释
样例 1 解释
下图给出了从初始鸟群序列 出发能够得到的鸟群序列,以及其中的部分合并关系:

包括初始序列本身在内,共可得到 种不同的鸟群序列。
数据规模与限制
对于 的数据,。
对于另外 的数据,。
对于另外 的数据,所有 相等。
对于另外 的数据,所有 均为 的非负整数次幂。
对于 的数据,,。
T827752 [模拟赛 #1] 卡农
题目描述
在卡农中,一个声部奏出旋律后,其他声部会按一定规则依次模仿并与之呼应。为了记录一首特殊作品中各段旋律的演奏次序,乐谱采用了一棵满二叉树来组织这些音符。
这棵树的高度为 ,共有 个结点。结点编号为 ,其中 号结点为根。对于每个非叶结点 ,它的左儿子为 ,右儿子为 。
每个结点上放着一个用正整数表示的音符。设结点 上的音符为 ,保证 恰好构成 的一个排列。
演奏时,音符按照这棵树的中序遍历顺序依次奏出:对于任意结点 ,先演奏它左子树中的所有音符,再演奏结点 上的音符,最后演奏它右子树中的所有音符。

图:以 为例:结点上的音符与中序遍历
如果最终听到的音符依次恰好为 ,则称这次演奏是完美的。
为了调整各段旋律的先后次序,你可以对任意非叶结点 进行一次调整:交换结点 的整棵左子树和整棵右子树。进行这次调整需要付出 的代价。
排练过程中,乐谱会发生 次修改。每次修改给出两个结点 ,交换这两个结点上的音符(并不交换结点本身)。每次修改都会永久保留,并影响之后的修改。
在每次修改之后,请你求出:至少需要付出多少总代价,才能通过若干次调整使演奏变得完美。如果无论怎样调整都无法得到完美的演奏,输出 。
注意,调整仅用于计算当前这次修改后的答案,不会保留到之后的修改中。处理下一次修改时,树的左右儿子关系恢复为初始状态,仅此前对结点上音符的修改会保留。
输入格式
第一行两个整数 ,分别表示树的高度和修改次数。
第二行 个整数 ,其中 表示初始时结点 上的音符。
第三行 个整数 ,其中 表示对非叶结点 进行一次调整的代价。当 时,这一行为空行。
接下来 行,每行两个整数 ,表示一次修改:交换结点 与结点 上的音符。 可能等于 。
输出格式
输出 行,第 行一个整数,表示第 次修改之后使演奏变得完美所需的最小总代价;若无法使演奏变得完美,输出 。
输入输出样例 #1
输入 #1
4 3
8 12 4 10 14 6 2 9 11 15 13 5 7 1 3
5 3 8 2 6 4 7
8 9
10 11
2 3
输出 #1
21
15
-1
输入输出样例 #2
输入 #2
见下发文件
输出 #2
输入输出样例 #3
输入 #3
见下发文件
输出 #3
输入输出样例 #4
输入 #4
见下发文件
输出 #4
说明/提示
样例解释
样例 1 解释
树高 ,共 个结点,非叶结点为 。下图每一行对应一次修改:左侧为修改后的乐谱,右侧为进行调整后的结果。圆内的数字为结点上的音符,圆下方的数字为结点编号;加粗的结点及音符为本次修改中交换的音符所在位置,灰色的结点为需要调整的结点。

图:样例 1 中各次修改及调整后的乐谱
- 第 次修改交换结点 上的音符。此时调整结点 即可使演奏变得完美,总代价为 ,输出 。
- 第 次修改交换结点 上的音符。此时调整结点 即可,总代价为 ,输出 。
- 第 次修改交换结点 上的音符。此时无论怎样调整,都无法使演奏变得完美,输出 。
样例 2 解释
该组样例满足 ,。
样例 3 解释
该组样例满足 ,,且每次修改中 与 至少有一个等于 。
样例 4 解释
该组样例满足 ,。
数据规模与限制
对于 的数据,,。
对于另外 的数据,,。
对于另外 的数据,所有 相等。
对于另外 的数据,每次修改中 与 至少有一个等于 。
对于 的数据,,,,。
全部评论 9
T1的话,我的思路是进行dp,dp[i]的定义为前 i 个数的方案数,再维护一个邻接表l表示这一位可合并的区间左下标。转移: , 至于去重......(
本人刚过七级,这着实有点难)这里应该是一个渐进时间复杂度T2我感觉要先建一个二分搜索树,再对比一下原本的满二叉树,用贪心的方法求出在修改以前的总值(对于每一个点,找到他的父节点,与他父节点的子树交换)。
对于每一次修改,我们先将两点直接交换,对比交换的两点在二分搜索树可能出现的情况:
1)交换之后两个点都到了应该到的地方,此时总值-2 ;
2)交换之后有一个点到了应该到的地方,另一个点任然不匹配,此时总值-1;
3)交换之后有一个点到了应该到的地方,另一个点原本匹配而现在不匹配,此时总值不变。
4)交换之后两个点都由匹配变成不匹配,此时总值+2 ;
5)交换之后有一个值原本匹配而现在不匹配,另一个值任然不匹配,此时总值+1 。
这样的话时间复杂度应该是O(n \log \n \+ \q) .
我还只是一个刚过七级的小学生,恳求大佬给点意见2天前 来自 浙江
1dsa
2天前 来自 广东
0dsa,但是 T2 是树形 dp。我看过题目讲解了但还是 thx
2天前 来自 湖北
0
2
2天前 来自 浙江
0这妈的能发吗
3天前 来自 湖北
0kkk 又不在 ACGO 怕啥
3天前 来自 安徽
0( orz
3天前 来自 湖北
0我咋到安徽了
3天前 来自 安徽
0
我直接把题给你偷走了(
3天前 来自 湖北
0T1的口胡(
对于每个点位 维护所有以 结尾的可合并后缀,用这些后缀的起始位置 做转移、
转移推了一个 、3天前 来自 上海
0thx
3天前 来自 湖北
0大神啊
3天前 来自 广东
0
使唤了一下 AI,AI 钦定是蓝紫,我认为 AI 做法是青蓝
3天前 来自 广东
0问的是DS吗,DS难度会高一档
3天前 来自 广东
0是 ds
3天前 来自 广东
0感觉是刚好高一档的样子
3天前 来自 广东
0
鉴赏了一下T1发现是DP,然后不会了、
3天前 来自 上海
0欸卧槽是不是可以对于每个点位 考虑对于 中的后缀能不能凑出合并,中间枚举断点🤔
3天前 来自 上海
0合并鸟群(
3天前 来自 湖北
0、
3天前 来自 上海
0
T1就放我不会的
3天前 来自 广东
0/jk
3天前 来自 广东
0那我更不会了
3天前 来自 广东
0这是 T4(
3天前 来自 湖北
0
d
3天前 来自 湖北
0






































有帮助,赞一个