2019 年 CSP 模拟练习赛
3.0 小时完成
（请选手务必仔细阅读本页内容）
| 题目名称 | 矩阵游戏 | 割韭菜 | 翻硬币 |
| 程序文件名 | matrixgame | leeks | coins |
| 输入文件名 | matrixgame.in | leeks.in | coins.in |
| 输出文件名 | matrixgame.out | leeks.out | coins.out |
| 每个测试点时限 | 1 sec | 2 sec | 1 sec |
| 测试点数目 | 10 | 10 | 10 |
| 每个测试点分值 | 10 | 10 | 10 |
| 内存限制 | 256m | 256m | 256m |
| 题目类型 | 传统型 | 传统型 | 传统型 |
提交源程序文件名：
| 对于 Pascal 语言 | matrixgame.pas | leeks.pas | coins.pas |
| 对于 C 语言 | matrixgame.c | leeks.c | coins.c |
| 对于 C++ 语言 | matrixgame.cpp | leeks.cpp | coins.cpp |
注意事项
1、文件名（程序名和输入输出文件名）必须使用小写。
2、除非特殊说明，结果比较方式均为忽略行末空格及文末回车的全文比较。
3、 C/C++中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0
1. 矩阵游戏
(matrixgame.pas/c/cpp)
【问题描述】
何老板有一个 N 行 M 列的数字矩阵。
第一行的数字是 1,2,3,...,M
第二行的数字是 M+1,M+2,M+3,...,2*M
第三行的数字是 2*M+1,2*M+2,2*M+3,...,3*M
以此类推，第 N 行的数字是(N-1)*M+1,(N-1)*M+2,(N-1)*M+3,...,N*M 。
例如,N=3,M=4 的矩阵是这样的:
1 2 3 4
5 6 7 8
9 10 11 12
现在何老板要改造这个矩阵,改造会进行 K 次,每次改造会将矩阵的某一行或某一列乘上
一个数字。
你的任务是计算最终这个矩阵内所有数字的和,输出答案对 109+7 取模。
【输入格式】
第一行包含三个正整数 N、 M、 K，表示矩阵的大小与改造次数。接下来的 K 行,每行会
是如下两种形式之一:
R X Y,表示将矩阵的第 X(1 ≤ X ≤ N)行变为原来的 Y(0 ≤ Y ≤ 109)倍.
S X Y,表示将矩阵的第 X(1 ≤ X ≤ M)列变为原来的 Y(0 ≤ Y ≤ 109)倍.
【输出格式】
输出一行一个整数,表示最终矩阵内所有元素的和对 109+7 取模。
【输入输出样例】
| 样例输入 1 | 样例输入 2 |
| 3 4 4 R 2 4 S 4 1 R 3 2 R 2 0 |
2 4 4 S 2 0 S 2 3 R 1 5 S 1 3 |
| 样例输出 1 | 样例输出 2 |
| 94 | 80 |
【样例 1 解释】
操作结束之后矩阵会变成这样:
1 2 3 4
0 0 0 0
18 20 22 24
【数据范围】
40%的数据满足： 1≤N,M≤1000；
80%的数据满足： 1≤N,M≤1000000,1 ≤ K ≤10000；
100%的数据满足： 1≤N,M≤1000000,1 ≤ K ≤100000。
2. 割韭菜
(leeks.pas/c/cpp)
【问题描述】
何老板有一个农场，农场可看作 N*M 的方格，每个方格都是一块韭菜田。
每块田都长有一定数量的韭菜。其中坐标为(i,j)的田,即第 i 行，第 j 列的这块田长有
Aij公斤韭菜。
何老板打算从坐标为(X,Y)的田出发，沿上下左右四个方向移动，每到达一块田，何老板
会割走该田所有韭菜。 若当前何老板位于坐标为(i,j)的田，他收割到的韭菜为 Aij公斤，当
何老板离开该田后，该田又会立即长出 Aij公斤韭菜。
何老板今天打算移动 T 步，最后恰好回到起点(X,Y)。问，何老板最多能收割多少公斤韭
菜。
【输入格式】
第一行:5 个正整数 N,M,X,Y,T。
接下来 N 行， 每行 M 个非负整数， 代表农场， 其中第 i 行第 j 列表示 Aij
数据保证 AXY=0， 且 T 为偶数
【输出格式】
一个整数，表示能收割到的最多韭菜公斤数
【输入输出样例】
| 样例输入 1 | 样例输入 2 | 样例输入 3 |
| 2 2 1 1 2 0 1 2 10 |
2 2 1 1 4 0 5 5 10 |
3 3 2 2 6 5 1 0 1 0 3 1 3 3 |
| 样例输出 1 | 样例输出 2 | 样例输出 3 |
| 2 | 20 | 15 |
【数据范围】
对于 30% 的数据， 1≤T≤10000
对于 100% 的数据， 1≤N,M≤100 2 ≤T≤109 0≤Aij≤109
3.翻硬币
(coins.pas/c/cpp)
【问题描述】
何老板给你一棵由 n 个节点构成的树，节点编号 1 到 n，其中 1 号点为根。每个节点上都有一枚硬币，
硬币一面是头像一面是金额，一开始所有硬币都是头像朝上。
接下来何老板进行了 m 次操作，操作分两种：
0 号操作： 将一枚硬币翻转
1 号操作： 指定节点与所有金额朝上节点求 LCA,找出其中深度最大一个 LCA 的编号
【输入格式】
第 1 行，两个正整数 n， m
第 2 行， 共 n-1 个正整数， 其中第 i 个正整数表示 i+1 号结点的父亲
接下来 m 行， 每行一个整数 x ， |x|表示被操作的节点编号， x>0 为 0 号操作， 否则为 1
号操作。
【输出格式】
对于每个 1 号的操作输出对应的节点编号，若树上没有金额朝上的硬币，输出 0。
【输出输出样例】
| 样例输入 1 | 样例输入 2 |
| 10 10 6 2 7 9 1 10 5 4 3 -2 2 -2 3 -5 8 1 4 -1 -5 |
25 12 1 2 2 2 2 2 2 3 8 7 6 8 11 8 14 13 11 12 14 14 17 20 19 20 6 16 -5 8 25 2 - 17 7 -8 - 23 18 -12 |
| 样例输出 1 | 样例输出 2 |
| 0 2 3 1 5 | 2 8 8 20 6 |
【数据范围】
50%的数据 1<=n,m<=3000
100%的数据 1<=n,m<=300000