2024-06 · 5级 · 黑白格

GESP 标程 · 考级真题 · 代码 · cpp · 难度 5/5 · 共 1478 字

CCF 原卷官方标程 · 数组与向量、字符串、位运算、图论 · 本地编译通过

2024-06
数组与向量

正文

// GESP 2024-06 C++ 5级 编程题 1 · 黑白格
// 原题：https://oj.yecheng.tv/p/gs2406l5p1
// 官方原卷：https://gesp.ccf.org.cn/101/attach/1621071558082592.pdf
// 题意：小杨有一个行列的网格图，其中每个格子要么是白色，要么是黑色。
// 知识点：数组与向量、字符串、位运算、图论
// 参考程序：CCF 原卷官方标程，PDF 抽取后已去行号；本地编译核验通过，供打字练习
// 原卷样例验证：样例验证 1/1 通过
//
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int w[N][N];
int sum[N][N];
int n,m;
int main(){
    int k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        for(int j=1;j<=m;j++){
            w[i][j]=s[j-1]-'0';
            sum[i][j]=sum[i][j-1]+w[i][j];
        }
    }
    int ans = 0;
    for(int i=1;i<=m;i++){
        for(int j=i;j<=m;j++){
            vector<int> num;
            int now = 0;
            for(int l=1;l<=n;l++){
                int tmp = sum[l][j]-sum[l][i-1];
                now+=tmp;
                num.push_back(now);
                if(now>=k){
                    if(ans ==0)ans=(j-i+1)*l;
                    else ans=min(ans,(j-i+1)*l);
                    int L=1,R=l;
                    while (L < R){
                        int mid = L + R + 1 >> 1;
                        if (now-num[mid-1]>=k) L = mid;
                        else R = mid - 1;
                    }
                    if(now-num[L-1]>=k){
                        if(ans ==0)ans=(j-i+1)*(l-L);
                        else ans=min(ans,(j-i+1)*(l-L));
                    }
                }
            }
        }
    }
    cout<<ans<<"\n";
}

2024-06 · 5级 · 黑白格

正文

GESP 标程 · 考级真题的其它内容