题目链接：http://codeforces.com/contest/838/problem/A
知识点： (void)
题目大意：
给一个 (n imes m) 的 01 矩阵，对于矩阵在 (n imes m) 这个范围外的可以都视为 0。将矩阵分为多个 (k imes k) 的小块 ((k>1, k in Z))，但是要变换矩阵上的元素，使每个小块都为 0 或者都为 1。求最少变换多少个元素可以满足要求。
解题思路：
用 vector<int> point[i] 记录第 (i) 行的 1 的位置。然后从 2 开始枚举 (k) 到 max(n,m)，（剪枝：由某一个 (k) 得到的答案一定会优于或等于由 (n imes k (n > 1, n in Z)) 得到的答案。因此，我们考虑完 (k) 之后，对于 (2k, 3k...) 这些就都不用考虑了，也就是说我们只需考虑 (k) 是素数的情况），对于每一个 (k)，先遍历它对应的每一个小方块的左上角的点，然后遍历每个小方块的每一行，用 lower_bound() 找出这一行中位于对应小方块中的 1 的个数，加起来得到小方块中 1 的总数。然后每个小方块需要变换的元素数就是 min((k^2) - num_of_one, num_of_one) （注：(k^2)-num_of_one = num_of_zero），加起来就是对应这个 (k) 对应的总变换数，最终答案就取那个最小值。
AC代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int inf = 0x3f3f3f3f, maxn = 2600; 5 int vis[maxn]; 6 char st[maxn][maxn]; 7 vector<int> point[maxn]; 8 int main() { 9 int n, m; 10 int num = 0; 11 scanf("%d%d", &n, &m); 12 for (int i = 0; i<n; i++) scanf("%s", st[i]); 13 for (int i = 0; i<n; i++) 14 for (int j = 0; j<m; j++) { 15 if (st[i][j] == '1') { 16 point[i].push_back(j); 17 num++; //1的总个数 18 } 19 } 20 int maxk = max(n, m), ans = num; 21 int temp, fail, tone; 22 for (int k = 2; k <= maxk; k++) { 23 if (vis[k]) continue; 24 else { 25 for (int i = k; i <= maxk; i += k) vis[i] = 1; 26 } 27 28 temp = 0, fail = 0, tone = 0; 29 for (int i = 0; i<n; i += k) { 30 if (tone >= num || fail) break; //如果找出了所有的1，那么就没有必要再继续遍历下去了，其他的都是0 31 for (int j = 0; j<m; j += k) { //定左上角 32 if (tone >= num || fail) break; 33 int one = 0; 34 for (int z1 = 0; z1<k&&i + z1<n; z1++) { 35 if (tone >= num || fail) break; 36 int l = lower_bound(point[i + z1].begin(), point[i + z1].end(), j) - point[i + z1].begin(); 37 int r = lower_bound(point[i + z1].begin(), point[i + z1].end(), j + k) - point[i + z1].begin(); 38 one += r - l; 39 tone += r - l; 40 } 41 temp += min(k*k - one, one); 42 if (temp >= ans) { //如果发现temp已经大于或等于我们目前已知的最佳答案，那么也没有必要继续下去了 43 fail = 1; 44 break; 45 } 46 } 47 } 48 if (temp<ans) ans = temp; 49 } 50 printf("%d ", ans); 51 52 return 0; 53 }