注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

蛋糕(cake)解题报告  

2015-08-08 08:27:35|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目描述:

由于信息学成绩好,Bonnie得到了妈妈奖励的一个蛋糕. 蛋糕是正方形的, 蛋糕的正中间有一个正方形的空洞蛋糕和空洞的中心都是在坐标(0,0). 现在Bonnie打算横的切N, 再竖的切M,问蛋糕最后变成了多少块? 给出一个数组hcuts[1..N ],表示横的切蛋糕时, i刀经过的点是(0,  hcuts[i]), 该刀是平行于X轴的直线,切过点(0,  hcuts[i]).  同理: 给出一个数组vcuts[1..M],表示竖的切蛋糕时, j刀经过的点是(vcuts[j], 0), 该刀是平行于Y轴的直线,并且经过点( vcuts[i], 0).    我们还给出蛋糕外正方形的边长的一半: cakeLen, 给出蛋糕里面的空洞的正方形的边长的一半:  holeLen.

输入:

l       第一行: 两个整数:  cakeLenholeLen.  2 <= cakeLen <= 100

    1 <= holeLen  <= cakeLen 1.

l       第二行:两个整数: N 和 M. 表示横的(平行于X轴)切N刀,竖的(平行于Y轴)切M刀。 0 <= N, M <= 50

l       接下来一行有N个整数,则hcuts[ ], 空格分开,第i个整数表示横的切第i刀,它经过点的坐标是:(0, hcuts[i ]. 如果N = 0, 那么该行没有数据。

l       接下来一行有M个整数,则vcuts[ ], 空格分开,第j个整数表示竖的切第j刀,它经过点的坐标是:(vcuts[ j], 0. 如果M = 0, 那么该行没有数据。

 注意:hcuts[ ] 数组里面没有重复的数据,vcuts[ ]也没有重复数据,并且两个数组里面元素的范围都是:[-cakeLen + 1, cakeLen 1

  提示:每次切蛋糕,肯定是把整个蛋糕切开两半,则:不存在,刀不够长而不能把蛋糕完整的切开。

 输出:

一个整数:蛋糕最后变成了多少块?

 样例1:

输入: cake.in

   5   3

   2   1

   1   -4

   1

输出:cake.out

6

如下图所示:

蛋糕(cake)解题报告 - 杨鸿飞 - 一个叫杨鸿飞的人的博客

 

如上图所示:蛋糕的边长是2*5 = 10 空洞的边长是2* 3 = 6

横的切两刀,也就是分别用直线y = 1y = -4 切下去, 竖的切1刀,用直线x = 1切下去。于是最后蛋糕变成了6块,分别用不同的颜色表示。

===========================================================================

两种方法:

    1,数学方法:利用补集的思路,先求出整个蛋糕在没有空洞的情况下能分几块,再求完全在空洞内部的块数,相减即可;

    2,枚举:每一块蛋糕,都是一个长方形,有四个顶点,如果四个顶点都在空洞里,这块就不算。

============================================================================

    程序在此:

数学方法:

#include<cstdio>

#include<iostream>

#include<stdlib.h>

#include<cstring>

#include<algorithm>

#include<fstream>


using namespace std;


int main()

{

freopen("cake.in","r",stdin);

freopen("cake.out","w",stdout);

int cakelen,holelen,n,m,hh=0,ll=0,h=0,l=0;

cin>>cakelen>>holelen;

cin>>n>>m;

for (int i=0; i<n; i++)

{

int s; cin>>s;

if ( s<=cakelen && s>=0-cakelen ) h++;

if ( s<=holelen && s>=0-holelen ) hh++;

}

for (int i=0; i<m; i++)

{

int s; cin>>s;

if ( s<=cakelen && s>=0-cakelen ) l++;

if ( s<=holelen && s>=0-holelen ) ll++;

}

int ans=(l+1)*(h+1),s=0;     //蛋糕面积

s=(ll-1)*(hh-1);    //空洞部分面积

if (ll==0 && hh==0) ans++;  //特殊情况

cout<<ans-s;

return 0; 

}

枚举:下面是梁庆雅神犇的程序
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>

std::ifstream fin ("cake.in");
std::ofstream fout ("cake.out");

bool CK[205][205];
int R[53],L[53];

int main()
{
int cl,hl,n,m;
fin >> cl >> hl >> n >> m;
for(int i=cl-hl;i<=cl+hl;i++)
{
for(int j=cl-hl;j<=cl+hl;j++)
{
CK[i][j]=1;
}
}
R[0]=L[0]=0;
R[n+1]=L[m+1]=2*cl;
for(int i=1;i<=n;i++)
{
fin >> R[i];
R[i]=cl-R[i];
}
    for(int i=1;i<=m;i++)
    {
    fin >> L[i];
    L[i]=L[i]+cl;
    }
    
    std::sort(R+1,R+n+1);
    std::sort(L+1,L+n+1);
   
int ans=0;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
int tsum=0;
if(!CK[R[i]][L[j]]) tsum++;
if(!CK[R[i+1]][L[j]]) tsum++;
if(!CK[R[i]][L[j+1]]) tsum++;
if(!CK[R[i+1]][L[j+1]]) tsum++;
if(tsum>1) ans++;
}
}
fout << ans << '\n';
return 0;
}
  评论这张
 
阅读(6)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018