题目信息
-
题目类型
-
练习
-
题目年份
-
2025
-
题目题型
-
编程题
-
关 键 词
-
今晚吃花
题目题干
- 描述
- 我们之前看到了Marmot为Mole的午餐准备的小游戏。现在到了晚饭时间，我们都知道Marmot喜欢吃花，每一顿晚饭他都会吃一些红花和白花。因此一顿晚饭可以被表示成一个花朵的序列。mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
Mole打算准备一顿可口的晚餐，但是Marmot有个神奇的能力：Marmot可以吃连续的数量为 k 的白花，并且被Marmot吃过的白花就会变成红花。形式化的，一顿晚饭是 01 字符串，0 代表红花，1 代表白花，即当一个字符串内如果存在连续 k 个 1 的子串，Marmot能将该子串变为 k 个 0。mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
Marmot还有一个奇怪的习惯，当Marmot吃了若干次连续的数量为 k 的白花后，他希望他的晚饭此时只剩下红花。mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
现在Mole想知道从哪一种晚饭最合适Marmot的胃口，于是她会向你提问 q 次，每次询问给定两个整数 l 和 r，你需要找到在所有花朵数量为 x (l ≤ x ≤ r) 的晚饭中，有多少种晚饭是符合Marmot习惯的。你需要将答案对 109 + 7 取模。
- 输入
- 第一行包含两个正整数 q, k，含义如题。mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
接下来 q 行，每行包含2个整数代表该次询问的 l,r。
- 输出
- 输出 q 行，每行一个整数表示在所有花朵数量为 x(l ≤ x ≤ r) 的晚饭中，有多少种晚饭是符合Marmot习惯的。
- 样例输入
-
【输入#1】
3 2
1 3
2 3
4 4
- 样例输出
-
【输出#1】
6
5
5
- 提示
- 【解释#1】mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
Marmot每次能将连续2朵白花变为红花。mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
当晚饭为1朵花时，Marmot仅能吃{红}。mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
当晚饭为2朵花时，Marmot能吃{红红}，{白白}。mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
当晚饭为3朵花时，Marmot能吃{红红红}，{红白白}，{白白红}。mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
当晚饭为4朵花时，Marmot能吃{红红红红}，{红白白红}，{白白红红}，{红红白白}，{白白白白}。但是他不能吃{白白白红}，因为他无论如何吃，都不能在吃完后晚饭只剩下红花。mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于第一个询问，在晚饭的花朵数量在1朵到3朵之间时，有6种符合Marmot习惯的晚饭。mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【数据范围】mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于 10% 的数据，q = 1, r < 20；mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于 30% 的数据，q ≤ 100, r < 20；mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
额外有 10% 的数据，q = 1, l = r；mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
额外有 20% 的数据，q = 10^5, l = r；mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
mQD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于 100% 的数据，1 ≤ q,k ≤ 10^5, 1 ≤ l ≤ r ≤ 10^5。
答案解析
相关题目
-
Shaass的书架描述 Shaass有 n 本书。他想把所有的书摆在一个书架上。他希望书架的尺寸越小越好。已知第 i 本书的厚度为 ti，宽度等于 wi。所有书的高度都相同。 Shaass按照以下
-
今晚吃花描述 我们之前看到了Marmot为Mole的午餐准备的小游戏。现在到了晚饭时间，我们都知道Marmot喜欢吃花，每一顿晚饭他都会吃一些红花和白花。因此一顿晚饭可以被表示成一个花朵的序列。 M
-
采果子描述 Bessie 和她的妹妹 Elsie 正在 Farmer John 的浆果园里采浆果。Farmer John 的浆果园里有 N 棵浆果树（1≤N≤1000）；第 i 棵树上有 Bi 个浆果
-
移球游戏描述 有 N 个球从左到右摆成一排。每个球上都有一个数字，初始时，从左数第 i 个球上的数字恰好为 i。 小明依次进行 Q 次操作，第 i (1<=i<=Q) 次操作为： 将写
-
砝码称重描述 你有一架天平和N个砝码，这N个砝码重量依次是W1, W2, ... WN。 请你计算一共可以称出多少种不同的重量？ 注意砝码可以放在天平2边。只统计大于0的重量。 输入 第一行包含一个
-
单调数组描述 给定一个长度为 n 的整数数组 A=[A1,A2,...,An]。 你可以进行至多一次如下操作： 选择整数 i (1 ≤ i < n)，并将 A1,A2,...Ai 移动至最右
-
掷骰子描述 小明是个掷骰子爱好者。有一天他碰到了这么一个问题： 有一枚 6 个面的骰子，分别写了 1, 2, 3, 4, 5, 6 ，每一面朝上的概率是均等的。 现在小明想知道，如果他投掷 n 次
-
最小ASCII删除和描述 给定两个字符串S和T，你可以从两个字符串中删除若干个字符，目标是使得剩余两个字符串相等（都是空串也算相等）。 代价是删除的字符的ASCII值之和。 请输出最小的代价是多少
-
最低等级通关描述 小Hi在玩一款电子游戏，他现在处于一座由NxN个方块区域组成的迷宫中。小Hi开始时位于左上角的区域，他只能向右或者向下移动，而要通关必须移动到右下角的方格区域。 每个方格区域都标记
-
合唱队形描述 N 位同学站成一排，音乐老师要请其中的 (N-K) 位同学出列，使得剩下的 K 位同学排成合唱队形。 合唱队形是指这样的一种队形：设 K 位同学从左到右依次编号为 1, 2, …, K
提示声明
- 免责声明：本站资源均来自网络或者用户投稿，仅供用于学习和交流：如有侵权联系删除!
- 温馨提示：本文属于积分文章，需要充值获得积分或升级VIP会员，也可在会员中心投稿获取。
猜你喜欢
Scratch3.0
全国青少年软件编程等级考试
Python
Scratch图形化一级
Scratch图形化四级
Scratch图形化三级
Scratch图形化二级
电子学会
