[Codeforces 496.C] Removing Columns

原题

思路

  1. 先考虑比较简单的一个问题:比较相邻的某两行,删除哪些列可以使得这两行变为字典序?

    1. 从左向右遍历,相等的元素并不能帮助我们判断字典序。当遇到第一个字典逆序('s' > 'r'),那么这一列必须删除,否则不可能达成字典正序。

      1
      2
      case
      care
    2. 如果某列上已经是字典正序的元素('c' < 'd'),对整体字典序的判断有何影响?答案是显然的,可以提前确认是字典正序,而与后续的元素无关。在此处也无需删除列。

      1
      2
      case
      dare
    3. 结论就是,遇到相等元素,需将判断权委托给后续的元素。而遇到严格的字典正序,可以提前判断;严格的字典逆序,意味着这一列必须删除,计数++,继续向后判断。

  2. 由于n, m都较小,直接暴力把上述方法扩展到n行即可(维护n个状态,记录每行遍历过的前j-1列是否已经提前达成字典正序),$O(nm)$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
* https://codeforces.com/problemset/problem/496/C
* C. Removing Columns
*/
#include <bits/stdc++.h>
using namespace std;
/*
* Solution goes here.
*/
int removingColumns(int n, int m, vector<string>& table) {
// corner cases
if (n == 1) return 0;
vector<bool> sorted(n, false);
int count = 0;
for (int j = 0; j < m; ++j) {
char c = table[0][j];
vector<bool> tmp = sorted;
bool remove = false;
for (int i = 1; i < n; c = table[i][j], ++i) {
if (tmp[i] || table[i][j] == c) continue;
if (table[i][j] > c) {
tmp[i] = true;
continue;
}
// deletion needed
remove = true;
break;
}
if (remove) ++count;
else sorted = tmp;
}
return count;
}