Skip to content

14206: 【原4206】Strict Yan涂色

题目

题目描述

author: 静爸爸 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4206

Description

Alice 得到了一张由n×m 个黑白像素点组成的图片,她想要压缩这张图片。压缩图片的过程如下:

  1. 首先,选择一个正整数k\((k \ge 1)\),将图片划分成若干个\(k \times k\)的小块。如果n,m不能被k整除,用白色像素点在图片的右边或下面补全,使补全成n,m都能被k整除。

  2. 由于压缩时每个\(k \times k\)的小块必须颜色一致(即全黑或者全白),所以需要先改变某些像素点的颜色,然后再进行压缩。

在Alice 可以自由的选择任意一个大于1的正整数k 作为小块的边长的情况下,请你告诉Alice,她至少需要改变多少个像素点的颜色。

Input Format

输入的第一行包含两个由空格隔开的正整数n,m\((2 \leq n,m \leq 1000)\),表示图片的尺寸。

接下来n 行,每行包含一个长度为m 的”01”串,表示Alice 得到的那张图片。”0”表示一个白色像素点,”1”表示一个黑色像素点。

Output Format

输出一个整数,表示Alice 要压缩她的图片至少需要改变颜色的像素点的个数。

Sample Input

3 5
00100
10110
11001

Sample Output

5

Note

选择k=2,图片被补全为,如下:

001000
101100
110010
000000

为使每个2×2 的小块颜色一致,改变颜色为,如下:

001100
001100
000000
000000

可以发现这是所有情况中改变颜色的像素点数最少的,改变了5个像素点的颜色(答案为5的改色方案不止这一种)。

Subtasks

  • 对于40%的数据,满足n=2 或者m=2,且\(n,m \leq 100\)。
  • 对于70%的数据,满足\(n,m \leq 100\)。
  • 对于100%的数据,满足\(n,m \leq 1000\)。

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/28.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

using ll=long long;

bool notPrime[1005] = {};
bool table[2005][2005];

int main() {
    for (int i = 2; i < 1005; ++i) {
        if (!notPrime[i]) {
            for (int j = 2; j * i < 1005; ++j) {
                notPrime[i * j] = true;
            }
        }
    }

    int n, m;
    char tmp;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            do {
                scanf("%c", &tmp);
            } while (tmp == '\n');
            table[i][j] = tmp == '1';
        }
    }

    int minAns = 0x7fffffff;

    int s = min(m, n);
    int t = max(m, n);
    int CNT;
    int cnt;
    int max = (n >= 100 || m >= 100) ? 23 : s;
    for (int p = 2; p <= max; ++p) {
        if (notPrime[p]) continue;
        CNT = 0;
        for (int x = 0; x < n; x += p) {
            for (int y = 0; y < m; y += p) {
                cnt = 0;
                for (int i = 0; i < p; ++i) {
                    for (int j = 0; j < p; ++j) {
                        cnt += table[x + i][y + j];
                    }
                }
                CNT += min(cnt, p * p - cnt);
            }
        }
        minAns = min(minAns, CNT);
    }

    cout << minAns << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

constexpr int inf = 1000000009;

int a[1009][1009] = { 0 };
bool not_num[1009] = { 0 };
int n, m;
int f(int posx, int posy) {
    if (posx <= n && posy <= m)
        return a[posx][posy];
    else if (posx <= n)
        return a[posx][m];
    else if (posy <= m)
        return a[n][posy];
    else
        return a[n][m];
}

int main() {

    cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        a[i][0] = a[i - 1][1];
        for (int j = 1; j <= m; ++j) {
            int temp;
            scanf("%1d", &temp);
            a[i][j] = temp + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        }
    }

    //计算质数
    int max_k = n > m ? n : m;
    for (int i = 2; i <= max_k / 2 + 1; ++i) {
        if (not_num[i])
            continue;
        for (int j = i * 2; j <= max_k; j += i)
            not_num[j] = true;
    }

    int ans = inf;
    for (int k = 2; k <= max_k; ++k) {
        if (not_num[k])
            continue;
        int temp_ans = 0;
        for (int i = 1; i <= n; i += k) {
            for (int j = 1; j <= m; j += k) {
                int posx = i + k - 1, posy = j + k - 1;
                int temp = f(posx, posy) - f(posx - k, posy) - f(posx, posy - k) + f(posx - k, posy - k);
                temp_ans += temp < k * k - temp ? temp : k * k - temp;
            }
        }
        if (temp_ans < ans)
            ans = temp_ans;
    }

    printf("%d", ans);

    return 0;
}

q4x3's solution

/**
 * 模拟 + 二维前缀和
 * 先暴力试试看
 **/
#include <iostream>
#include <stdio.h>

using namespace std;

int n, m, a[2233][2233], tmp, sum[2233][2233];
char c[1233][1233];

int main() {

    scanf("%d %d", &n, &m);
    getchar();
    for(int i = 1;i <= n;++ i) {
        cin >> c[i];
        for(int j = 0;j < m;++ j) {
            a[i][j + 1] = c[i][j] - '0';
        }
    }
    tmp = (m > n) ? m : n;
    for(int i = 1;i <= 2 * tmp;++ i) {
        for(int j = 1;j <= 2 * tmp;++ j) {
            sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + a[i][j];
        }
    }
    int tmpm, tmpn, ans = 1000000, tmpchn, tmpans, flag;
    for(int i = 2;i <= tmp;++ i) {
        if(m % i != 0) tmpm = (m / i + 1) * i;
        else tmpm = m;
        if(n % i != 0) tmpn = (n / i + 1) * i;
        else tmpn = n;
        tmpans = 0;
        flag = 1;
        for(int j = i;j <= tmpn;j += i) {
            for(int k = i;k <= tmpm;k += i) {
                tmpchn = sum[j][k] + sum[j - i][k - i] - sum[j - i][k] - sum[j][k - i];
                tmpans += ((tmpchn < i * i - tmpchn) ? tmpchn : (i * i - tmpchn));
                if(tmpans > ans) {
                    flag = 0;
                    break;
                }
            }
            if(flag == 0) break;
        }
        if(tmpans < ans) ans = tmpans;
    }
    cout << ans << endl;
}

skyzh's solution

#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
using namespace std;

static int PRIME[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};
int PRIME_N = 168;
char MAP[2001][2001] = { 0 };
int D[2001][2001] = { 0 };

int main() {
    int M, N;
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> MAP[i][j];
            MAP[i][j] -= '0';
        }
    }
    D[1][1] = MAP[1][1];
    for (int j = 2; j <= 2000; j++) D[1][j] = D[1][j - 1] + MAP[1][j];
    for (int i = 2; i <= 2000; i++) {
        D[i][1] = MAP[i][1] + D[i - 1][1];
        for (int j = 2; j <= 2000; j++) {
            D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + MAP[i][j];
        }
    }
    int m_sum = INT_MAX, m_idx = -1;
    for (int _k = 0; _k < PRIME_N; _k++) {
        int k = PRIME[_k];
        int n = ceil(1.0 * N / k) * k;
        int m = ceil(1.0 * M / k) * k;
        int blk_size = k * k;
        int sum = 0;
        for (int i = 0; i < n; i += k) {
            for (int j = 0; j < m; j += k) {
                int cnt = D[i + k][j + k] - D[i][j + k] - D[i + k][j] + D[i][j];
                sum += min(cnt, blk_size - cnt);
            }
        }
        if (sum < m_sum) {
            m_sum = sum;
            m_idx = k;
        }
    }
    printf("%d\n", m_sum);
    return 0;
}

victrid's solution

#include <cmath>
#include <iostream>
using namespace std;
int pic[1005][1005] = {0};
int n, m;
inline int getpixel(int i, int j, int k) {
    return pic[(i * k > n) ? n : i * k][j * k > m ? m : j * k];
}
int getdelta(int i, int j, int k) {
    int ans = getpixel(i, j, k) - getpixel(i - 1, j, k) - getpixel(i, j - 1, k) + getpixel(i - 1, j - 1, k);
    return min(ans, k * k - ans);
}
int gettotals(int k) {
    int nmax   = ceil(n / (double)k);
    int mmax   = ceil(m / (double)k);
    int totals = 0;
    for (int i = 1; i <= nmax; i++) {
        for (int j = 1; j <= mmax; j++) {
            totals += getdelta(i, j, k);
        }
    }
    return totals;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char proc;
            do {
                scanf("%c", &proc);
            } while (proc == '\n');
            pic[i][j] = pic[i - 1][j] + pic[i][j - 1] - pic[i - 1][j - 1] + proc - '0';
        }
    }
    int chvl = max(n, m) * max(n, m);
    for (int k = 2; k < max(n, m); k++) {
        chvl = min(chvl, gettotals(k));
    }
    cout << chvl;
    return 0;
}