USACO Section 1.4 Packing Rectangles

2024-09-05 03:58

文章标签 1.4 usaco section packing rectangles

本文主要是介绍USACO Section 1.4 Packing Rectangles，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

已知4个矩形的l和w 矩形可以旋转和平移用一块最小面积的新的矩形覆盖4个矩形

求最小的面积以及新矩形的l和w

思路：

题目已经给出6种摆放方式按它的方式摆即可

我们要枚举4个矩形是否旋转（只转90度）过然后枚举每种摆放方式中矩形的编号

代码中的枚举方法是二进制枚举旋转全排列枚举编号

最后计算所有情况中的答案

第6种摆放方式比较难想大致思路就是先放下面两块在根据下面两块的高度分别讨论上面两块如何摆放

/*
ID: housera1
PROG: packrec
LANG: C++
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;struct rectangle
{int l,w

这篇关于USACO Section 1.4 Packing Rectangles的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

http://www.chinasem.cn/article/1137882。 23002807@qq.com

相关文章

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路： 1. 用一个 hash[ ] 数组存放输入的数字，令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ，检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999，第二行数从 10到99。 4. 剪枝。代码： /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

阅读更多...

usaco 1.3 Calf Flac（暴搜）

usaco 1.3 Calf Flac（暴搜）

思路是暴搜。需要注意的地方是输入的方法，以及输出时的换行。代码： /*ID: who jayLANG: C++TASK: calfflac*/#include<stdio.h>#include<string.h>#include<math.h>int main(){freopen("calfflac.in","r",stdin);freopen("calfflac.ou

阅读更多...

usaco 1.3 Barn Repair（贪心）

usaco 1.3 Barn Repair（贪心）

思路：用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序，选取最大的M-1个作为间隙，其余地方用木板盖住。做法： 1.若，板（M）的数目大于或等于牛棚中有牛的数目（C），则目测给每个牛牛发一个板就为最小的需求~ 2.否则，先对牛牛们的门牌号排序，然后用一个数组 blank[ ] 记录两门牌号之间的距离，然后用数组 an

阅读更多...

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c

阅读更多...

usaco 1.2 Palindromic Squares（进制转化）

usaco 1.2 Palindromic Squares（进制转化）

考察进制转化注意一些细节就可以了直接上代码： /*ID: who jayLANG: C++TASK: palsquare*/#include<stdio.h>int x[20],xlen,y[20],ylen,B;void change(int n){int m;m=n;xlen=0;while(m){x[++xlen]=m%B;m/=B;}m=n*n;ylen=0;whi

阅读更多...

usaco 1.2 Name That Number（数字字母转化）

usaco 1.2 Name That Number（数字字母转化）

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字需要注意的是重新开一个数组 c [ ] 存储字符串应人为的在末尾附上 ‘ \ 0 ’ 详见代码： /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

阅读更多...

usaco 1.2 Milking Cows（类hash表）

usaco 1.2 Milking Cows（类hash表）

第一种思路被卡了时间到第二种思路的时候就觉得第一种思路太坑爹了代码又长又臭还超时！！第一种思路：我不知道为什么最后一组数据会被卡超时超了0.2s左右大概想法是快排加一个遍历先将开始时间按升序排好然后开始遍历比较 1 若下一个开始beg[i] 小于 tem_end 则说明本组数据与上组数据是在连续的一个区间取max( ed[i],tem_end ) 2 反之这个

阅读更多...

usaco 1.2 Transformations（模拟）

usaco 1.2 Transformations（模拟）

我的做法就是一个一个情况枚举出来注意计算公式：（变换后的矩阵记为C）顺时针旋转90°：C[i] [j]=A[n-j-1] [i] （旋转180°和270° 可以多转几个九十度来推）对称：C[i] [n-j-1]=A[i] [j] 代码有点长。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

阅读更多...

usaco 1.1 Broken Necklace（DP）

usaco 1.1 Broken Necklace（DP）

直接上代码接触的第一道dp ps.大概的思路就是先从左往右用一个数组在每个点记下蓝或黑的个数再从右到左算一遍最后取出最大的即可核心语句在于：如果 str[i] = 'r' , rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' , bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w', bl[i]=b

阅读更多...

炮弹【USACO】

炮弹【USACO】

题目背景时/空限制：1s / 64MB 题目描述贝茜已经精通了变成炮弹并沿着长度为 N 的数轴弹跳的艺术，数轴上的位置从左到右编号为 1,2,…,N 。她从某个整数位置 S 开始，以 1 的起始能量向右弹跳。如果贝茜的能量为 k ，则她将弹跳至距当前位置向前距离 k 处进行下一次弹跳。从 1 到 N 的每个整数位置上均有炮击目标或跳板。每个炮击目标和跳板都有一个在 0 到

阅读更多...