题意分析:
有编号为A-I的9个时钟,时钟只有指向3、6、9、12四种状态,一次转动只能顺时针转90度,已知9种转动方式,每种转动方式指定不同的几个钟顺时针转90度,要使所有钟都回到12点,根据不同的输入,要如何组合这9种转动方式呢?找出最短序列,同样长度的情况下以序列编号小为先。
解题思路1:
某一种转动方式若使用4次即没使用。因此1-9每一种转动方式至多使用4次,因此9种转动方式最多产生4(enum 0...3)^9=262144个序列,使用dfs完全遍历也不会超时。保存每次产生的有效序列结果,全部遍历完成后,按序列长度和数字大小排序,输出第一个结果。
代码实现1:
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/clocks.java
解题思路2:
有以下改进余地:
1)产生序列时,可先尽量多得产生标号小的。每次标号产生完毕后,检查序列长度以及有效性,若序列较短则替换原有的长度及序列。
2)时钟的状态不需要每次重新算,可以作为搜索的状态跟着跑。
代码实现2:
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/clocks_refined.java
本题的数据比较弱,细节上有失误也许也会过。
有编号为A-I的9个时钟,时钟只有指向3、6、9、12四种状态,一次转动只能顺时针转90度,已知9种转动方式,每种转动方式指定不同的几个钟顺时针转90度,要使所有钟都回到12点,根据不同的输入,要如何组合这9种转动方式呢?找出最短序列,同样长度的情况下以序列编号小为先。
解题思路1:
某一种转动方式若使用4次即没使用。因此1-9每一种转动方式至多使用4次,因此9种转动方式最多产生4(enum 0...3)^9=262144个序列,使用dfs完全遍历也不会超时。保存每次产生的有效序列结果,全部遍历完成后,按序列长度和数字大小排序,输出第一个结果。
代码实现1:
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/clocks.java
解题思路2:
有以下改进余地:
1)产生序列时,可先尽量多得产生标号小的。每次标号产生完毕后,检查序列长度以及有效性,若序列较短则替换原有的长度及序列。
2)时钟的状态不需要每次重新算,可以作为搜索的状态跟着跑。
代码实现2:
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/clocks_refined.java
本题的数据比较弱,细节上有失误也许也会过。
发表评论
-
USACO Section 1.5.4 [Checker Challenge] Java题解
2011-07-15 23:16 1662题意分析: 该题是需要深度优化的八皇后问题,首先看一下,经典八 ... -
USACO Section 1.5.3 [Superprime Rib] Java题解
2011-07-15 22:24 1506题意分析: 7331是素数,733是素数,73是素数,7也是素 ... -
USACO Section 1.5.2 [Prime Palindromes] Java题解
2011-07-15 22:12 1412题意分析: 找出a和b间既对称既是素数的数。 解题思路: 用 ... -
USACO Section 1.5.1 [Number Triangles] Java题解
2011-07-15 21:21 754题意分析: 数字三角形,找到从顶到底的最大和的通路。 解题思 ... -
USACO Section 1.4.4 [Mother's Milk] Java题解
2011-07-15 18:57 1271题意分析: 有容量为A,B,C的三个牛奶桶,容量范围为1-20 ... -
USACO Section 1.4.3 [Arithmetic Progressions] Java题解
2011-07-15 16:38 1810题意分析: 定义算术级数:一种序列a, a+b, a+2b, ... -
USACO Section 1.4.1 [Packing Rectangles] Java题解
2011-07-14 17:18 1862题意分析: 给出4个长方形的高和长,以及给出6种基本布局,求合 ... -
USACO Section 1.3.4 [Prime Cryptarithm] Java题解
2011-07-10 14:36 1415题意分析: 已知数字1-9组成集合的一个子集,求满足题意乘法步 ... -
USACO Section 1.3.3 [Calf Flac] Java题解
2011-07-10 14:35 1306题意分析: 一眼看上去,又是找对称的,不过有一些明显的干扰因素 ... -
USACO Section 1.3.2 [Barn Repair] Java题解
2011-07-10 14:33 1197题意分析: C头奶牛在畜栏里(一个畜栏里最多只能有一头奶牛), ... -
USACO Section 1.3.1 [Mixing Milk] Java题解
2011-07-10 14:30 933题意分析: 牛奶收购站每天需要收购总量为N加仑牛奶,告诉你每天 ... -
USACO Section 1.2.5 [Dual Palindromes] Java题解
2011-07-08 21:49 885题意分析: 这题和上一题基本是一样的,输出N个大于S的Dual ... -
USACO Section 1.2.4 [Palindromic Squares] Java题解
2011-07-08 21:43 977题意分析: N固定为10进制的1-300,N的平方表示成B进制 ... -
USACO Section 1.2.3 [Name That Number] Java题解
2011-07-08 21:40 1291题意分析: 奶牛们原来只有由四个数字组成的编号,例如4734, ... -
USACO Section 1.2.2 [Transformations] Java题解
2011-07-08 21:37 832题意分析: 给定N*N的二维数组的变化前和变化后的情况,思考如 ... -
USACO Section 1.2.1 [Milking Cows] Java题解
2011-07-07 15:39 1272题意分析: 输入为N组 [900,1800],[1200,22 ... -
USACO Section 1.1.4 [Broken Necklace] Java题解
2011-07-06 20:41 1279题意分析: 一串项链,由红蓝白三种颜色的珠子串成。在某一点拆开 ... -
USACO Section 1.1.3 [Friday the Thirteenth] Java题解
2011-07-04 20:22 804题意分析: 已知1900年1月1日是周一(即1900年1月13 ... -
USACO Section 1.1.2 [Greedy Gift Givers] Java题解
2011-07-04 12:31 1062解题思路: 直接用String[]保持名字的顺序,Map< ... -
USACO Section 1.1.1 [Your Ride Is Here] Java题解
2011-07-04 11:23 1597众所周知,Java的运行效率大约比C/C++慢3倍左右。大多数 ...
相关推荐
USACO题目The Clocks解答,包括代码
USACO所有题目的题解 NOCOW整理版
usaco测试数据+标程 usaco的section1到section5的所有测试数据 以及标准程序
USACO教程,包含USACO全部英文原题,题解(NOCOW整理版),翻译,教程,代码,测试数据。
适合USACO的Java选手参考
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
USACO题目Friday the Thirteenth,包含代码解析
usaco的某道题的题解
我的USACO题解和程序
USACO1.4~2.3C语言题解 绝对能通过
USACO题解(NOCOW整理版).doc
Usaco总结&题解 一位大牛写的Usaco的总结,并有所有题的题解,推荐!!
usaco全部题解。 网址:blog.csdn.net/jiangshibiao
P8898 [USACO22DEC] Feeding the Cows B 题解.docx
USACO的题目Clocks解析 ,包括解答和代码。
usaco section2.3--section5.5源程序。。。。。。。。。。。。。。。。
USACO编程题中的一个,由一般方法编程,容易看懂,仅供交流。
资源包包括USACO 2001-2007年月赛的测试数据;usaco月赛十年题典(2000-2009),usaco月赛2002-2008题解。单独下载需资源分30分以上。为了方便编程爱好者,我这边统一下载打包。欢迎下载。
丰富的USACO1.1--2.3.4的所有题解
USACO题解及中文译题1.1.1-2.4.5 题目为TXT格式文档,代码为C++语言所编写