Skip to content

11621: 【原1621】未命名

题目

题目描述

author: Chika 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1621 ## Description

人总会有没灵感的时候。

没灵感的时候，出的题多半都是平凡的Idea堆出来的。

这大概是个懒题，我也不太有想法给它取个好名字。

现在有一个n×n的黑白矩阵，我想找到一个面积最大的全白子矩形。

这次你获得了某种特权，你似乎可以随意交换两行任意多次，于是你可以获得一个更好一点的答案。

于是请你轻松随意的把这题写掉吧。

Input Format

第一行是一个数n，描述这个矩阵的大小。

接下来将会读入n行的01字符串来描述这个矩阵。如果是0，就代表这个格子是黑点，否则是白点。

Output Format

一行，输出最大全白子矩形的大小。

Sample Input

2
11
11

Sample Output

4

Limits

  • 对于40%的数据，n <= 8
  • 对于100%的数据，n <= 1000

q4x3's solution 

/**
 * 用一个矩阵存储每个格子左侧最长的连续白子序列(包括自己)
 * 对矩阵的每一列排序后，遍历，更新答案
 **/
#include <iostream>

using namespace std;

template <typename T>
void merge(int lo, int mi, int hi, T* a)
{
    T* A = a + lo;
    int lb = mi - lo;
    T* B = new T[lb];
    T* BB = B;
    for(int i = 0;i < lb;++ i)
        B[i] = A[i];
    int lc = hi - mi;
    T* C = a + mi;
    int cnt = 0;
    while(1) {
        if ((lb == 0) && (lc == 0)) break;
        if (lb == 0) {
            A[cnt] = C[0];
            ++ cnt; ++ C; -- lc;
        }
        else if (lc == 0) {
            A[cnt] = B[0];
            ++ cnt; ++ B; --lb;
        }
        else {
            if(B[0] < C[0]) {
                A[cnt] = B[0];
                ++ cnt; ++ B; -- lb;
            }
            else {
                A[cnt] = C[0];
                ++ cnt; ++ C; -- lc;
            }
        }
    }
    delete []BB;
}

template <typename T>
void mergeSort(int lo, int hi, T* A)
{
    if(hi - lo < 2) return;
    int mi = (lo + hi) / 2;
    mergeSort(lo, mi, A); mergeSort(mi, hi, A);
    merge(lo, mi, hi, A);
}

int n, b[1010][1010], c[1010], ans;
char a[1010][1010];

int main() {
    cin >> n;
    for(int i = 0;i < n;++ i)
        cin >> a[i];
    for(int i = 0;i < n;++ i)
        for(int j = 0;j < n;++ j) {
            int tmp = j;
            while(a[i][tmp] == '1') {
                -- tmp;
                ++ b[i][j];
            }
        }
    for(int i = 0;i < n;++ i) {
        for(int j = 0;j < n;++ j)
            c[j] = b[j][i];
        mergeSort(0, n, c);
        for(int j = 0;j < n;++ j) {
            if(c[j] * (n - j) > ans) ans = c[j] * (n - j);
        }
    }
    cout << ans << endl;
}

victrid's solution 

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int* MergeSort(int* list, int listSize) {
    if (listSize == 1)
        return list;
    if (listSize == 2) {
        if (list[0] < list[1]) {
            int temp = list[0];
            list[0]  = list[1];
            list[1]  = temp;
            return list;
        }
        return list;
    }
    int* tmplist = new int[listSize];
    int* llst    = MergeSort(list, listSize / 2);
    int* rlst    = MergeSort(list + listSize / 2, listSize - listSize / 2);
    int lct = 0, rct = 0;
    while (lct + rct != listSize) {
        if ((llst[lct] >= rlst[rct] && lct < listSize / 2) || rct >= listSize - listSize / 2) {
            tmplist[lct + rct] = llst[lct];
            lct++;
        } else {
            tmplist[lct + rct] = rlst[rct];
            rct++;
        }
    }
    memcpy(list, tmplist, sizeof(int) * listSize);
    delete[] tmplist;
    return list;
}
int main() {
    int n;
    cin >> n;
    int** mat = new int*[n];
    for (int i = 0; i < n; i++) {
        mat[i] = new int[n]();
    }
    for (int i = 0; i < n; i++) {
        int suml = 0;
        char proc;
        cin.get();
        for (int j = 0; j < n; j++) {
            scanf("%c", &proc);
            proc -= '0';
            suml += proc;
            suml *= proc;
            // suml += proc *= proc; /*fatal*/
            mat[j][i] = suml;
        }
    }
    int pzmax = 0;
    int proc  = 0;
    for (int j = 0; j < n; j++) {
        MergeSort(mat[j], n);
        for (int i = 0; i < n; i++) {
            proc  = mat[j][i] * (i + 1);
            pzmax = pzmax > proc ? pzmax : proc;
        }
    }
    cout << pzmax;
    return 0;
}

WashSwang's solution 

#include <iostream>
using namespace std;
int n,sorted[1001],pre[1001],cur,ans;
char mat[1001][1001];
void qsort(int l,int r){
    if (l+1>=r) return;
    int i=l,j=r-1,k=sorted[l];
    while (i<j){
        while (i<j&&sorted[j]<=k) j--;
        if (i<j) sorted[i++]=sorted[j];
        while (i<j&&sorted[i]>=k) i++;
        if (i<j) sorted[j--]=sorted[i];
    }
    sorted[i]=k;
    qsort(l,i);
    qsort(i+1,r);
}
int main() {
    cin>>n;
    for (int i=0;i<n;++i)
        cin>>mat[i];
    for (int i=0;i<n;++i)
    {
        for (int j=0;j<n;++j)
            if (mat[j][i]!='1')
                sorted[j]=pre[j]=0;
            else sorted[j]=pre[j]=pre[j]+1;
        qsort(0,n);
        cur=sorted[0];
        for (int j=0;j<n;++j){
            cur=min(cur,sorted[j]);
            ans=max(ans,cur*(j+1));
        }
    }
    cout<<ans;
    return 0;
}

zqy2018's solution 

/*
    Hint: build triangular matrix
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, len[1005] = {0}, tmp[1005];
char s[1005][1005];
void init(){
    n = read();
    for (int i = 0; i < n; ++i)
        scanf("%s", s[i]);
}
void solve(){
    int ans = 0;
    for (int i = n - 1; i >= 0; --i){
        for (int j = 0; j < n; ++j)
            len[j] = (s[j][i] == '0' ? 0: len[j] + 1), 
            tmp[j] = len[j];
        sort(tmp, tmp + n);
        for (int j = n - 1; j >= 0; --j)
            ans = max(ans, tmp[j] * (n - j));
    }
    printf("%d\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}