2013编程之美 资格赛 长方形

0.00 avg. rating (0% score) - 0 votes
转载请注明: 吹水小镇 | reetsee.com
原文链接地址: http://blog.reetsee.com/archives/26

做这题的时候,资格赛已经结束了,不过出于兴趣,就做了一下,虽然没办法提交,但是代码较短,思路还算清晰,所以也贴出来先,标准代码可以参见“其它参考”部分。

要注明的是:这里的代码并没有提交,我不知道答案对错,所以下面的解题思路也是我写这个代码时的思路,不一定正确,如果有错,还请一定指出!多谢!


题目描述:

时间限制: 1000ms 内存限制: 256MB

描述

在 N 条水平线与 M 条竖直线构成的网格中,放 K 枚石子,每个石子都只能放在网格的交叉点上。问在最优的摆放方式下,最多能找到多少四边平行于坐标轴的长方形,它的四个角上都恰好放着一枚石子。

输入

输入文件包含多组测试数据。

第一行,给出一个整数T,为数据组数。接下来依次给出每组测试数据。

每组数据为三个用空格隔开的整数 N,M,K。

输出

对于每组测试数据,输出一行”Case #X: Y”,其中X表示测试数据编号,Y表示最多能找到的符合条件的长方形数量。所有数据按读入顺序从1开始编号。

数据范围

1 ≤ T ≤ 100

0 ≤ K ≤ N * M

小数据:0 < N, M ≤ 30

大数据:0 < N, M ≤ 30000

样例输入

3

3 3 8

4 5 13

7 14 86

样例输出

Case #1: 5

Case #2: 18

Case #3: 1398

 

解题思路:

/*

最多长方形的情况就是恰好所有点分别形成边长为1的单位正方形,然后所有单位正方形恰好能组成一个大正方形。

但是有时不会这么“好彩”,可能会出现多出几个点的情况,设多出点的数目为z,假设原本的正方形是a*a,那么就要进行以下检查

1. 多出的点是否能够让正方形变成a*(a+l)的长方形,如果可以那么变成这个长方形,z=z-a*l

2. 检查长方形的长边(a+l)有没有超出最大范围,如果超出,削减至和最大范围一致,然后将多出来的点加到z

3. 多出的点不能够增加长方形,那么就优先全部排到长方形的短边上,如果超出最大范围,则排到长边上 

4. 计算长方形个数

但是这里也有个问题,假如n和m非常大,给你21个点,那么排成4*4的长方形后,剩下5个点,那么这5个点应该是拆成4+1,增加一条边,而剩下一个没用的点,还是说拆成3+2,分别排在正方形的两边呢?

我用自己非常屎的数学算了一下,貌似还是应该优先按照4+1的方法,尽量增加长方形长边的长度···

现在忽然又觉得很捶春的是那个检测系统关闭了,让我没办法验证代码,至于参考代码我还没看···迟点看看说不定就有答案,或者别人根本不是用这个方法。

*/

刚刚瞥了一眼发现别人代码短得不行···惭愧啊,然后我比对了一下数据,我的代码是错的,不误人子弟了

注意:

//主要注意的地方就是长方形的边长不能超过最大范围,要作判断

 

代码:下面这个是错的

#include<stdio.h>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
	bool ax;
	int tc;
	long long i,j,n,m,k,x,y,z,cnt=0;
	long long ans;
	scanf("%d",&tc);
	while(tc--)
	{
		ax=false;
		ans = 0;
		scanf("%lld%lld%lld",&n,&m,&k);
		if(n>m)
			swap(n,m);

		if(n*n<k)
		{	
			x=n;
			y=k/n;
			z=k-x*y;
		}
		else
		{
			x=y=sqrt(k);
			z=k-x*y;
			y+=(z/x);
			z%=x;
			if(y>m)
			{
				z+=(y-m)*x;
				y=m;
				ax=true;
			}
		}
		//得到长、宽、剩余量,长的一边用y表示

		for(i=1;i<x;++i)
		{
			for(j=1;j<y;++j)
			{
				ans+=(y-j)*(x-i);
			}
		}
		long long tx=2,ty=z;
		long long tmp=0;
		for(i=1;i<tx;++i)
		{
			for(j=1;j<ty;++j)
			{
				tmp+=(ty-j)*(tx-i);
			}
		}
		if(ax)
		{
			ans+=tmp*x;
		}
		else
			ans+=tmp*y;
		printf("Case #%lld: %lld\n",++cnt,ans);
	}
}

其它参考:

//第二题来自 mochavic
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
long long f(long long x){
    return x * (x - 1) / 2;
}
int main(){
    long long ans = 0;
    int T, n, m, k, ri = 1, x, y, z;
    scanf("%d", &T);
    while (T--){
        scanf("%d%d%d", &n, &m, &k);
        ans = 0;
        for (x = 1; x <= n; x++){
            y = k / x;
            z = k % x;
            if (y + (z?1:0) > m) continue;
            ans = max(f(x) * f(y) + y * f(z), ans);
        }
        for (x = 1; x <= m; x++){
            y = k / x;
            z = k % x;
            if (y + (z?1:0) > n) continue;
            ans = max(f(x) * f(y) + y * f(z), ans);
        }
        cout << "Case #" << ri++ << ": " << ans << endl;
    }
    return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注