Summary6

$BO\sim BT$

BO 钓鱼题

时间限制：1000ms 内存限制：65536kb

通过率：470/534 (88.01%) 正确率：470/895 (52.51%)

题目背景

Ender_hzEnder_hz 遇到了这样一套钓鱼题，但是他太弱了，于是来请教了会程设的你。请你帮他完成这套题目。

题目描述

Ender_hzEnder_hz 拿到的题目是这样的：

1. 这道题的答案是：
   A. $A$ B. $B$ C. $C$ D. $D$
2. 第 55 题的答案是：
   A. $C$ B. $D$ C. $A$ D. $B$
3. 以下选项中哪一题的答案与其他三项不同：
   A. 第 $3$ 题 B. 第 $6$ 题 C. 第 $2$ 题 D. 第 $4$ 题
4. 以下选项中哪两题的答案相同：
   A. 第 $1,5$ 题 B. 第 $2,7$ 题 C. 第 $1,9$ 题 D. 第 $6,10$ 题
5. 以下选项中哪一题的答案与本题相同：
   A. 第 $8$ 题 B. 第 $4$ 题 C. 第 $9$ 题 D. 第 $7$ 题
6. 以下选项中哪两题的答案与第 88 题相同：
   A. 第 $2,4$ 题 B. 第 $1,6$ 题 C. 第 $3,10$ 题 D. 第 $5,9$ 题
7. 在此十道题中，被选中次数最少的选项字母为：
   A. $C$ B. $B$ C. $A$ D. $D$
8. 以下选项中哪一题的答案与第 11 题的答案在字母表中不相邻：
   A. 第 $7$ 题 B. 第 $5$ 题 C. 第 $2$ 题 D. 第 $10$ 题
9. 已知 ⌈⌈第 $1$ 题和第 $6$ 题的答案相同⌋⌋ 与 ⌈⌈第 XX 题和第 $5$ 题的答案相同⌋⌋ 的真假性相反，那么 XX 为：
   A. $6$ B. $10$ C. $2$ D. $9$
10. 在此 $10$ 道题中，$ABCD$ 四个字母出现次数最多与最少者的差为：
    A. $3$ B. $2$ C. $4$ D. $1$

请你用任意方法（抄袭除外）完成这道题并提交答案。

输入

无

输出

一行 $10$ 个大写字母 $a_1a_2…a_{10}$，不含空格，$a_i\in${A,B,C,D}，表示第 $i$ 题的答案。

注意是你的程序 输出 答案，而非直接提交选项！

输出样例

AAAAAAAAAA

Hint

• 输出样例仅供格式参考，不代表真实答案；
• 如果你想，可以试试手算；
• 如果认为某道题的判断难以实现，可以尝试跳过，最后人工核验。

Author: Ender_hzEnder_hz.

Think

网上的一道逻辑题，程序化解决就是对选项节点进行 dfs 暴力搜索

BP 宝石迷阵 (Bejeweled)

时间限制：1000ms 内存限制：65536kb

通过率：4/31 (12.90%) 正确率：4/114 (3.51%)

题目描述

WIKI 最近迷恋上了宝石迷阵, 她给她最好的朋友 NonFriedChips 出了一道题, 做不出来要狠狠惩罚 NonFriedChips

NonFriedChips 不想被 WIKI 狠狠惩罚, 于是她找到了你, 想让你帮她做出来这道题

注意, 玩过宝石迷阵并不会帮助理解题意, 请仔细阅读, 该题和普通三消规则并不相同

现在有 $n$ 个宝石排成一列, 每个宝石有一个颜色 $a$

每次操作都将进行以下两步

1. 选择不在最后的一个宝石 $i$, 且有宝石颜色标号 $a_i=i$
2. 消除该宝石及它紧邻后面的一个宝石, 消除之后后面的宝石将会向前移动与前面部分相连

请求出你最多能操作的次数

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $t (1≤t≤100)$ —— 测试用例的数量。每个测试用例的描述如下：

每个测试用例的第一行包含一个整数 $n (1≤n≤800)$ —— 宝石的数量

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,…,a_n (1≤a_i≤n)$——每个宝石的颜色

保证所有测试用例中的 $n$ 之和不超过 800

输出

对于每个测试用例，输出一个整数 —— 可以执行操作的最大次数。

样例输入

1
5
1 5 3 2 4

样例输出

2

BQ 身高问题（concert）

时间限制：1000ms 内存限制：28672kb

通过率：6/21 (28.57%) 正确率：6/64 (9.38%)

题目描述

日本演唱会门票的售卖方式是先抽后卖，所以如果想要抢到一个好的位置一定不要忘记参与抽选活动哦！由于位置抽选的方式是随机的，可能会在观看演唱会时出现这种情况：前面的人比后面的人高，导致到后面的看不到小绿毛。

同一排上的观众是不会相互遮挡的，所以我们在这里只在意一列长度为 $n$ 的座位。从舞台向外将座位编号为 1,2,…,n1,2,…,n，且这 $n$ 的人的身高是 1,2,…,n1,2,…,n。如果位置 $i$ 的人前面有 aa 个比他要高的人，那么他就会产生 aa 点怒气。对于这 $n$ 个人，一个座位顺序的怒气值 AA 是所有人的怒气和，每个人坐到每个位置的概率是相等的。你坐在 SVIP 座，所以不参与排座，看着他们生气会产生 kA+A2kA+A2 的惬意（什么资本家。。。）。

现在你想知道，对于所有可能的座位顺序，你产生的惬意总和。答案对 109+7109+7 取模。

简要题意：

设 PP 为任意一个 1∼n1∼n 的排列，τ(P)τ(P) 为其中的逆序对个数，求（答案对 109+7109+7 取模）

∑p∈permutation(n)(kτ(P)+τ2(P))∑p∈permutation⁡(n)(kτ(P)+τ2(P))

输入格式

本题为多组数据，第一行为数据组数 TT。

对于每组数据，一行两个正整数 $n$，kk。意义为题目中所述。

输出格式

对于每组数据，一行一个整数。

样例

输入 #1

1
3 2

输出 #1

40

说明/提示

对于 10%10% 的数据：T=1,n≤10,k≤2T=1,n≤10,k≤2

对于 30%30% 的数据：T=1,n≤100,k≤2T=1,n≤100,k≤2

另外有 5%5% 的数据：n=1,k≤1e9n=1,k≤1e9

对于 100%100% 的数据：∑n≤107,T≤106,2≤k≤109∑n≤107,T≤106,2≤k≤109

对于 0%0% 的数据：∑n≤1012∑n≤1012

BR 捅似你喵

时间限制：2000ms 内存限制：65536kb

通过率：3/20 (15.00%) 正确率：3/53 (5.66%)

题目背景

“你吃的是什么喵？分我一点喵？什么，这不是我的分吗喵！不要吃我的分喵！不要吃了喵！捅似你喵！捅似你喵！捅似你喵！”长久地被炸鱼勾折磨，SuB 对炸鱼勾的怨念越来越深了。在一个月黑风高的夜晚，SuB 黑进了游戏的服务器，并锁定了几个炸鱼勾的账号，现在他准备将他们匹配到一起，体会体会掉分的痛苦！

题目描述

SuB 将炸鱼勾排成了一个 n×mn×m 的矩阵，他每次可以选择将任意一个子矩阵中的炸鱼勾分配到一个房间，并且在暗箱操作下，他可以保证每个人都能掉 1 分。

但是，由于段位保护，如果一个炸鱼勾的分数归零，那么他将无法再被匹配进房间，即是说，炸鱼勾的分数不能为负数。

现在，SuB 想知道，他最少需要操作几次，才可以使所有炸鱼勾的分数归零。

输入

第一行两个正整数 $n$ 和 $m$ ；

接下来 $n$ 行，每行 mm 个正整数 ai,jai,j ，表示炸鱼勾的初始分数。

输出

共一个数，表示 SuB 最少所需的分配次数。

输入样例

3 4
2 4 4 2
4 8 8 4
2 4 4 2

输出样例

8

样例解释

如图所示，分别将这四个子矩阵中的炸鱼勾分配到一起各 22 次，即可使所有炸鱼勾的分数归零。

数据范围

• 对于 20%20% 的数据， 1≤n,m≤101≤n,m≤10
• 对于 60%60% 的数据， 1≤n,m≤1001≤n,m≤100
• 对于 100%100% 的数据， 1≤n,m≤200,0≤ai,j≤1061≤n,m≤200,0≤ai,j≤106

Not Hint

似了喵。。

BS Contrasty Angeles

时间限制：1000ms 内存限制：65536kb

通过率：6/16 (37.50%) 正确率：6/36 (16.67%)

题目背景

露薇娅和芦苇鸭是一体两面的好朋友。

她们住在环形小镇的两端。环形小镇从 11 到 $n$ 顺序编号，共有 $n$ 条双向道路，露薇娅住在 ss，而卤味鸭住在 $t$。

这天，露薇娅收掉了定数最高的魔王曲「Contrasty Angeles」，想要去和芦苇鸭炫耀一下。

但是天空依然在下着雨。虽然她并不会被雨淋湿，也不会因为淋雨而陷入梦境，但经过水坑仍是很麻烦的事情。

于是她把这个问题交给了你，想要知道：假设每个道路的长度在整数区间 [1,m][1,m] 中随机选取且已知，从 ss 到 $t$ 最短路径的长度期望是多少？

同时，她发现你可能不会分数的模运算，于是她为了让你能够输出整数，你可以输出期望值乘以 mnmn。

同时由于答案可能非常大，你的答案应该对 109+7109+7 取模。

题目描述

与上文题目背景等价。

给定一个 $n$ 个节点的环，节点依次编号为 1,2,3,⋯,n1,2,3,⋯,n。

很明显该环有双向边 (1,2),(2,3),(3,4),⋯(n−1,n),(n,1)(1,2),(2,3),(3,4),⋯(n−1,n),(n,1)，共有 $n$ 条边。

通过这些边可以从一个节点走到相邻的节点上。显然任意两个节点之间可以互相到达。

给定正整数 $m$，这 $n$ 条边的距离可能在 { 1,2,3,⋯,m−1,m1,2,3,⋯,m−1,m } 中等概率随机选取。

显然，这 $n$ 条边各有 $m$ 种可能，所以一共有 mnmn 种可能的不同选取方案。

给定起点 ss 和终点 $t$，求从 ss 到 $t$ 最短路径在这 mnmn 种情况下的和。

答案对 109+7109+7 取模。

形式化题面

与上文题目描述等价。

我们令从 vv 到 v+1v+1 的边 (v,v+1)(v,v+1) 的长度设为 evev。特别地，边 (n,1)(n,1) 的长度为 enen。

求：

answer=∑e1=1m∑e2=1m⋯∑en=1mdistance(s,t)mod109+7=∑(e1,e2,⋯,en)∈1,2,⋯,mnmin{es+⋯+et−1,et+⋯+en+e1+⋯+es−1}mod109+7answer=∑e1=1m∑e2=1m⋯∑en=1mdistance(s,t)mod109+7=∑(e1,e2,⋯,en)∈1,2,⋯,mnmin{es+⋯+et−1,et+⋯+en+e1+⋯+es−1}mod109+7

输入格式

共两行，第一行为两个由空格分隔的正整数n,mn,m，第二行为两个由空格分隔的正整数 s,ts,t。

输出格式

一行一个整数，代表答案。

样例输入 #1

3 2
1 2

样例输出 #1

12

样例解释 #1

这是一个节点数为 33 的环，共 33 条边，每条边长度在{ 1,21,2 } 间随机，共 23=823=8 种情况。要找的路径从 11 到 22。

当边 (1,2)(1,2) 长度为 11 时，最短路径长度一定是 11，共 44 种情况。

当边 (1,2)(1,2) 长度为 22 时，最短路径长度一定是 22，共 44 种情况。

答案为 1×4+2×4=121×4+2×4=12。

样例输入 #2

4 3
2 4

样例输出 #2

272

样例解释 #2

这是一个节点数为 44 的环，共 44 条边，每条边长度在 { 1,2,31,2,3 } 间随机，共 34=8134=81 种情况。要找的路径从 22 到 44。

可以发现有两条路可走：A:2→3→4A:2→3→4 或 B:2→1→4B:2→1→4。

可以证明，路径 A,BA,B 均有 32=932=9 种可能，长度为 2,3,4,5,62,3,4,5,6 的可能分别为 1,2,3,2,11,2,3,2,1。

因此，路径 A,BA,B 长度最小值可能是 2,3,4,5,62,3,4,5,6，可能为 17,28,27,8,117,28,27,8,1。

答案为 2×17+3×28+4×27+5×8+6×1=2722×17+3×28+4×27+5×8+6×1=272。

样例输入 #3

8 6
2 4

样例输出 #3

11755310

样例输入 #4

40 50
20 30

样例输出 #4

536456982

数据范围

对于 30%30% 的数据，n≤5,m≤5,s=1,t=$n$≤5,m≤5,s=1,t=n。

对于 80%80% 的数据，n≤50,m≤50n≤50,m≤50。

对于 100%100% 的数据，1≤s≤t≤n≤500,m≤5001≤s≤t≤n≤500,m≤500。

Hint

一个方便理解的样例：

当 n=6,s=1,t=5,e1=1,e2=2,e3=3,e4=4,e5=5,e6=6n=6,s=1,t=5,e1=1,e2=2,e3=3,e4=4,e5=5,e6=6 时：

从起点 s=1s=1 到终点 t=5t=5 的最短路径长度为 1+2+3+4=101+2+3+4=10。另一条路的长度为 5+6=115+6=11，不是最短路径。

哎音游人真的是

BT mod 2024

时间限制：1000ms 内存限制：65536kb

通过率：239/364 (65.66%) 正确率：239/1068 (22.38%)

题目背景

本题由同学供题，助教代为上传

题目描述

输入两个自然数 m,nm,n，求出 $n$ 除以 $m$ 的余数。

输入

两个自然数 m,nm,n。

输出

$n$ 除以 $m$ 的余数。

输入样例

91
1000000000000000000000000

输出样例

1

数据范围

$1≤m≤10^9,0≤n<10^{106}$

出题人：tb148