【题目描述】
在 N 条水平线与 M 条竖直线构成的网格中,放 K 枚石子,每个石子都只能放在网格的交叉点上。问在最优的摆放方式下,最多能找到多少四边平行于坐标轴的长方形,它的四个角上都恰好放着一枚石子。
【输入】
输入文件包含多组测试数据。
第一行,给出一个整数T,为数据组数。接下来依次给出每组测试数据。
每组数据为三个用空格隔开的整数 N,M,K。
3 3 3 8 4 5 13 7 14 86
【输出】
对于每组测试数据,输出一行"Case #X: Y",其中X表示测试数据编号,Y表示最多能找到的符合条件的长方形数量。所有数据按读入顺序从1开始编号。
Case #1: 5 Case #2: 18 Case #3: 1398
【题解】
首先先考虑对于一个布满点的矩形(x行,Y列),所有的矩形总数为 C(2,x)*C(2,y)。要使数量最多,则x和y要尽可能接近(有最大行和最大列的限制)。 题中所给的K可能不能刚好排成大矩形,可能有多余的几个点,这几个点的数量一定不会超过一行或一列的最大数量。 试想如果超过,则多出来完整的一行或一列可以和原来的大矩形构成更大的矩形,剩下的点就不能构成完整的一行或一列了。
多余多出来的点,以一排或一列的形式,靠在大矩形短的一边(要注意是否到达边界),设多余K个点,则多增加的矩形数为 C(2,K)*L (L为长边的点数)。
为了简单起见,可以规定行大于列(对调旋转下),枚举 X、Y的有效极大组合,找出最大的结果就行了。
AC代码:
1 #include <stdio.h> 2 #include <string.h> 3 #include <math.h> 4 int n,m,k; 5 void swap(int &a,int &b) 6 { 7 int t=a; 8 a=b; 9 b=t; 10 } 11 long long getc(long long j) 12 { 13 return j*(j-1)/2; 14 } 15 int main() 16 { 17 int T; 18 scanf("%d",&T); 19 int cas=0; 20 while (T--) 21 { 22 scanf("%d%d%d",&n,&m,&k); 23 if (n<m) swap(n,m); 24 int t=sqrt(k); 25 int b=t>m?m:t; 26 int a=k/b>n?n:k/b; 27 long long max=0; 28 for (;b>=2 && a<=n;--b,a=k/b) 29 { 30 long long sum=getc(a)*getc(b); 31 int p=k-a*b; 32 if (a<n) 33 { 34 sum=sum+getc(p)*a; 35 } 36 else 37 { 38 sum=sum+getc(p)*b; 39 } 40 max=max>sum?max:sum; 41 } 42 printf("Case #%d: %I64d\n",++cas,max); 43 } 44 45 return 0; 46 }
相关推荐
信息学奥赛一本通2081:【21CSPS提高组】交通规划(traffic)
是本人自己做的一个代码 用vc的 是图形学中画直线的趋势走向 可以很清楚的看到机器是如何实现一条直线的
VB 6.0 使用Line方法画网格线,文字下面的网格背景线,是基于VB中的Line方法绘制出来的,学习一下简单的VB绘图技巧,核心代码: Private Sub Form_Load() Show Scale (0, 0)-(10, 10) '自定义坐标系 ...
等值线是一种离散数据的图形表示方法,在水利、土木、地质、石油勘探等工程和技术领域内广泛的应用。常规的等值线绘制通常采用网格法,其绘制的步骤一般为:离散数据网 格化;等值点的计算;等值线的追踪;光滑和...
Android 开发 Camera拍照出现竖线,与硬件 cache 相关
司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成,地图的每一格可能是山地(用"H" 表示),也可能是平原(用"P"表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队...
给定(n+1)×(m+1)个空间点阵r_ij(i=0,1,…,nj;j=0,1,…,m),双三次B样条曲面可分块表示为 r_l,k(u,v)=∑3i=0∑3 j=0 Ei,3(u)Ej,3(v)r(i+l)(j+k), 0≤u,v≤1,l=0,1,…,n-3,k=0,1,…,m-3(211) 其中 基函数为 E0,...
不错的一个小程序,保管看的懂,如何在对话框上画网格
基本图形的生成基本图形的生成基本图形的生成基本图形的生成
在WORD中使用网格进行对齐,本篇主要讲解的是对齐方法以及网格的设置方法
VB 'InNum-ÊäÈëÊý,nDec-СÊýλÊý,nWidth-¿í¶È,IC-×óÓÒ¶ÔÆë±êÖ¾,OutStr-Êä³ö×Ö·û´® Public Function Formats(InNum As Variant, cFormat As String) As String ...
matlab编写的,计算射线穿过网格的一系列坐标,对于射线追踪以及射线与坐标网格求交点!!!
本人在使用ctrllist的时候,遇到这样一个问题,就是ctrllist(report型的)每行之间没有分割线,看起来不方便,后来经过研究发现有一个LVS_EX_GRIDLINES风格说是加网格线的,可在打印的时候就是不行,于是参考网上...
四面体网格与六面体网格的比较,可以供大家参考一下。
在当前图表上创建水平网格线, 以便进行价格行为分析
word显示和使用网格线与参考线.docx
线段、射线课件有利于教师上课,学生学习带来方便。
《网格系统与版式设计》通过大量20世纪的经典设计案例,包括包豪斯的平面设计和耐克的产品目录,从构成要素与程序入手,对网格系统做出了通俗易懂的介绍,讲解了网格系统的应用法则,并提供了详细的版式设计步骤。...
汽车车门把手有限元网格模型
自绘CListCtrl(实现格子网状,去掉竖线)