0907 第 18 场 小白入门赛/强者挑战赛

• 小白入门赛：https://www.lanqiao.cn/oj-contest/newbie-18/
• 强者挑战赛：https://www.lanqiao.cn/oj-contest/senior-18/
• 题解回放：https://www.bilibili.com/video/BV1EJpLeREp8/

T1. 武松打病猫【算法赛】

问题描述

武松打虎那可是家喻户晓，可谁能想到，最近这事却被人给揭了老底。原来，武松打的根本不是老虎，而是一只病猫？！

武松本人不好意思承认，便偷偷找了鲁智深商量对策。

鲁智深听完，哈哈大笑：“武二郎啊武二郎，你可真行，打了只病猫还到处吹牛。人家猫可有 $9$ 条命，你也就打掉 $1$ 条，剩下的命可还多着呢！”

武松苦着脸：“那你说说，还剩几条？”

鲁智深摸了摸光头，笑道：“你自己算算不就知道了？”

现在，请你帮武松算算，那只病猫剩下的命数是多少。

输入格式

无。

输出格式

输出一个整数，表示答案。

T2. 情报传递 1【算法赛】

问题描述

请注意：本题与情报传递 $2$ 的区别仅在于测试数据数量与数据范围不同。

在北宋末年的乱世，梁山泊的好汉们经常要穿梭于各地，传递情报和策划行动。一天，智多星吴用接到了一项紧急任务，需要派遣鲁智深从一个编号为 $a$ 的城市出发，前往编号为 $b$ 的城市，以商讨与盟友的下一步行动。

然而，朝廷已经在沿途布下了天罗地网，凡是编号为 $c$ 的倍数的城市都设有重重哨卡，一旦经过这些城市，梁山的行踪就会被朝廷发现，后果不堪设想。因此，鲁智深在赶往 $b$ 号城市的路上，必须避开这些编号为 $c$ 倍数的城市。

每次，鲁智深可以选择沿着大道前进，假设当前鲁智深在 $x$ 号城市，那么经过一天徒步他可以到达 $x+1$ 或 $x+2$ 号城市 ，但无论如何都不能进入那些危险的城市。为了万无一失，吴用需要设计出一条最安全且最短的路径，让鲁智深能以最少的步数到达 $b$ 号城市。

现在，请你帮助吴用计算：鲁智深最少需要多少天，才能从 $a$ 号城市安全抵达 $b$ 号城市？

输入格式

第一行输入一个整数 $t(t=1)$ 表示测试数据的数量。

接下来 $t$ 行，每行包括三个整数 $a,b,c(1 \leq a <b \leq 10^5,2 \leq c \leq 10^5)$ 表示一组测试数据。

数据保证 $a,b$ 不为 $c$ 的倍数。

输出格式

输出 $t$ 行，每行一个整数表示答案。

输入样例

1
2 7 3

输出样例

3

说明

对于样例，一种赶路方案为 $2 \rightarrow4 \rightarrow 5 \rightarrow 7$，总共需要 $3$ 天。

T3. 村长分钱【算法赛】

问题描述

那天，宋江在梁山聚义厅中，与众兄弟们正饮酒作乐。喝得正高兴时，武松大步走了进来，手里还提着大碗酒，爽朗说道：“哥哥们！我今日在山下小村遇到一件奇怪的事儿。”

宋江见状，笑道：“兄弟，有啥稀奇事？说来让大家也乐呵乐呵。”

武松放下酒碗，抹了抹嘴巴，道：“我在村子里碰到村长，他拿着一袋银子，愁眉苦脸。说是想把这些银子分给村民，但不知道每人分多少银两合适。”

李逵一听，咧嘴大笑：“嘿！这有啥好犯愁的？村长啥事儿都要愁，难不成是怕银两分不出去？”

武松摇了摇头，解释道：“村里的人口众多，压根不用担心银两分不出去。可是村长有个特别的要求，他希望这些银两能够平均地分给若干村民，每次分的银两数量相同，直到袋里剩下的银两不足以再分一次为止。关键是，他希望最后剩下的银子正好是 $k$ 两，好买点酒喝。”

“这事简单！咱们就设每次分的银两数为$x$，只要满足 $n$ 除以 $x$ 后的余数为 $k$，不就找到了一个合适的 $x$、确定了每人分多少银两合适了嘛？！”

“对，对的！兄弟所言极是。这样吧，咱大伙一起来来算算，一共有多少个不同的 $x$，满足 $n$ 除以 $x$ 的余数为 $k$。” 宋江提议道。

众好汉们纷纷点头。

现在，请你和众好汉一起，算算满足条件的 $x$ 的个数。注意，$x$ 必须是正整数，且 $x$ 不能大于 $n$。

输入格式

输入一行，包含两个整数 $n$（$1\leq n \leq 10^9$） 和 $k$（$0 \leq k < n$），其中 $n$ 为村长手中的银子总数，$k$ 是希望剩下的银子数量。

输出格式

输出一个整数，表示满足条件的不同的 $x$ 的个数。

样例输入

13 3

样例输出

2

样例说明

满足条件的 $x$ 有 $5$、$10$，共 $2$ 个。

T4. 情报传递 2【算法赛】

问题描述

请注意：本题与情报传递 $1$ 的区别仅在于测试数据数量与数据范围不同。

在北宋末年的乱世，梁山泊的好汉们经常要穿梭于各地，传递情报和策划行动。一天，智多星吴用接到了一项紧急任务，需要派遣鲁智深从一个编号为 $a$ 的城市出发，前往编号为 $b$ 的城市，以商讨与盟友的下一步行动。

然而，朝廷已经在沿途布下了天罗地网，凡是编号为 $c$ 的倍数的城市都设有重重哨卡，一旦经过这些城市，梁山的行踪就会被朝廷发现，后果不堪设想。因此，鲁智深在赶往 $b$ 号城市的路上，必须避开这些编号为 $c$ 倍数的城市。

每次，鲁智深可以选择沿着大道前进，假设当前鲁智深在 $x$ 号城市，那么经过一天徒步他可以到达 $x+1$ 或 $x+2$ 号城市 ，但无论如何都不能进入那些危险的城市。为了万无一失，吴用需要设计出一条最安全且最短的路径，让鲁智深能以最少的步数到达 $b$ 号城市。

现在，请你帮助吴用计算：鲁智深最少需要多少天，才能从 $a$ 号城市安全抵达 $b$ 号城市？

输入格式

第一行输入一个整数 $t(1 \leq t \leq 10^5)$ 表示测试数据的数量。

接下来 $t$ 行，每行包括三个整数 $a,b,c(1 \leq a <b \leq 10^9,2 \leq c \leq 10^9)$ 表示一组测试数据。

数据保证 $a,b$ 不为 $c$ 的倍数。

输出格式

输出 $t$ 行，每行一个整数表示答案。

输入样例

1
2 7 3

输出样例

3

说明

对于样例，一种赶路方案为 $2 \rightarrow4 \rightarrow 5 \rightarrow 7$，总共需要 $3$ 天。

T5. 好汉身份【算法赛】

问题描述

当梁山迎来了新的一批好汉加入时，宋江哥哥决定要给各位兄弟改善一下伙食，便派了“智多星”吴用下山采购。

吴用来到山下一看，好巧不巧，正好赶上一年一度的梁山跳蚤市场开市。他们发现市场上共有 $2N$ 件商品，这第 $i$ 件商品，若是寻常百姓购买，需花费 $a_i$ 两银子；可若是梁山好汉亮出身份，那店家便会给出一个“梁山好汉价”，需花费 $b_i$ 两银子。

回到山上，吴用将此事告知了宋江。宋江听罢，哈哈大笑，说道：“妙啊！咱们来玩个游戏！我扮作寻常百姓，吴军师你亮出身份，咱们比试一番，看看最后谁花的银子少！”

于是，宋江摇身一变，换上了一身寻常百姓的衣裳，只带了一顶普通的帽子，遮住了他那标志性的红脸膛，便大摇大摆地混进了熙熙攘攘的跳蚤市场。而吴学究则摇着羽扇，施施然地来到了市场，准备和宋江来一场斗智斗勇的比拼。

他们定下规矩：双方轮流购买商品，宋江先出手，吴用后出手，直到所有商品都被买走为止。设宋江最终花费了 $X$ 两银子，而吴用最终花费了 $Y$ 两银子。宋江试图最小化 $X - Y$，而吴用试图最大化 $X - Y$。

现在，请你计算，当双方都采取最优策略时，$X - Y$ 的值会是多少。

输入格式

第一行一个整数 $n$（$1\leq n \leq 10^3$），表示共有 $2n$ 件商品。

第二行 $2n$ 个整数，$a_1,a_2,\cdots,a_{2n}$（$1\leq a_i \leq 10^9$），其中 $a_i$ 表示第 $i$ 件商品的“寻常百姓价”。

第三行 $2n$ 个整数，$b_1,b_2,\cdots,b_{2n}$（$1\leq b_i \leq 10^9$），其中 $b_i$ 表示第 $i$ 件商品的“梁山好汉价”。

输出格式

输出一行一个整数，表示答案。

样例输入

1
3 1
4 2

样例输出

-3

样例说明

宋江可以先手选择第 $2$ 件商品，花费 $1$ 两银子。此时吴用只能选择第 $1$ 件商品，花费 $4$ 两银子。两者的差值为 $-3$。

T6. 武功秘籍【算法赛】

问题描述

神行太保戴宗获得了一本武功秘籍，据说练成之后可以日行千里，夜走八百。戴宗正想找个僻静的地方修炼一番，却发现修炼它需要用到一种特殊的数字，叫做“梁山数”。这“梁山数”，和平常的数字不太一样，它的每个数位上的数字都有个上限，超过了就不行。比如，个位数上限是 $5$，十位数上限是 $3$，百位上限是 $1$，那么最大的三位“梁山数”就是 $135$。

想修炼好这门神功，就需要先找到第 $k$ 小的“梁山数”。但是，这可难倒了戴宗，于是，他急忙找到浪子燕青，将事情的来龙去脉告诉了他，并请他帮忙计算出第 $k$ 小的“梁山数”。

燕青看了看，心想这“梁山数”虽然奇怪，但也不过是换了一种计数方式而已，本质上还是数字，于是便答应下来。戴宗给了燕青每个数位上的上限值，用一个整数 $n$ 表示，$n$ 的第 $i$ 位数字 $n_i$ 表示“梁山数”从右往左数第 $i$ 位上的最大值。

现在，请你协助燕青，解决这个问题。

输入格式

输入一行，包含两个整数 $n,k$（$1\leq n,k \leq 10^{18}$），分别表示每个数位的最大值、需要找的“梁山数”的序号。

保证数据合法。

输出格式

输出一个整数，表示第 $k$ 小的“梁山数”。

样例输入

135 8

样例输出

11

样例说明

当 $n = 135$ 时，所有的‘梁山数’从小到大排列是：$0, 1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15, 20, 21, ...$，其中第 $8$ 小的是 $11$。

T7. 朝廷查账【算法赛】

问题描述

“哥哥！不好啦！出大事啦！”

只见小弟慌慌张张地跑进聚义厅，满头大汗，上气不接下气。

“慌什么慌！没看到哥哥我正在喝酒吗？天塌下来了，也有哥哥我顶着！”

“哥哥，是账目的事！咱们山寨的账目 $A$ 和朝廷送来的账目 $B$ 对不上号啦！”

“什么？！这可是大事！快说说，怎么回事？”

“哥哥，是这样的。咱们山寨的账目 $A$ 和朝廷送来的账目 $B$，都记录了 $10^{99999}$ 条金银交易记录，每条记录都对应着一个数字，代表了交易的数额。账目 $A$ 中第 $i$ 笔记录的数字表示为 $A_i$。账目 $B$ 中第 $i$ 笔记录的数字表示为 $B_i$。但是，咱们山寨的账目 $A$ ，只有前 $a$ 笔记录是有数的，后面的都还没来得及记，所以都是 $0$。朝廷送来的账目 $B$ 也是，只有前 $b$ 笔记录是有数的，后面的也都是 $0$。”

“这有什么奇怪的？咱们山寨和朝廷做的买卖本来就多，有些还没来得及记也很正常嘛！”

“可是哥哥，这两本账目，就算把已经记好的那些数进行比对，也好像对不上啊？！朝廷那边说，咱们要是不能把账目对上，就要派兵来剿咱们了！”

“什么？！岂有此理！这帮官兵，分明是来找茬的！看来，只能先礼后兵了！小弟，你去把军师请来！”

“是，哥哥！”

不多时，军师便来到了聚义厅。

“军师，你快看看，这账目到底是怎么回事？能不能想办法，把它们对上？”

军师仔细地看了看账目，又沉思了片刻，说道：“哥哥，这两本账目，虽然乍一看对不上，但也不是完全没有办法。我们可以用两种方法来调整账目上的数字：”

1. “从账目 $A$ 中任选三笔不同的记录，设它们的编号分别是 $p,q,r$（$1 \le p, q, r \le 10^{99999}$），然后把第 $r$ 笔记录的数 $A_r$ 改为第 $p$ 笔和第 $q$ 笔记录的数之和，即 $A_r = A_p + A_q$。”
2. “从账目 $A$ 中任选三笔不同的记录，设它们的编号分别是 $p,q,r$（$1 \le p, q, r \le 10^{99999}$），然后把第 $r$ 笔记录的数 $A_r$ 改为第 $p$ 笔和第 $q$ 笔记录的数之差，即 $A_r = A_p - A_q$。”

“军师，你的意思是，只要用这两种方法，就能把账目 $A$ 调整成和账目 $B$ 一模一样吗？”

“不一定，我得仔细算算才能知道。”

现在，请你帮军师算一算，经过若干次（可以是 $0$ 次）的调整，这两本账目能不能一模一样。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试数据的组数。

接下来是 $t$ 组测试数据，每组数据的格式如下：

• 第一行包含两个整数 $a$ 和 $b$（$1 \le a, b \le 10^5$），分别表示账目 $A$ 和 $B$ 中已经记录的数的个数。
• 第二行包含 $a$ 个整数 $A_1, A_2, \dots , A_a$（$1\leq A_i \leq 10^9$），表示账目 $A$ 中前 $a$ 笔记录的数。
• 第三行包含 $b$ 个整数 $B_1, B_2, \dots, B_b$（$1\leq B_i \leq 10^9$），表示账目 $B$ 中前 $b$ 笔记录的数。

保证在所有的测试数据中，$a$ 和 $b$ 的总和不超过 $2\times 10^5$。

输出格式

对于每组测试数据，如果能将账目 $A$ 调整成和账目 $B$ 一致，则输出 YES，否则输出 NO。

样例输入

2
2 2
1 1
1 2
2 1
2 4
3

样例输出

YES
NO

样例说明

对于第一组数据，起初：

$$A = [1, 1, 0, 0, 0, \cdots]$$

选择 $r = 3, q = 1,p =2$，令 $A_3 = A_1 + A_2$：

$$A = [1, 1, 1, 0, 0, \cdots]$$

选择 $r = 2,q=1,p=3$，令 $A_2 = A_1 + A_3$：

$$A = [1, 2, 1, 0, 0, \cdots]$$

选择 $r = 3, q = 4, p = 5$，令 $A_3 = A_4 + A_5$：

$$A = [1, 2, 0, 0, 0, \cdots]$$

此时，$A = B$，输出 YES。

对于第二组数据，无论如何调整，也无法使 $A = B$，因此输出 NO。

T8. 晁盖分饼【算法赛】

问题描述

在梁山泊的一次盛大聚会上，晁盖为了庆祝诸位英雄好汉的勇猛，特意准备了一块巨大的圆形烧饼。这块烧饼需要被分配给参加聚会的 $k$ 名好汉，每位好汉都应分得一份。

晁盖大手一挥，对着各位兄弟说道：“兄弟们，今天这块烧饼，咱们要分而食之，以庆祝咱们的义气！”

李逵一听，顿时来了兴致，嚷嚷道：“哥哥，这烧饼怎么分？俺要吃最大的那块！”

晁盖笑着说：“放心，少不了你的。咱们按规矩来，每个人分到的烧饼份额，都用一个整数来表示，这个整数至少是 $1$，最大不超过 $n$。比方说，如果谁的烧饼份额为 $2$，那么他将会分得整张烧饼的 $\frac{1}{2}$；如果谁的烧饼份额为 $3$，那么他将会分得整张烧饼的 $\frac{1}{3}$！”

吴用摇着羽扇，补充道：“哥哥，这烧饼得正好分完才行！如果只有两个人分烧饼，一个人分到了 $\frac{1}{3}$ 的烧饼，另一个人分到了 $\frac{1}{2}$ 的烧饼，那这烧饼就还剩下 $\frac{1}{6}$ 没分完，这就不好了，咱可不能浪费啊！”

晁盖点点头：“军师说得对，这饼一定要正正好好的分完，不能有剩下的。现在，我想问问各位兄弟，你们谁能算出来，有多少种不同的分饼的方法，能够把这块饼正好分给在座的 $k$ 位兄弟，且每个人分到的饼的份额都是 $1$ 到 $n$ 之间的整数？”

不同的分饼方法定义为：如果在两种分饼方法中，至少有一个好汉获得的份额不同，则视为不同的分饼方法。

例如，当 $n = 4, k = 3$ 时，$[4, 2, 4]$、$[2, 4, 4]$ 就被视为两种不同的分饼方法。

• $[4,2,4]$：第一个好汉分得整张烧饼的 $\dfrac{1}{4}$，第一个好汉分得整张烧饼的 $\dfrac{1}{2}$，第三个好汉分得整张烧饼的 $\dfrac{1}{4}$。

• $[2,4,4]$：第一个好汉分得整张烧饼的 $\dfrac{1}{2}$，第一个好汉分得整张烧饼的 $\dfrac{1}{4}$，第三个好汉分得整张烧饼的 $\dfrac{1}{4}$。

“哥哥，这也太难算了吧！”好汉们纷纷摇头。

“哈哈，不用担心，我已经算过了，答案不会超过 $2^{60}$ 种！”晁盖笑着说。

请你算算有多少种分配烧饼的方式。

输入格式

输入一行包含两个整数 $n$ 和 $k$（$1\leq k \leq n \leq 24$），表示每位好汉的最大分饼份额 $n$ 和参加聚会的好汉的数量 $k$。

输出格式

输出一个整数，表示有多少种不同的分配烧饼的方式。

样例输入

4 3

样例输出

4

样例说明

分饼方法有以下 $4$ 种：

• $[3, 3,3]$：第一个好汉分得整张烧饼的 $\dfrac{1}{3}$，第一个好汉分得整张烧饼的 $\dfrac{1}{3}$，第三个好汉分得整张烧饼的 $\dfrac{1}{3}$。

• $[2,4,4]$：第一个好汉分得整张烧饼的 $\dfrac{1}{2}$，第一个好汉分得整张烧饼的 $\dfrac{1}{4}$，第三个好汉分得整张烧饼的 $\dfrac{1}{4}$。

• $[4,2,4]$：第一个好汉分得整张烧饼的 $\dfrac{1}{4}$，第一个好汉分得整张烧饼的 $\dfrac{1}{2}$，第三个好汉分得整张烧饼的 $\dfrac{1}{4}$。

• $[4,4,2]$：第一个好汉分得整张烧饼的 $\dfrac{1}{4}$，第一个好汉分得整张烧饼的 $\dfrac{1}{4}$，第三个好汉分得整张烧饼的 $\dfrac{1}{2}$。

T9. 酒量争霸赛【算法赛】

问题描述

话说在梁山水泊，宋江大哥为了让兄弟们在酒桌上比出个高下，决定来一场“酒量争霸赛”。这场比赛不比拳脚功夫，只比谁能喝得多，喝得久。

于是，$n$ 个好汉齐聚一堂，各个摩拳擦掌，准备展示自己的酒量。宋江大哥发话：“每位兄弟上场前，按照顺序报报自己的酒量，让大家心里有个数。” 于是，兄弟们依次按顺序报上了自己的初始酒量：$a_1, a_2, \ldots, a_n$。

接着，宋江大哥详细讲起了比赛的规则：

1. 每一轮开始前，所有兄弟先计算一下“累计酒量”，也就是这轮每个人要喝的酒量。具体来说，第 $i$ 个人这轮要喝的酒量 $b_i$ 是前面所有人的酒量之和：

   $$b_i = a_1 + a_2 + \cdots + a_i$$

   这就意味着，越靠后的兄弟，这轮得喝的酒越多！

2. 喝完这一轮后，最靠前的的那位兄弟会被淘汰出局（即序列 $b$ 的第一个元素）。

3. 剩下的兄弟们继续喝下一轮。在下一轮中，大家的酒量数据在每轮结束后会更新成上一轮的累计酒量（即上一轮计算出来的累计酒量 $b$ 会成为下一轮的初始酒量 $a$）。接着，大家再重新计算各自这一轮要喝的酒量。

4. 如此这般，每轮淘汰掉一个兄弟，直到最后只剩下一位能喝的“酒霸”。

宋江大哥笑着说：“这位酒霸的最终酒量，也不知道会是多少。”

对此，请你计算，经过一轮轮“喝酒淘汰赛”，最终那位唯一的酒霸，他的酒量对 $10^9 + 7$ 取余会是多少呢？

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 10^5)$，表示好汉的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 10^9)$，表示每位好汉的初始酒量。

输出格式

输出一行，表示最终剩下的酒霸的酒量对 $10^9 + 7$ 取余的结果。

样例输入

3
1 2 3

样例输出

9

样例说明

1. 第一轮：
   • 初始酒量：$a = [1, 2, 3]$
   • 累计酒量：$b = [1, 3, 6]$
   • 淘汰第一个：$1$
2. 第二轮：
   • 更新酒量：$a = [3, 6]$
   • 累计酒量：$b = [3, 9]$
   • 淘汰第一个：$3$
3. 第三轮：
   • 更新酒量：$a = [9]$
   • 只有一人，结束。

最终酒霸的酒量为 $9$，输出结果为 $9$。