集训队作业0059-burmuda题目0059Burmuda百慕大三角的蛋糕

1、题目 0059 Burmuda（百慕大三角的蛋糕）题目来源：Tehran01者：林希德一、英文原文The Bermuda Trianglehe hidden region of the Bermuda Triangle make everything they needPeopleriangularshs. One day, someone decided to break the rule and bake a hexagonally shd cake. But asusual, he has to serve the cake in triangular pie. The pieare e

2、quilateral triangles but indifferent sizes for different people. He can use as many triangles as needed to cut the cakeopie, sucht nothing remains from the cake. For exle, the following figure showsayt a hexagon with side 9 can be cuto triangles with side 2 and 3. (The cake is cut along thethick lin

3、es, thin lines are drawn to show the sizes).Input is a hexagon and triangle types (specified by the length of their sides) and the goal is to decide if the hexagon can be compley divided by the given triangle types.Inputeger t (1 t 10), the number of test cases,Theline of the input file contains a s

4、inglefollowed by the input data for each test case. Each test case consists of a single line, containing s(1 s 25), the length of the hexagone, followed by n, the number of triangle types (1 n 10), followed by ninclusive).Outputegers representing the length of each triangle typee (betn 1 and 25,Ther

5、e should be one output line per test case containing either YES or NO depending on whetherthe hexagon can be compley divided by the given triangle types.S357le Input2 2 32 3 213 2 2 3Sle OutputNO NOYES二、中文翻译百慕大三角的蛋糕一位百慕大三角的糕点师傅打算用一些正三角形的蛋糕拼成一块正六边形的蛋糕。现在给你正六边形蛋糕的边长 s（s25）以及 n（n10）种正三角形蛋糕的边长（正三角形蛋糕数量不

6、限），请你告诉糕点师傅打算能否成功实现。例如下图就是用边长为 2 和 3 的正三角形蛋糕拼成的边长为 9 的正六边形蛋糕。输入文件第一行包含整数 t (1 t 10)表示有 t 个测试数据。每个测试数据仅由一行组成，头两个数是整数 s 和 n，其后有 n 个不超过 25 的正整数，表示 n 种正三角形蛋糕的边长。输出针对每个数据输出 YES 或者 NO 表示糕点师傅的愿望能否实现。样例输入35 2 2 37 2 3 213 2 2 3样例输出NO NOYES三、初步情况搜索搜吧！典型的搜索题。搜索吧！昆只想到搜索除了搜没别的想法璟除了搜索，应该有数学方法吧？恐怕真的是NP没什么思路。应该是搜索

7、吧。复杂的搜索题目。我目前没好的猜想，不过建议把问题化简，变成正方形，这样会得到的好的猜想以及剪枝条件。这道题目，可以用数学方法在判断继续划分无解时有一定的优化，不过有时可能时间复杂度更高，暂时没很好的判定方法由于是正六边形，不像正方形那样规则，题目的数据量又较小，所以还是用搜索来解决比较好。不知道是否可以贪心从一个角上开始用某种边长的正三角形覆盖一个小的正六边形、或是平行四边形？林希德仍然是搜索，不过有一些优化：1、 将正六边形分成 6 个正三角形，转而判断正三角形是否可被覆盖2、 将正六边形分成 3 个菱形，转而判断菱形是否可被覆盖3、 将正六边形分成 2 个梯形，转而判断梯形是否可被覆盖

8、4、 最后判断正六边形是否可被覆盖从数据规模上看，出题人只想到了搜索。但是即使是搜索也有优化的余地，例如先看六变形的 1/6 是否有解，再看 1/3 是否有解，再看 1/2 是否有解，这样可以通过大多数数据。好像可以先将正六边形分成 6 个一样的正三角形，然后看每个正三角形是否能被完全覆盖；的话可以考虑分成 3 个一样的菱形；再的话分成 2 个一样的梯形；最后则为正六边形。这样可能可以稍微减少一点搜索的复杂度。目前还没有自己做过。我觉得，如果搜索的话，不要先急着去搜索整个六边形，可以先试着搜索能不能拼成正六边形的 1/6（就是正三角形），如果再去搜索能不能拼成正六边形的 1/3（就是两个整三角形拼成的菱形），再就去搜索正六边形的