标签：10 普及 le 23 样例 输出 免费 输入 out

便宜没好货。

T1

U362268

题目描述

有一个 MAR 数列，它的定义是这样的：对于每一个 \(f_{i}(i>2)\)：\(f_i=f_{i-1} \times f_{i-2}\)，并且对于每个 \(f_i(i>2)\)，需要对 \(i\) 取模，现在给出 \(f_1,f_2\) 的值，需要你求出 \(f_n\) 的值。

输入格式

三个正整数 \(f_1,f_2,n\)。

输出格式

这个序列的第 \(n\) 项的值。

样例 #1

样例输入 #1

1 5 5

样例输出 #1

4

样例 #2

样例输入 #2

9 10 2

样例输出 #2

10

提示

【样例解释 #1】

这个序列为：\(\{1,5,2,2,4\}\)，第 \(5\) 项是 \(4\)，

【样例解释 #2】

这个序列为：\(\{9,10\}\)，第 \(2\) 项是 \(10\)，

【样例 #3】

见附件中的 A3.in 与 A3.out。

【样例 #4】

见附件中的 A4.in 与 A4.out。

【数据范围】

对于 \(10\%\) 的数据，\(1 \le f_1,f_2,n \le 2\)，

对于 \(20\%\) 的数据，\(1 \le f_1,f_2,n \le 10\)，

对于 \(30\%\) 的数据，\(1 \le f_1,f_2,n \le 10^2\)，

对于 \(50\%\) 的数据，\(1 \le f_1,f_2,n \le 10^3\)，

对于 \(70\%\) 的数据，\(1 \le f_1,f_2,n \le 10^5\)，

对于 \(90\%\) 的数据，\(1 \le f_1,f_2,n \le 10^7\)，

对于 \(100\%\) 的数据，\(1 \le f_1,f_2,n \le 10^8\)，保证数据在范围内均匀生成。

Solution

模拟 + 特判

T2

U362416

题目描述

现在有 \(n\) 个人在玩狼人杀，一共有 \(3\) 个身份，身份的介绍是这样的：

1. 狼人，每晚所有狼人会杀死一个非狼人且最左边的人，投票会投给非狼人且最左边的人。

2. 女巫，有一瓶解药，这瓶解药在夜晚可以任意复活一个人，投票会投给编号最左边的人，注意，每个女巫只有一瓶解药，且这瓶解药必定会给好人。

3. 平民，投票会投给编号最左边的人。

每晚所有玩家会按照身份编号顺序依次行动。

对于游戏结束的判定：

1. 若活着人的数量 \(\le\) 狼人数 \(\times 2\)，则狼人获胜，你需要输出 1 x y，其中 \(x\) 表示存活的好人人数，\(y\) 表示存活的狼人人数。

2. 若狼人的数量为 \(0\)，则好人获胜，你需要输出 2 x y，其中 \(x\) 表示存活的好人人数，\(y\) 表示存活的狼人人数。

特别的，这个判定在每一个白天或夜晚结束时才会判定，且先判定狼人的获胜条件。

对于投票的判定：

驱逐被投票数最多的人，若有平票，则放逐序号最小的那个，此时白天结束。

输入格式

第一行输入一个正整数 \(n\)，表示游戏总人数，

第二行输入 \(n\) 个正整数 \(a_i\)，表示这 \(n\) 个人每个人的身份。

输出格式

输出 \(3\) 个正整数 \(a,x,y\)，分别表示获胜阵营，游戏结束时存活的好人人数和存活的狼人人数。

样例 #1

样例输入 #1

4
1 2 3 3

样例输出 #1

2 3 0

提示

【样例解释 #1】

首先开始是夜晚，狼人会杀死 \(2\) 号，女巫会自救，之后天亮了，大家投 \(1\) 号，由于狼人数量为 \(0\)，因此游戏结束，好人胜利，存活的好人数为 \(3\)。

【样例 #2】

见附件中的 B2.in 与 B2.out。

【样例 #3】

见附件中的 B3.in 与 B3.out。

【样例 #4】

见附件中的 B4.in 与 B4.out。

【数据范围】

保证对于 \(100\%\) 的数据，\(1 \le n \le 10^7\)。

测试点编号	\(n \le\)	特殊性质
\(1\)	\(10\)	无
\(2\)	\(10^2\)	无
\(3\)	\(10^3\)	无
\(4\)	\(10^4\)	无
\(5\)	\(10^5\)	无
\(6\)	\(10^6\)	保证没有平民
\(7\)	\(10^6\)	无
\(8\)	\(10^7\)	保证没有平民
\(9\)	\(10^7\)	无
\(10\)	\(10^7\)	无

Solution

随便贪一下就过了。

T3

U362724

题目背景

你掉进了一个迷宫里。

题目描述

这个迷宫里有几种地板，@ 表示起点，& 表示终点，0 表示能走，1 表示不能走，大写字母表示一个传送门，可以传送到对应字母的位置。你从起点开始最少要走几步才能到终点。

输入格式

第一行两个正整数，\(n,m\)，表示迷宫的大小。

然后一个 \(n \times m\) 的字符矩阵，表示整个迷宫。

输出格式

一个正整数，表示最少的步数。若无解，则输出 No Solution.。

样例 #1

样例输入 #1

3 5
@0010
A1000
100A&

样例输出 #1

2

提示

【样例解释 #1】

第一步走到 \((2,1)\)，传送到 \((3,4)\)，第二步走到终点 \((3,5)\)。

【样例 #2】

见附件中的 C2.in 与 C2.out。

【样例 #3】

见附件中的 C3.in 与 C3.out。

【样例 #4】

见附件中的 C4.in 与 C4.out。

【数据范围】

保证对于 \(100\%\) 的数据，\(1\le n,m \le 10^3\)，每个大写字母不超过 \(2\) 个，保证有起点和终点。

测试点编号	\(n,m \le\)	特殊性质
\(1\)	\(10\)	无
\(2\)	\(10\)	无
\(3\)	\(10^2\)	无
\(4\)	\(10^2\)	无
\(5\)	\(10^2\)	无
\(6\)	\(10^3\)	保证没有传送门
\(7\)	\(10^3\)	保证数据在范围内均匀生成
\(8\)	\(10^3\)	无
\(9\)	\(10^3\)	无
\(10\)	\(10^3\)	无

Solution

bfs 板子。

T4

U361837

题目描述

现在有一个 \(n\) 行 \(m\) 列的矩阵，你需要求出从 \((x1,y1)\) 走到 \((x2,y2)\) 的方案数（只能往右方和下方走），但是需要注意的是，矩阵中间可能会有一处炸弹，你不能走到那个地方，否则炸弹就会爆炸。

输入格式

输入共 \(q+1\) 行：

第 \(1\) 行输入 \(n,m,q,opt\)，分别表示矩阵的大小及询问的次数，若 \(opt=1\)，则需要额外输入一个含有炸弹的坐标。

之后 \(q\) 行输入 \(x1,y1,x2,y2\)，表示从 \(x1,y1\) 走到 \(x2,y2\) 的方案数。

输出格式

对于每组询问，给出能从 \(x1,y1\) 走到 \(x2,y2\) 的方案数，由于结果可能很大，所以需要你对 \(10^9+7\) 取模。

样例 #1

样例输入 #1

3 3 1 0
1 1 3 3

样例输出 #1

6

样例 #2

样例输入 #2

3 3 1 1 2 2
1 1 3 3

样例输出 #2

2

提示

【样例 #3】

见附件中的 D3.in 与 D3.out。

【样例 #4】

见附件中的 D4.in 与 D4.out。

【数据范围】

数据保证 \(x1,y1,x2,y2\) 均为合法的。

测试点编号	\(n,m \le\)	\(q \le\)	\(opt=\)	特殊条件
\(1 \sim 2\)	\(10\)	\(10\)	\(0\)	无
\(3 \sim 4\)	\(10\)	\(10\)	\(1\)	无
\(5\)	\(10^3\)	\(10^2\)	\(0\)	无
\(6\)	\(10^3\)	\(10^2\)	\(1\)	无
\(7\)	\(10^3\)	\(10^3\)	\(0,1\)	无
\(8 \sim 10\)	\(10^4\)	\(10^3\)	\(0,1\)	无
\(11 \sim 12\)	\(10^4\)	\(10^4\)	\(0,1\)	无
\(13 \sim 16\)	\(10^4 \times 5\)	\(10^4 \times 5\)	\(0,1\)	无
\(17 \sim 18\)	\(10^5\)	\(10^5\)	\(0,1\)	无
\(19\)	\(10^6\)	\(10^6\)	\(0,1\)	保证数据在范围内均匀生成
\(20\)	\(2 \times 10^6\)	\(2 \times 10^6\)	\(0,1\)	无

Solution

组合数，直接预处理一下逆元就好了，单次查询 \(O(1)\)。

标签：10,普及,le,23,样例,输出,免费,输入,out
From： https://www.cnblogs.com/wangmarui/p/18024147