[2018.04.17][水][日志][7][#188][USACO 3.1 Shaping Regions][漂浮大陆][背景-amp;amp;amp;gt;][表示为什么如此虚伪+纯模拟一只]

本文主要是介绍[2018.04.17][水][日志][7][#188][USACO 3.1 Shaping Regions][漂浮大陆][背景-amp;amp;amp;gt;][表示为什么如此虚伪+纯模拟一只],希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

[背景]

    这是我发的多少道模拟题了......

    本道题表面和善,内在虚伪,因为,如果用纯模拟,你的程序将一塌糊涂..

[#188][USACO 3.1 Shaping Regions]

题目描述
N个不同的颜色的不透明的长方形(1 <= N <= 1000)被放置在一张宽为A长为B的白纸上。
这些长方形被放置时,保证了它们的边与白纸的边缘平行。
所有的长方形都放置在白纸内,所以我们会看到不同形状的各种颜色。坐标系统的原点(0,0)设在这张白纸的左下角,而坐标轴则平行于边缘。 
输入格式
按顺序输入放置长方形的方法。第一行输入的是那个放在底的长方形(即白纸)。 
第 1 行: A , B 和 N, 由空格分开 (1 <=A, B<=10,000) 
第 2 到N+1行: 为五个整数 llx, lly, urx, ury, color 这是一个长方形的左下角坐标,右上角坐标和颜色。 
颜色 1和底部白纸的颜色相同。 (1 <= color <= 2500) 
输出格式
输出文件应该包含一个所有能被看到颜色连同该颜色的总面积的清单( 即使颜色的区域不是连续的),按color的增序顺序。 
不要显示没有区域的颜色。 
样例数据
input
20 20 3
2 2 18 18 2
0 8 19 19 3
8 0 10 19 4
output
1 91
2 84
3 187

4 38

[分析]

    这道题虚伪就虚伪在数据量上,如果使用O(n^2)算法暴搜,我们将:1,定义不了那么大的数组2.严重超时

    现在就GG了,怎么做才比较虚伪地AC呢?

    根据大神的说法,我们引入一个新名词,“漂浮法”,类似于...向菜刀上落饼干,饼干会一份两半移开....

    这就为递归打好了准备...


很好!程序的主体已经完成,现在只要虚伪出核心代码了!


总结来说,我们在思考这类题目时可以考虑一反常识,进行计算

[code]

#include<bits/stdc++.h>
using namespace std;
int x_1[1002],y_1[1002],x_2[1002],y_2[1002];
int color[1002]={1},cnt[2502],N;
void cover(int lx,int ly,int rx,int ry,int c,int h);
int main(void)
{
	cin>>x_2[0]>>y_2[0]>>N;
	for(int i=1;i<=N;i++)	cin>>x_1[i]>>y_1[i]>>x_2[i]>>y_2[i]>>color[i];
cnt[color[N]]+=(y_2[N]-y_1[N])*(x_2[N]-x_1[N]);
for(int i=N-1;i>=0;i--)	cover(x_1[i],y_1[i],x_2[i],y_2[i],color[i],i+1);
for(int i=1;i<=2500;++i)	if(cnt[i])	cout<<i<<" "<<cnt[i]<<endl;
	return 0;
}
void cover(int lx,int ly,int rx,int ry,int c,int h)
{
	if(lx==rx||ly==ry)	return;
	if(h>N)	cnt[c]+=(rx-lx)*(ry-ly);
	else
	{	if(ly<y_1[h])	cover(min(lx,x_2[h]),ly,min(rx,x_2[h]),min(y_1[h],ry),c,h+1);	if(rx>x_2[h])	cover(max(x_2[h],lx),min(y_2[h],ly),rx,min(y_2[h],ry),c,h+1);	if(ry>y_2[h])	cover(max(lx,x_1[h]),max(y_2[h],ly),max(rx,x_1[h]),ry,c,h+1);	if(lx<x_1[h])	cover(lx,max(y_1[h],ly),min(x_1[h],rx),max(y_1[h],ry),c,h+1);
	}
	return;
}

这篇关于[2018.04.17][水][日志][7][#188][USACO 3.1 Shaping Regions][漂浮大陆][背景-amp;amp;amp;gt;][表示为什么如此虚伪+纯模拟一只]的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/682642

相关文章

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

golang 日志log与logrus示例详解

《golang日志log与logrus示例详解》log是Go语言标准库中一个简单的日志库,本文给大家介绍golang日志log与logrus示例详解,感兴趣的朋友一起看看吧... 目录一、Go 标准库 log 详解1. 功能特点2. 常用函数3. 示例代码4. 优势和局限二、第三方库 logrus 详解1.

如何自定义Nginx JSON日志格式配置

《如何自定义NginxJSON日志格式配置》Nginx作为最流行的Web服务器之一,其灵活的日志配置能力允许我们根据需求定制日志格式,本文将详细介绍如何配置Nginx以JSON格式记录访问日志,这种... 目录前言为什么选择jsON格式日志?配置步骤详解1. 安装Nginx服务2. 自定义JSON日志格式各

SpringBoot项目使用MDC给日志增加唯一标识的实现步骤

《SpringBoot项目使用MDC给日志增加唯一标识的实现步骤》本文介绍了如何在SpringBoot项目中使用MDC(MappedDiagnosticContext)为日志增加唯一标识,以便于日... 目录【Java】SpringBoot项目使用MDC给日志增加唯一标识,方便日志追踪1.日志效果2.实现步

SQL Server清除日志文件ERRORLOG和删除tempdb.mdf

《SQLServer清除日志文件ERRORLOG和删除tempdb.mdf》数据库再使用一段时间后,日志文件会增大,特别是在磁盘容量不足的情况下,更是需要缩减,以下为缩减方法:如果可以停止SQLSe... 目录缩减 ERRORLOG 文件(停止服务后)停止 SQL Server 服务:找到错误日志文件:删除

CSS模拟 html 的 title 属性(鼠标悬浮显示提示文字效果)

《CSS模拟html的title属性(鼠标悬浮显示提示文字效果)》:本文主要介绍了如何使用CSS模拟HTML的title属性,通过鼠标悬浮显示提示文字效果,通过设置`.tipBox`和`.tipBox.tipContent`的样式,实现了提示内容的隐藏和显示,详细内容请阅读本文,希望能对你有所帮助... 效

grom设置全局日志实现执行并打印sql语句

《grom设置全局日志实现执行并打印sql语句》本文主要介绍了grom设置全局日志实现执行并打印sql语句,包括设置日志级别、实现自定义Logger接口以及如何使用GORM的默认logger,通过这些... 目录gorm中的自定义日志gorm中日志的其他操作日志级别Debug自定义 Loggergorm中的

SpringBoot项目注入 traceId 追踪整个请求的日志链路(过程详解)

《SpringBoot项目注入traceId追踪整个请求的日志链路(过程详解)》本文介绍了如何在单体SpringBoot项目中通过手动实现过滤器或拦截器来注入traceId,以追踪整个请求的日志链... SpringBoot项目注入 traceId 来追踪整个请求的日志链路,有了 traceId, 我们在排

Spring Boot整合log4j2日志配置的详细教程

《SpringBoot整合log4j2日志配置的详细教程》:本文主要介绍SpringBoot项目中整合Log4j2日志框架的步骤和配置,包括常用日志框架的比较、配置参数介绍、Log4j2配置详解... 目录前言一、常用日志框架二、配置参数介绍1. 日志级别2. 输出形式3. 日志格式3.1 PatternL

css渐变色背景|<gradient示例详解

《css渐变色背景|<gradient示例详解》CSS渐变是一种从一种颜色平滑过渡到另一种颜色的效果,可以作为元素的背景,它包括线性渐变、径向渐变和锥形渐变,本文介绍css渐变色背景|<gradien... 使用渐变色作为背景可以直接将渐China编程变色用作元素的背景,可以看做是一种特殊的背景图片。(是作为背