[编程题]分田地
- 热度指数：17478 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
牛牛和 15
个朋友来玩打土豪分田地的游戏，牛牛决定让你来分田地，地主的田地可以看成是一个矩形，每个位置有一个价值。分割田地的方法是横竖各切三刀，分成 16
份，作为领导干部，牛牛总是会选择其中总价值最小的一份田地， 作为牛牛最好的朋友，你希望牛牛取得的田地的价值和尽可能大，你知道这个值最大可以是多少吗？
输入描述:
每个输入包含 1 个测试用例。每个测试用例的第一行包含两个整数 n 和 m（1 <= n, m <= 75），表示田地的大小，接下来的 n 行，每行包含 m 个 0-9 之间的数字，表示每块位置的价值。
输出描述:
输出一行表示牛牛所能取得的最大的价值。
示例1
输入
4 4 3332 3233 3332 2323
输出
2
刚看完大佬的思路AC了，可能还有人不明白，我仔细解释一下吧
题意是：通过横竖各三刀将一个矩阵分为16部分，每部分的value即为这一部分包含的所有数字之和。我们要做的就是想一种切法，使得这16部分中value最小的那个尽可能的大。
首先很显然，每一个部分的value在0-sum之间，sum是指整个矩阵所有数字之和。这样最终的结果一定是[0, sum]中的某一个整数
这里稍微逆向思考一下，既然不容易直接求结果，可不可以我猜一个值(k)，然后判断能不能通过某种切法使最小的那一块value>=k呢？（也就是说，使16块的value都能大于等于k）
如果可以的话，我们就可以对[0, sum]这个区间进行二分查找。这个容易理解吧，当然逻辑上你从num开始递减遍历判断a肯定也是ok的，但是会超时，所以换成二分
二分的复杂度是log(sum)
接下来是重点：对于一个值，怎么判断能不能横竖切三刀，使16块的value都大于等于k呢
可以先横着切三刀，然后纵向贪心遍历一遍。这部分我也不用多说了，想不通的话看看代码就明白了。复杂度是n^4
最后我真是太菜了。。。不看别人思路完全做不出来。。。
#include <cstdio>
#include <iostream>
using namespace std;
int n, m;
int a[100][100];
int sum[100][100];
inline int calc(int x1, int y1, int x2, int y2) {
return sum[x2][y2] - sum[x2][y1] - sum[x1][y2] + sum[x1][y1];
}
int ojbk(int k) {
for (int x1 = 1; x1 <= n-3; x1++)
{
for (int x2 = x1+1; x2 <= n-2; x2++)
{
for (int x3 = x2+1; x3 <= n-1; x3++)
{
int cnt = 0;
int rec = 0;
for (int y = 1; y <= m; y++)
{
if (calc(0, rec, x1, y) >= k\
&& calc(x1, rec, x2, y) >= k\
&& calc(x2, rec, x3, y) >= k\
&& calc(x3, rec, n, y) >= k)
{
cnt++;
rec = y;
}
}
if (cnt >= 4)
{
return true;
}
}
}
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
char buf[100];
for (int i = 1; i <= n; i++)
{
scanf("%s", buf+1);
for (int j = 1; j <= m; j++)
{
a[i][j] = buf[j] - '0';
}
}
memset(sum, 0, sizeof(sum));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + a[i][j];
}
}
int l = 0, r = sum[n][m];
int m;
int ans = 0;
while (l <= r)
{
m = (l+r)/2;
if (ojbk(m))
{
l = m+1;
ans = m;
}
else
{
r = m-1;
}
}
cout << ans << endl;
return 0;
}
发表于 2018-03-25 19:14:38
回复(12)
#-*- coding: utf8 -*- """ 横竖各三刀将一个矩阵分为16部分，每部分的value即为这一部分包含的所有数字之和。 我们要做的就是想一种切法，使得这16部分中value最小的那个尽可能的大。 首先很显然，每一个部分的value在0-sum之间，sum是指整个矩阵所有数字之和， 这样最终的结果一定是[0, sum]中的某一个整数。 这里稍微逆向思考一下，既然不容易直接求结果，可不可以我猜一个值k 然后判断能不能通过某种切法使最小的那一块value>=k,也就是说，使16块的value都能大于等于k, 如果可以的话，我们就可以对[0, sum]这个区间进行二分查找。 二分的复杂度是log(sum). 接下来是重点：对于一个值，怎么判断能不能横竖切三刀，使16块的value都大于等于k呢 二分答案，判断可行性时暴力枚举三列的情况，然后横着贪心地扫一遍, 每当四列都满足的时候就砍一刀，满足四次即可 """ n,m=map(int,raw_input().strip().split()) matrix=[map(int,list(raw_input().strip())) for _ in range(n)] sum_values = [[0]*(m+1) for i in range(n + 1)] for i in range(1, n + 1): for j in range(1, m + 1): sum_values[i][j] += sum_values[i - 1][j] + sum_values[i][j - 1] - sum_values[i - 1][j - 1] + matrix[i-1][j-1] def calculate_sum(p1,p2): x1,y1=p1 x2,y2=p2 a1,a2=sum_values[x1 - 1][y1 - 1],sum_values[x1 - 1][y2] a3,a4=sum_values[x2][y1 - 1],sum_values[x2][y2] value=a4-a3-a2+a1 return value def check(mid): for j1 in range(1, m - 2): if calculate_sum((1,1),(n,j1)) < mid * 4: continue for j2 in range(j1 + 1, m - 1): if calculate_sum((1,j1+1),(n,j2)) < mid * 4: continue for j3 in range(j2 + 1, m): if calculate_sum((1,j2+1),(n,j3)) < mid * 4: continue if calculate_sum((1,j3+1),(n,m)) < mid * 4: continue pstart,row_count=1,0 for pend in range(1, n + 1): p1_list=[(pstart,1),(pstart,j1+1),(pstart,j2+1),(pstart,j3+1)] p2_list=[(pend,j1),(pend,j2),(pend,j3),(pend,m)] values=[calculate_sum(p1,p2) for p1,p2 in zip(p1_list,p2_list)] if min(values) >= mid: pstart=pend+1 row_count+=1 if row_count == 4:return True return False l, r = 0, sum_values[n][m] answer = 0 while l <= r: mid = (l + r) / 2 if check(mid): l = mid + 1 answer = mid else: r = mid - 1 print answer
发表于 2018-07-31 09:57:51
回复(0)
//AC代码：
#include<stdio.h>
#include<string.h>
const int maxn=76;
int area[maxn][maxn],G[maxn][maxn];
char field[maxn][maxn];
int solve();
int getA(int,int,int,int);
bool judge(int,int,int,int);
bool isAreaOk(int);
int n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;scanf("%s",field[i]),i++);
printf("%d\n",solve());
}
int solve(){
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++) G[i][j]=field[i-1][j-1]-'0';
int Max=0;
area[1][1]=G[1][1];
for(j=2;j<=m;j++) area[1][j]=G[1][j]+area[1][j-1];
for(i=2;i<=n;i++) area[i][1]=G[i][1]+area[i-1][1];
for(i=2;i<=n;i++)
for(j=2;j<=m;j++)
area[i][j]=G[i][j]+area[i-1][j]+area[i][j-1]-area[i-1][j-1];
int l=0,r=75*75*9;
while(l+1<r){
int mid=(l+r)/2;
if(isAreaOk(mid)) l=mid;
else r=mid;
}
if(isAreaOk(r)) return r;
return l;
}
int getA(int i,int j,int k,int q){
return area[k][q]-area[i-1][q]-area[k][j-1]+area[i-1][j-1];
}
bool judge(int i,int j,int k,int x){
int q,cnt=0,pre=0;
for(q=1;q<=m;q++){
int x1=getA(1,pre+1,i,q),x2=getA(i+1,pre+1,j,q);
int x3=getA(j+1,pre+1,k,q),x4=getA(k+1,pre+1,n,q);
if(x1>=x&&x2>=x&&x3>=x&&x4>=x){
pre=q;
cnt++;
if(cnt==4) break;
}
}
return cnt==4;
}
bool isAreaOk(int x){
int i,j,k;
for(i=1;i<n;i++)
for(j=i+1;j<n;j++)
for(k=j+1;k<n;k++)
if(judge(i,j,k,x)) return true;
return false;
}
发表于 2017-10-19 12:20:40
回复(0)
原答案在这里：http://blog.csdn.net/damotiansheng/article/details/52160496
大神的思路果然厉害，但是注释的有含糊不清的地方，这里用java重新写了一下
import java.util.*;
public class Main
{
//二分答案，判断可行性时暴力枚举三列的情况，然后横着贪心地扫一遍
//每当四列都满足的时候就砍一刀，满足四次即可，复杂度O(N^4logN)
//计算matrix矩阵中左上顶点(i,j)到右下顶点(x-1,y-1)确定的田地的价值和
public static int cal(int x,int y,int i,int j,int[][] sum)
{
return sum[x][y]-sum[x][j]-sum[i][y]+sum[i][j];
}
//判断x是否小于等于小于田地中最小一块的值
public static boolean judge(int x,int n,int m,int[][] sum)
{
for (int i=1;i<=m-3 ;i++ )
{
for (int j=i+1;j<=m-2 ;j++ )
{
for (int k=j+1;k<=m-1 ;k++ )
{
int last=0,cnt=0;
for (int r=1;r<=n ;r++ )
{
int s1=cal(r,i,last,0,sum);
int s2=cal(r,j,last,i,sum);
int s3=cal(r,k,last,j,sum);
int s4=cal(r,m,last,k,sum);
//当前横切一刀条件满足
if (s1>=x&&s2>=x&&s3>=x&&s4>=x)
{
last=r;
cnt++;
}
}
//表明x小于等于16块田地中的最小值，返回true
if (cnt>=4)
{
return true;
}
}
}
}
return false;
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
while (sc.hasNext())
{
int n=sc.nextInt();
int m=sc.nextInt();
int[][] matrix=new int[n][m];
for (int i=0;i<n ;i++ )
{
String str=sc.next();
for (int j=0;j<m ;j++ )
{
matrix[i][j]=str.charAt(j)-'0';
}
}
//sum[i][j]表示
//左上顶点matrix[0][0]到右下顶点matrix[i-1][j-1]
//确定的的矩阵元素的和
//例如sum[1][1]就表示matrix[0][0];
int[][] sum=new int[n+1][m+1];
for (int i=1;i<=n ;i++ )
{
for (int j=1;j<=m ;j++ )
{
sum[i][j]=sum[i-1][j]+
sum[i][j-1]-sum[i-1][j-1]+matrix[i-1][j-1];
}
}
int left=0,right=sum[n][m],res=0;
while (left<=right)
{
int mid=(left+right)/2;
/*对于题目输入示例中的情况
输入示例
4 4
3332
3233
3332
2323
输出
2
sum矩阵为
0 0 0 0 0
0 3 6 9 11
0 6 11 17 22
0 9 17 26 33
0 11 22 33 43
mid依次为21->10->4->1->2
*/
if (judge(mid,n,m,sum))
{
left=mid+1;
res=mid;
}
else
{
right=mid-1;
}
}
System.out.println(res);
}
sc.close();
}
}
发表于 2017-08-20 17:43:44
回复(10)
题目意思是把这块地分16份，但是当不是4*4的其他情况的矩阵的时候，就有多种切分的情况，每种情况牛牛都会有最小的一块地，这里就有多种最小的情况，然后从这多种最小的情况下，找到最大的一个情况！
发表于 2017-12-18 21:38:54
回复(0)
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.IllegalStateException;
public class Main {
/**
*本题的暴力方法是一刀一个循环，这样总共六个循环，然后遍历，获取每个块的价值，这样就变成O(n^8);
*所以要优化，第一个优化的位置是如何避免每次遍历获取方块的价值，可以通过一个二维数组sum简化。
*sum[i][j]表示土地（0，0）到（i,j）所有小方块的价值的和。利用几何知识，
*我们知道（startX,startY）到（stopX, stopY）区间的价值为 sum[stopX][stopY] - sum[stopX][startY] - sum[startX][stopY] + sum[startX][startY]
*这样处理后，获取矩形中价值的速度优化为O(1);
*第二个优化就是横切。我们的目的是使得16块中价值最小的模块价值尽可能大，如果横切使用三个循环，就没有考虑到价值从小到大的序列。
*我们从价值小到大去切（当前的价值为curValue），如果这样每切一刀，四个方块，都能满足价值大于curValue,那么这一刀就有效，然后去找下一到，如果到最后，超过了四刀，
*则，这是一次有效的切割。但是这不一定是最小的，我们要找到，第一个不成立的，它的前面哪一个就是成立的最大的最小值。此时的复杂度为O(n^5);
*但是我要要注意到价值从和最小到最大，一一遍历是很慢的，所以我们要使用二分去优化，把遍历价值这个复杂度降为O(logN),
*最终我们获得了O(N^4logN)的方法。
*/
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] arrInput = br.readLine().trim().split(" ");
int n = Integer.parseInt(arrInput[0]);
int m = Integer.parseInt(arrInput[1]);
if (n<4 || m <4) {//要满足可以横竖各切三刀
throw new IllegalStateException();
}
int[][] sum = new int[n+1][m+1];
int start = Integer.MAX_VALUE;//记录最小值
for (int i=1; i<=n; i++) {//输入数据，sum是左上角（0，0）到右下角（i，j）表示的矩阵的所有元素之和。这也是动态规划的关键，如果不这样存数据，那么求每个矩阵的值就要遍历，耗费很多时间
char[] arrChar = br.readLine().trim().toCharArray();
for (int j=1; j<=m; j++) {
int valueInput = arrChar[j-1] - '0';
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + valueInput;
if (valueInput < start) {
start = valueInput;
}
}
}
int stop = sum[n][m];
int maxMin = start;
while (start <= stop) {
int middle = (start + stop) / 2;
if (Main.isValid(middle, sum)) {
maxMin = middle;
start = middle + 1;
} else {
stop = middle -1;
}
}
System.out.println(maxMin);
}
public static boolean isValid(int judgeValue, int[][] sum) {
int maxRow = sum.length - 1;
int maxCol = sum[0].length - 1;
for (int i=1; i<=maxCol-3; i++) {//竖切第一刀
for(int j=i+1; j<=maxCol-2; j++) {//竖切第二刀
for (int k=j+1; k<=maxCol-1; k++) {//竖切第三刀
int cnt = 0;//记录横切的第几刀
int lastRow = 0;//记录横切的上一刀的位置
for (int row=1; row<=maxRow; row++) {//横切
int s1 = Main.SumOfSubMatrix(lastRow, 0, row, i, sum);
int s2 = Main.SumOfSubMatrix(lastRow, i, row, j, sum);
int s3 = Main.SumOfSubMatrix(lastRow, j, row, k, sum);
int s4 = Main.SumOfSubMatrix(lastRow, k, row, maxCol, sum);
if (s1>=judgeValue && s2>=judgeValue && s3>=judgeValue && s4>=judgeValue) {//满足条件就记录这一刀为有效
cnt++;
lastRow = row;
}
}
if (cnt>=4) {//大于四刀，说明这样切是可以的
return true;
}
}
}
}
return false;
}
/**
*求子矩阵的元素和
*包含右下角，不包含左上角
*/
public static int SumOfSubMatrix(int startX, int startY, int stopX, int stopY, int[][] sum) {
int sumVal = sum[stopX][stopY] - sum[stopX][startY] - sum[startX][stopY] + sum[startX][startY];
return sumVal;
}
}
发表于 2018-11-02 11:32:33
回复(0)
//============================================================================
// Name : DistributeLand.cpp
// Author : tricoffee
// Version :
// Copyright : Your copyright notice
// Description : DistributeLand in C++, Ansi-style
//============================================================================
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
//记录坐标点(i,j)之前的所有元素(包括坐标点(i,j)在内)之和
void calculate_sum(int **sum,int **a,int n,int m)
{
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{ sum[i][j] = sum[i][j-1]+ sum[i-1][j] \
- sum[i-1][j-1] + a[i][j];
}
}
}
//获得区域：左上(x0,y0)~右下(x1,y1)之间的所有元素（值）的和，即为这个块的值
int getBlockValue(int **sum,int x1,int y1,int x2,int y2)
{
int tmp = sum[x2][y2] - sum[x2][y1] - sum[x1][y2] \
+ sum[x1][y1];
return tmp;
}
//把矩阵（土地）a[n][m]分割成4块,并且满足条件：各个块的值都不小于k;
bool divLandRight(int **sum,int n,int m,int k)
{
for(int i=1;i<=n-3;++i)
{
for(int j=i+1;j<=n-2;++j)
{
for(int p=j+1;p<=n-1;++p)
{ int y1 = 0;
int cnt = 0;
for(int y2=1;y2<=m;++y2)
{
int tmp1 = getBlockValue(sum,0,y1,i,y2);
int tmp2 = getBlockValue(sum,i,y1,j,y2);
int tmp3 = getBlockValue(sum,j,y1,p,y2);
int tmp4 = getBlockValue(sum,p,y1,n,y2);
if(tmp1>=k && tmp2>=k && tmp3>=k && tmp4>=k)
{
cnt += 1;
y1 = y2;
}
if(cnt>=4)
{
return true;
}
}
}
}
}
return false;
}
int main()
{
int n = 0;
int m = 0;
cin >> n >> m;
int **a = new int *[n+1];
int **sum = new int *[n+1];
for(int i=0;i<=n;++i)
{ a[i] = new int[m+1];
sum[i] = new int[m+1];
}
//================================
//get input
char *ch = new char[n+1];
for(int i=1;i<=n;++i)
{
cin >> (ch+1);
for(int j=1;j<=m;++j)
{
a[i][j] = ch[j] - '0';
}
}
delete [] ch;
calculate_sum(sum,a,n,m);
//print_sum(sum,a,n,m);
//================================
int left = 0;
int right = sum[n][m];
int ans = 0;
while(left<=right)
{
int mid = (left+right)/2;
if(divLandRight(sum,n,m,mid))
{
left = mid + 1;
ans = mid;
}
else
{
right = mid - 1;
}
}
//====================
cout << ans << endl;
//释放内存
for(int i=0;i<=n;++i)
{
delete [] a[i];
}
delete [] a;
return 0;
}
编辑于 2018-09-09 10:04:28
回复(0)
思路：假设X是每种切割方法中的最小值，而题目的要求则是求X的最大可能性。因此可用二分法查找，每二分一次则判断一次，是否有满足的切割法可以使最小值大于X，若有的话，说明X太小，若没有则说明X太大，根据相应的情况调整。计算每一块地的大小则是计算该数据块中所有矩阵元素值的和,设(x0,y0)是土地块的左上起始坐标，（x1,y1）为右下结束坐标，则为s[x1][y1]+s[x0][y0]-s[x1]y[0]-s[x0][y1]刚开始连题目都没有读懂，还是看了AC大神的思路才明白，不过不知道为什么我的代码在所有数据全是0的时候不通过，所以我另外加了一个判断，专门用来判断全为0的时候，下面是我的代码加了一些自己的注释，有什么错误，希望大佬们加以指正~代码：//横竖三刀切完之后，每一块土地的价值 def sumPach(x0,y0,x1,y1,land): return s[x1][y1]+s[x0][y0]-s[x0][y1]-s[x1][y0] //判断二分法所找出的val是否满足存在一种切割方式，可以使最小的土地值也大于val def judge(land,n,m,val)://模拟横切三刀，每切一刀都判断一下，如果横切一刀后产生的新土地块的值小于4*val，则这种切割方式肯定不是我们所要寻找的//为什么是4*val，之前没想通，后面想通了，因为横切的时候没有纵切，所以每横切一刀产生的新的土地块相当于是纵切后4块土地合起来的 for r1 in range(1,n-2): if sumPach(0,0,r1,m,land)<4*val:continue for r2 in range(r1+1,n-1): if sumPach(r1,0,r2,m,land)<4*val:continue for r3 in range(r2+1,n): if sumPach(r2,0,r3,m,land)<4*val:continue if sumPach(r3,0,n,m,land)<4*val:continue//贪心算法，遍历每一种纵切的可能性 start,count=0,0 for i in range(1,m+1): if sumPach(0,start,r1,i,land)>=val and sumPach(r1,start,r2,i,land)>=val and sumPach(r2,start,r3,i,land)>=val and sumPach(r3,start,n,i,land)>=val: start = icount = count + 1 if count==4: return True return False n,m=map(int,raw_input().split()) land =[[int(c) for c in raw_input().strip()] for i in range(n)] # sum grid from (x0,y0) to (x1,y1) s=[[0]*(m+1) for i in range(n+1)] for i in range(1,n+1): for j in range(1,m+1): s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+land[i-1][j-1] left=0 right=s[n][m]//先判断，如果s[n][m]=0，则说明所有的land都为0，那样就不必二分法，直接返回0即可 if s[n][m] == 0: print 0 else: while left<right: mid=(left+right)//2 state = judge(land,n,m,mid) if state: left=mid+1 else: right=mid print (right-1)
编辑于 2018-07-05 14:34:42
回复(0)
//这题时间卡的忒紧了，用python超，用cin也超。。
#include <cstdio>
#include <algorithm>
using namespace std;
int A[80][80], B[80][80] = {0};
char cc[80];
int val(int x1, int y1, int x2, int y2) {
return B[x2][y2] - B[x2][y1] - B[x1][y2] + B[x1][y1];
}
bool isOk(int n, int m, int mid) {
for (int i = 1; i < n - 2; ++i) {
for (int j = i + 1; j < n - 1; ++j) {
for (int k = j + 1; k < n; ++k) {
int last = 0, cnt = 0;
for (int t = 1; t <= m; ++t) {
int v1 = val(0, last, i, t);
int v2 = val(i, last, j, t);
int v3 = val(j, last, k, t);
int v4 = val(k, last, n, t);
if (v1 >= mid and v2 >= mid and v3 >= mid and v4 >= mid) {
last = t;
cnt++;
}
if (cnt >= 4)
return true;
}
}
}
}
return false;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) {
scanf("%s", cc);
for (int j = 0; j < m; ++j) {
A[i][j] = cc[j] - '0';
}
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
B[i][j] = B[i][j - 1] + B[i - 1][j] - B[i - 1][j - 1] + A[i - 1][j - 1];
int l = 0, r = B[n][m], d = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (isOk(n, m, mid)) {
d = max(d, mid);
l = mid + 1;
} else
r = mid - 1;
}
printf("%d\n", d);
}
发表于 2017-09-03 22:03:03
回复(0)
狗带了……用了最粗暴的办法，把所有切法遍历一次，果不其然超时了……
知识点是动态规划，可我始终找不到那个关系式，马克一下以后再思考
发表于 2017-08-22 14:13:58
回复(0)
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <vector> #include <queue> #include <map> #include <algorithm> #include <set> using namespace std; #define MM(a,b) memset(a,b,sizeof(a)) #define SC scanf #define PF printf #define CT continue typedef long long ll; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const int inf = 0x3f3f3f3f;; const int N=2*1e5+10; int a[80][80],n,m; int area(int u,int d,int l,int r) { return a[d][r]-a[d][l]-a[u][r]+a[u][l]; } bool ok(int mid) { for(int l1=1;l1<m;l1++) for(int l2=l1+1;l2<m;l2++) for(int l3=l2+1;l3<m;l3++){ int last=0,r,k=4; while(k--){ for(r=last+1;r<=n;r++) if(area(last,r,0,l1)>=mid&&area(last,r,l1,l2)>=mid &&area(last,r,l2,l3)>=mid&&area(last,r,l3,m)>=mid) {last=r;break;} } if(r<=n) return true; } return false; } int main() { while(~SC("%d%d",&n,&m)){ for(int i=1;i<=n;i++){ char s[80];SC("%s",s+1); for(int j=1;j<=m;j++) a[i][j]=s[j]-'0',a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]; } int l=0,r=1e7; while(r-l>1){ int mid=(l+r)>>1; if(ok(mid)) l=mid; else r=mid; } PF("%d\n",l); } return 0; }
发表于 2017-03-19 11:23:25
回复(1)
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 80;
int G[MAXN][MAXN],sum[MAXN][MAXN];
int GetArea(int x1, int y1, int x2, int y2)
{ return sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1];
}
bool Judge(int n, int m, int mid)
{ for(int j1=1;j1<=m-3;j1++) for(int j2=j1+1;j2<=m-2;j2++) for(int j3=j2+1;j3<=m-1;j3++) { int peri = 0, cnt = 0; for(int i=1;i<=n;i++) { int cube1 = GetArea(peri, 0, i, j1); int cube2 = GetArea(peri, j1, i, j2); int cube3 = GetArea(peri, j2, i, j3); int cube4 = GetArea(peri, j3, i, m); if(cube1 >= mid && cube2 >= mid && cube3 >= mid && cube4 >= mid) { peri = i; cnt++; } } if(cnt>=4) return true; } return false;
}
int main()
{ int n,m; cin>>n>>m; for(int i=1;i<=n;i++) { string t; cin>>t; for(int j=1;j<=m;j++) G[i][j] = t[j-1] - '0'; } memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + G[i][j]; int l=0,h=sum[n][m],mid,ans; while(l<=h) { mid = (l+h)>>1; if(Judge(n,m,mid)) { l = mid + 1; ans = mid; }else{ h = mid - 1; } } cout<<ans<<endl; return 0;
}
发表于 2018-01-29 00:52:43
回复(0)
看了大神的思路然后Mark的
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 75 + 5;
int n,m;
int Data[maxn][maxn],sum[maxn][maxn];
int GetArea(int x1,int y1,int x2,int y2){
return (sum[x2][y2] - sum[x2][y1] - sum[x1][y2] + sum[x1][y1]);
}
bool Judge(int mid){
for(int j1=1;j1<=m-3;j1++){
for(int j2=j1+1;j2<=m-2;j2++){
for(int j3=j2+1;j3<=m-1;j3++){
int peri=0,cnt=0;
for(int i=1;i<=n;i++){
int cub1=GetArea(peri,0,i,j1);
int cub2=GetArea(peri,j1,i,j2);
int cub3=GetArea(peri,j2,i,j3);
int cub4=GetArea(peri,j3,i,m);
if(cub1>=mid && cub2>=mid && cub3>=mid && cub4>=mid){
peri=i;
cnt++;
}
}
if(cnt>=4) return true;
}
}
}
return false;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
string temp;
cin>>temp;
for(int j=1;j<=m;j++)
Data[i][j]=temp[j-1]-'0';
}
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+Data[i][j];
}
int low=0,high=sum[n][m],mid,ans;
while(low<=high){
mid=(low+high)>>1;
if(Judge(mid)){
low=mid+1;
ans=mid;
}
else{
high=mid-1;
}
}
cout<<ans<<endl;
return 0;
}
发表于 2017-09-04 10:23:42
回复(2)
问题信息
通过挑战的用户
查看代码-
2022-09-03 17:17:08
-
2022-09-03 16:02:35 -
2022-08-31 11:08:17 -
2022-08-30 00:02:45
-
2022-08-26 22:47:50
相关试题
-
评论(274) 来自网易2017内推笔试编程...
-
评论(183) 来自网易2017内推笔试编程...
-
评论(145) 来自网易2017内推笔试编程...
-
评论(339) 来自网易2017内推笔试编程...
-
评论(340) 来自网易2017内推笔试编程...
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
