| 题目名称 | 160. [USACO Oct07] 贝茜的秘密牧场 |
|---|---|
| 输入输出 | secpas.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 BYVoid
于2008-10-07加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：171， 提交：248， 通过率：68.95% | ||||
 cy |
100 | 0.000 s | 0.00 MiB | C++ |
|
莫知 |
100 | 0.000 s | 0.00 MiB | C++ |
 Sky_miner |
100 | 0.000 s | 0.00 MiB | C++ |
 AAAAAAAAAA |
100 | 0.000 s | 0.00 MiB | C++ |
 Youngsc |
100 | 0.000 s | 0.00 MiB | C++ |
 䱖虁職 |
100 | 0.000 s | 0.00 MiB | C++ |
 ┭┮﹏┭┮ |
100 | 0.000 s | 0.00 MiB | C++ |
 HeHe |
100 | 0.000 s | 0.05 MiB | C++ |
 奶猹 |
100 | 0.002 s | 0.29 MiB | C++ |
 Ezoi_XY |
100 | 0.002 s | 0.32 MiB | C++ |
| 关于 贝茜的秘密牧场 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
智障一样忘记输出文件了
跪了一遍  | ||||
|
话说，我总觉得这是个01背包
 _Itachi
2016-09-05 10:22
8楼
| ||||
|
DFS加了各种优化后从接近3s到1.44s，我是不是太无聊了
| ||||
|
用完全背包统计方案数的方法A掉
| ||||
|
题目中的描述：那么她可以有5种不同的方法选4块草皮： (1,1,1,1),(2,0,0,0),(0,2,0,0),(0,0,0,2)
的正确解读方法为：那么她可以有5种不同的方法选4块草皮： (1,1,1,1),(2,0,0,0),(0,2,0,0),(0,0,2,0),(0,0,0,2) 其中的数字为正方形的边长… 打表是什么可以吃吗0 0！ | ||||
|
直接深搜，但我一开始从0到n去搜，超时，于是改为搜到sqrt(n)就OK鸟= =.....
| ||||
|
Common Brute Force O(n^2)(超1组)
Better Brute Force Ｏ（ｎ＊ｎ＊０．５）(可AC) A little Skill O(n) | ||||
|
小号……
如需要生成打表程序， 请自行删除int main(void)中的注释符号。 | ||||
|
DFS有一组不过，
打表算法尝试中…… 打表果断全过。 小号（楼下）附带打表程序全自动生成工具。 | ||||
open the window
liu_runda
水中音
raywzy
QhelDIV
201101
Truth.Cirno【题目描述】
农夫约翰最近从他的牧场中收获了无限多块正方形草皮，草皮的边长总是整数（有时农夫约翰割草皮的刀法不合适，甚至切出了边长为0的正方形草皮），他把草皮放在了奶牛贝茜知道的地方。
贝茜希望把美味的草皮放在她的秘密庄园里，于是她决定从这些草皮中选取4块种到她的庄园，然后把它们分成1×1的小块，组成一个面积为N(1<=N<=10,000)个单位面积的草坪。
Bessie感兴趣的是，她若选取四块会有多少种不同方法。如果N=4，那么她就有5种不同分发：(1,1,1,1),(2,0,0,0),(0,2,0,0),(0,0,2,0),(0,0,0,2)，括号内数表示边长。注意这里要考虑顺序，如(1,2,3,4)与(4,3,2,1)是两种不同方法。
【输入格式】
第一行：一个单独的整数N。
【输出格式】
单独的一行包含一个整数，表示贝茜选四块草皮的方案数。
【输入样例】
4
【输出样例】
5