别给我谈心态，我第一题原本满分的QAQ，但是手贱，多点了一下，导致编译错误，算了讲一下吧。

T1.

矩阵游戏(game)

——九校联考24OI__D1T1

问题描述

LZK发明一个矩阵游戏，大家一起来玩玩吧，有一个N行M列的矩阵。第一行的数字是1,2,…M,第二行的数字是M+1,M+2…2*M,以此类推，第N行的数字是(N-1)*M+1,(N-1)*M+2…N*M。
例如,N=3,M=4的矩阵是这样的:
1 2 3 4
5 6 7 8
9 10 11 12

对于身为智慧之神的LZK来说,这个矩阵过于无趣.于是他决定改造这个矩阵,改造会进行K次,每次改造会将矩阵的某一行或某一列乘上一个数字,你的任务是计算最终这个矩阵内所有数字的和,输出答案对109+7取模。

输入

第一行包含三个正整数N、M、K，表示矩阵的大小与改造次数。接下来的行,每行会是如下两种形式之一:
R X Y,表示将矩阵的第X(1 ≤ X ≤ N)行变为原来的Y(00 ≤ Y ≤)倍.
S X Y,表示将矩阵的第X(1 ≤ X ≤ M)列变为原来的Y(00 ≤ Y ≤)倍.

输出

输出一行一个整数,表示最终矩阵内所有元素的和对109+7109+7取模的结果。

输入输出样例

样例1

input
3 4 4
R 2 4
S 4 1
R 3 2
R 2 0
output
94

样例2

input
2 4 4
S 2 0
S 2 3
R 1 5
S 1 3
output
80

样例一的解释:操作结束之后矩阵会变成这样:
1 2 3 4
0 0 0 0
18 20 22 24

数据范围

40%的数据满足：1≤N,M≤1000；
80%的数据满足：1≤N,M≤,1 ≤ K ≤1000；
100%的数据满足：1≤N,M≤,1 ≤ K ≤。

这一道题就是一道数学题，就考虑行，行乘改系数，纵乘改变量就好了

代码dangdang。

#include<bits/stdc++.h> #define int long long #define mod  using namespace std; inline int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)) { if(c == '-') { f = -1; } c = getchar(); } while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int yy[], xx[]; int s, ans, sum; signed main() { freopen("game.in", "r", stdin); freopen("game.out", "w", stdout); for(int i = 1; i <= ; i++) { yy[i] = xx[i] = 1; } int n = read(), m = read(), k = read(); for(int i = 1; i <= k; i++) { char c; int x, y; cin >> c >> x >> y; if(c == 'R') { yy[x] = yy[x] * y % mod; } else { xx[x] = xx[x] * y % mod; } } int s = 0, sum = 0; for(int i = 1; i <= n; i++) { s = (s + ((i - 1) * m + 1) % mod * yy[i]) % mod; sum = (sum + yy[i]) % mod; } int ans = 0; for(int i = 1; i <= m; i++) { ans = (ans + s * xx[i]) % mod; s = (s + sum) % mod; } cout << ans << endl; return 0; }

T2.

问题描述

跳房子，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。
跳房子是在N个格子上进行的，CYJ对游戏进行了改进，该成了跳棋盘，改进后的游戏是在一个N行M列的棋盘上进行，并规定从第一行往上可以走到最后一行，第一列往左可以走到最后一列，反之亦然。每个格子上有一个数字。
在这个棋盘左上角(1,1)放置着一枚棋子。每次棋子会走到右、右上和右下三个方向格子中对应上数字最大一个。即任意时刻棋子都只有一种走法，不存在多个格子同时满足条件。
现在有两种操作：
move k 将棋子前进k步。
change a b e 将第a行第b列格子上的数字修改为e。
请对于每一个move操作输出棋子移动完毕后所处的位置。

输入

第一行包含两个正整数N,M(3<=N,M<=2000)，表示棋盘的大小。
接下来N行，每行M个整数，依次表示每个格子中的数字ai,j。
接下来一行包含一个正整数Q(1<=Q<=5000)，表示操作次数。
接下来m行，每行一个操作，其中1<=a<=N,1<=b<=M,1<=k,e<=109。

输出

对于每个move操作，输出一行两个正整数x,y，即棋子所处的行号和列号。

讯享网

输入输出样例

样例输入

4 4
1 2 9 3
3 5 4 8
4 3 2 7
5 8 1 6
4
move 1
move 1
change 1 4 100
move 1

样例输出

4 2
1 3
1 4

数据范围

10%的数据满足：3<= N,M <=50，Q<=5000， k<=10；
20%的数据满足：3<= N,M <=200，Q<=5000，k<=5000；
另有20%的数据满足：3<= N,M <=200，Q<=5000，k<=109；
100%的数据满足：3<= N,M <=2000，Q<=5000，e,k<=109；

这题我暴力写挂了，QAQ，所以我存一下，一遍日后复习，防止出错。QAQ

代码

讯享网#include<bits/stdc++.h> #define int long long #define mod  using namespace std; inline int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)) { if(c == '-') { f = -1; } c = getchar(); } while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int a[2001][2001]; int n, m; int x = 1, y = 1; inline void move(int step) { int val = 0; if(x == n && y == 1) { if(a[1][n] > val) { x = 1, y = n, val = a[1][n]; } if(a[1][1] > val) { x = 1, y = 1, val = a[1][1]; } if(a[1][2] > val) { x = 1, y = 2, val = a[1][2]; } } else if(x == n && y == m) { if(a[1][m - 1] > val) { x = 1, y = m - 1, val = a[1][m - 1]; } if(a[1][m] > val) { x = 1, y = m, val = a[1][m]; } if(a[1][1] > val) { x = 1, y = 1, val = a[1][1]; } } else if(x == n) { if(a[1][m - 1] > val) { x = 1, y = m - 1, val = a[1][m - 1]; } if(a[1][m] > val) { x = 1, y = m, val = a[1][m]; } if(a[1][m + 1] > val) { x = 1, y = m + 1, val = a[1][m + 1]; } } else if(y == 1) { x = x + 1; if(a[x][m] > val) { y = m, val = a[x][m]; } if(a[x][1] > val) { y = 1, val = a[x][1]; } if(a[x][2] > val) { y = 2, val = a[x][2]; } } else if(y == m) { x = x + 1; if(a[x][m - 1] > val) { y = m - 1, val = a[x][m - 1]; } if(a[x][m] > val) { y = m, val = a[x][m]; } if(a[x][1] > val) { y = 1, val = a[x][1]; } } else { x = x + 1; int yy = y; if(a[x][y - 1] > val) { yy = y - 1, val = a[x][y - 1]; } if(a[x][y] > val) { yy = y, val = a[x][y]; } if(a[x][y + 1] > val) { yy = y + 1, val = a[x][y + 1]; } y = yy; } } signed main() { freopen("jump.in", "r", stdin); freopen("jump.out", "w", stdout); n = read(), m = read(); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { a[j][i] = read(); } } int T = read(); while(T--) { string judge; cin >> judge; if(judge == "move") { int k = read(); move(k); printf("%lld %lld\n", y, x); } else { int x = read(), y = read(), val = read(); a[y][x] = val; } } return 0; }

T3.

优美序列(sequence)

问题描述

Lxy养了N头奶牛，他把N头奶牛用1..N编号，第i头奶牛编号为i。为了让奶牛多产奶，每天早上他都会让奶牛们排成一排做早操。奶牛们是随机排列的。在奶牛排列中，如果一段区间[L,R]中的数从小到大排列后是连续的，他认为这段区间是优美的。比如奶牛排列为：(3, 1, 7, 5, 6, 4, 2)，区间[3,6]是优美的，它包含4,5,6,7连续的四个数，而区间[1,3] 是不优美的。Lxy的问题是：对于给定的一个区间[L,R]（1<=L<=R<=N）, 他想知道，包含区间[L,R]的最短优美区间，比如区间[1,3]的最短优美区间是[1,7]。

输入

第一行为一个整数N，表示奶牛的个数。
第二行为1到N的一个排列，表示奶牛的队伍。
第三行为一个整数M，表示有M个询问。
后面有M行，每行有两个整数L,R表示询问区间。

输出

输出为M行，每行两个整数，表示包含询问区间的最短优美区间。

输入输出样例

样例1

input
7
3 1 7 5 6 4 2
3
3 6
7 7
1 3
output
3 6
7 7
1 7

样例2

input
10
2 1 4 3 5 6 7 10 8 9
5
2 3
3 7
4 7
4 8
7 8
output
1 4
3 7
3 7
3 10
7 10

数据范围

15%的数据满足: 1 <=N,M <= 15；
50%的数据满足：1 <=N,M <= 1000。
100%的数据满足：1 <=N,M <= 。

我复制的博客上的题目，真的，我们考试用的图片太坑人了。

这道题我用线段树瞎水水了76分（某位100大佬985ms和我思路一样，就是我用的是线段树，他用的ST表QAQ瞧不起线段树啊）

算了贴一下代码（心态炸了）

#include<bits/stdc++.h> #pragma GCC optimize(2) #define int long long #define mod  using namespace std; inline int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)) { if(c == '-') { f = -1; } c = getchar(); } while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int a[], b[]; struct SegTree { int minv, maxv; } tree1[], tree2[]; inline void build(int v, int l, int r) { if(l == r) { tree1[v].minv = tree1[v].maxv = a[l]; tree2[v].minv = tree2[v].maxv = b[l]; return; } int mid = (l + r) >> 1; build(v << 1, l, mid); build(v << 1 | 1, mid + 1, r); tree1[v].minv = min(tree1[v << 1].minv, tree1[v << 1 | 1].minv); tree1[v].maxv = max(tree1[v << 1].maxv, tree1[v << 1 | 1].maxv); tree2[v].minv = min(tree2[v << 1].minv, tree2[v << 1 | 1].minv); tree2[v].maxv = max(tree2[v << 1].maxv, tree2[v << 1 | 1].maxv); } inline int querymin1(int v, int l, int r, int nl, int nr) { if(nl >= l && nr <= r) { return tree1[v].minv; } if(nl > r || nr < l) { return 0x7ffffff; } int mid = (nl + nr) >> 1; return min(querymin1(v << 1, l, r, nl, mid), querymin1(v << 1 | 1, l, r, mid + 1, nr)); } inline int querymax1(int v, int l, int r, int nl, int nr) { if(nl >= l && nr <= r) { return tree1[v].maxv; } if(nl > r || nr < l) { return 0; } int mid = (nl + nr) >> 1; return max(querymax1(v << 1, l, r, nl, mid), querymax1(v << 1 | 1, l, r, mid + 1, nr)); } inline int querymin2(int v, int l, int r, int nl, int nr) { if(nl >= l && nr <= r) { return tree2[v].minv; } if(nl > r || nr < l) { return 0x7ffffff; } int mid = (nl + nr) >> 1; return min(querymin2(v << 1, l, r, nl, mid), querymin2(v << 1 | 1, l, r, mid + 1, nr)); } inline int querymax2(int v, int l, int r, int nl, int nr) { if(nl >= l && nr <= r) { return tree2[v].maxv; } if(nl > r || nr < l) { return 0; } int mid = (nl + nr) >> 1; return max(querymax2(v << 1, l, r, nl, mid), querymax2(v << 1 | 1, l, r, mid + 1, nr)); } signed main() { freopen("sequence.in", "r", stdin); freopen("sequence.out", "w", stdout); int n = read(); for(int i = 1; i <= n; i++) { a[i] = read(); b[a[i]] = i; } build(1, 1, n); int m = read(); while(m--) { int l = read(), r = read(), max1, min1, ansl = 0, ansr = 0; bool flag = false; while(l != ansl || r != ansr) { if(flag) { l = ansl, r = ansr; } max1 = querymax1(1, l, r, 1, n); min1 = querymin1(1, l, r, 1, n); ansl = querymin2(1, min1, max1, 1, n); ansr = querymax2(1, min1, max1, 1, n); flag = 1; } printf("%lld %lld\n", ansl, ansr); } return 0; }

题解晚上再发（昨天的好像咕了QAQ）