codeforces 777C.Alyona and Spreadsheet 解题报告

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

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

解析：

（1）原输入：

   ——》

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

——》

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

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

方法 一 （一维数组）

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 /*  一维数组做法

 （1）up[0-m]：上一行输入数，每输入一行更新一次

 （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）

 （3）max_row[j]：每列非递减序列在第 j 行的最长值

 */

 const int maxn = 1e5 + ;

 int up[maxn];

 int cnt[maxn], max_row[maxn];

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("in.txt", "r", stdin);

     #endif // ONLINE_JUDGE

     int n, m;

     while (scanf("%d%d", &n, &m) !=EOF) {

         memset(cnt, , sizeof(cnt));

         memset(max_row, , sizeof(max_row));

         for (int i = ; i < m; i++) {    // 第 1 行

             scanf("%d", &up[i]);

             max_row[i] = cnt[i] = ;

         }

         int a;    // 第 2 行 ~ 第 n 行

         for (int i = ; i < n; i++) {

             for (int j = ; j < m; j++) {

                 scanf("%d", &a);

                 cnt[j] = (a >= up[j] ? cnt[j]+ : );

                 up[j] = a;    // 更新

                 max_row[i] = max(max_row[i], cnt[j]);

             }

         }

         int k, l, r;

         scanf("%d", &k);

         while (k--) {

             scanf("%d%d", &l, &r);

             printf("%s\n", max_row[r-] >= r-l+ ? "Yes" : "No");

         }

     }

     return ;

 }

方法二 （二维数组）

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <vector>

 using namespace std;

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("in.txt", "r", stdin);

     #endif // ONLINE_JUDGE

     int n, m;

     while (scanf("%d%d", &n, &m) !=EOF) {

         vector<vector<int> > a, cnt;

         a.resize(n);

         cnt.resize(n);

         for (int i = ; i < n; i++) {

             a[i].resize(m);

             cnt[i].resize(m);

             for (int j = ; j < m; j++) {

                 scanf("%d", &a[i][j]);

             }

         }

         for (int i = ; i < m; i++) {

             cnt[][i] = ;

             for (int j = ; j < n; j++) {

                 cnt[j][i] = (a[j][i] >= a[j-][i] ? cnt[j-][i]+ : );

             }

         }

         int maxr[];

         for (int i = ; i < n; i++) {

             maxr[i] = ;

             for (int j = ; j < m; j++) {

                 maxr[i] = max(maxr[i], cnt[i][j]);

             }

         }

         int k, l, r;

         scanf("%d", &k);

         for (int i = ; i < k; i++) {

             scanf("%d%d", &l, &r);

             printf("%s\n", r-l+ <= maxr[r-] ? "Yes" : "No");

         }

     }

     return ;

 }