codeforces 777C.Alyona and Spreadsheet 解题报告

题目链接：http://codeforces.com/problemset/problem/777/C

题目意思：给出一个 n * m 的矩阵，然后问 [l, r] 行之间是否存在至少一列是非递减序列

解析：

（1）原输入：

——》

（2）统计第 i 行里第 j 列的最长非递减序列数

——》

（3）每列非递减序列在第 i 行的最长值

然后有两种方法：二维数组和一维数组的处理。个人偏向一维数组

方法一（一维数组）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 /*  一维数组做法
 8 （1）up[0-m]：上一行输入数，每输入一行更新一次
 9 （2）cnt[0-m]： 如果当前输入数 a 与 up[0-m] 构成非递减序列，则cnt[0-m]累加1   （if  a >= up[x], cnt[x]=cnt[x-1]+1   0 < x < n）
10 （3）max_row[j]：每列非递减序列在第 j 行的最长值
11 */
12 
13 const int maxn = 1e5 + 5;
14 int up[maxn];
15 int cnt[maxn], max_row[maxn];
16 
17 
18 int main()
19 {
20     #ifndef ONLINE_JUDGE
21         freopen("in.txt", "r", stdin);
22     #endif // ONLINE_JUDGE
23 
24     int n, m;
25     while (scanf("%d%d", &n, &m) !=EOF) {
26         memset(cnt, 0, sizeof(cnt));
27         memset(max_row, 0, sizeof(max_row));
28 
29         for (int i = 0; i < m; i++) {    // 第 1 行
30             scanf("%d", &up[i]);
31             max_row[i] = cnt[i] = 1;
32         }
33 
34         int a;    // 第 2 行 ~ 第 n 行
35         for (int i = 1; i < n; i++) {
36             for (int j = 0; j < m; j++) {
37                 scanf("%d", &a);
38                 cnt[j] = (a >= up[j] ? cnt[j]+1 : 1);
39                 up[j] = a;    // 更新
40                 max_row[i] = max(max_row[i], cnt[j]);
41             }
42         }
43     
44         int k, l, r;
45         scanf("%d", &k);
46         while (k--) {
47             scanf("%d%d", &l, &r);
48             printf("%s
", max_row[r-1] >= r-l+1 ? "Yes" : "No");
49         }
50     }
51     return 0;
52 }

View Code

方法二（二维数组）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <vector>
 6 using namespace std;
 7 
 8 int main()
 9 {
10     #ifndef ONLINE_JUDGE
11         freopen("in.txt", "r", stdin);
12     #endif // ONLINE_JUDGE
13 
14     int n, m;
15     while (scanf("%d%d", &n, &m) !=EOF) {
16         vector<vector<int> > a, cnt;
17         a.resize(n);
18         cnt.resize(n);
19         for (int i = 0; i < n; i++) {
20             a[i].resize(m);
21             cnt[i].resize(m);
22             for (int j = 0; j < m; j++) {
23                 scanf("%d", &a[i][j]);
24             }
25         }
26 
27         for (int i = 0; i < m; i++) {
28             cnt[0][i] = 1;
29             for (int j = 1; j < n; j++) {
30                 cnt[j][i] = (a[j][i] >= a[j-1][i] ? cnt[j-1][i]+1 : 1);
31             }
32         }
33         int maxr[100005];
34         for (int i = 0; i < n; i++) {
35             maxr[i] = 0;
36             for (int j = 0; j < m; j++) {
37                 maxr[i] = max(maxr[i], cnt[i][j]);
38             }
39         }
40         int k, l, r;
41         scanf("%d", &k);
42         for (int i = 0; i < k; i++) {
43             scanf("%d%d", &l, &r);
44             printf("%s
", r-l+1 <= maxr[r-1] ? "Yes" : "No");
45         }
46     }
47     return 0;
48 }

View Code