当前位置:首页 >> >>

USACO Chapter 1 解题总结

USACO Chapter 1 解题总结
1.1.1 Your Ride Is Here 基本字符串操作,无压力。 1.1.2 Greedy Gift Givers 基础模拟题,弄明白题意,不怕麻烦,就 OK 了。 1.1.3 Friday the Thirteenth 自己的做法:三维数组代表年月日,400 的数据范围不大,模拟 走一下时间的流逝过程即可。时间复杂度 O(N*12*31),多好玩。 官方标程好像用到了一个神奇的公式,好像是什么蔡勒公式。 1.1.4 Broken Necklace 2*N 的拆环,枚举断点找即可。在找的过程中先要解决那个万能 的颜色珠子,如果起点是那个珠子,先累加答案,之后到头之后,再 按规则找。 1.2.1 Milking Cows 问题模型:找被覆盖的最长区间,和没有覆盖的最小区间长度。 自己用了一个基于扫描线的思想,遇到起点入栈,终点出栈,每遇到 一个点就计算一下当前长度。注意细节即可。 1.2.2 Transformations 非常恶心的模拟题,让人想吐。不多说。 1.2.3 Name That Number 双文件读入注意一下,解决了这个问题然后正常模拟就可以。 1.2.4 Palindromic Squares

进制转换基础 + 判断回文数。 1.2.5 Dual Palindromes 进 制 转 换 。 可 以 开 一 个 这 样 的 数 组 base[]={“0123456789ABCDEFG”}; 1.3.1 Mixing Milk 刚学不到 2 个月奥赛时候做的题,按照生活思路去贪心,注意贪 心的题,一般开始都要先排个序。 1.3.2 Barn Repair 区间动态规划,同 “乘积最大” 。注意细节即可。 1.3.3 Prime Cryptarithm 牛式,暴力枚举。注意数位就可以。 1.3.4 Combination Lock 正常循环加判断就行,话说自己一开始错是因为没有注意到这东 西是个环,是位置差 2,不是数值差 2。 1.3.5 Wormholes 第一章的 Boss,话说出来的有点早。搜索 + 剪枝 + 模拟,解题 报告已经写了。 1.3.6 Ski Course Design 暴力枚举每个答案做就行。一开始想复杂了。 1.4.1 Arithmetic Progressions 话说这题倒是让自己语文觉得不好了,读了 N 多遍题才明白。 类比于搜索,要学习的还是剪枝的技巧,当我写完解题报告之后

才发现自己有多么愚蠢。记住一个:你要找的等差数列的第一个数一 定是这个双平方数集合中的某个 BABY。然后枚举公差就可以。注意 剪枝。 1.4.2 Mother’s Milk BFS 搜索每一步的每种倒法, 一定要注意不合法的倒法是不能够 入队的,至于为什么,嘿嘿,自己试过就知道了。 1.5.1 Number Triangles 动态规划第一题,谁都是从这题开始 DP 的,放这里主要是让你 学习一下滚动数组。 1.5.2 Prime Palindromes 回文质数, 它给的两个性质很好, 只有奇数可能是质数 (2 除外) , 先找回文数再找质数。如果是暴力的做法,你打个表,如果是正解, 你就写个生成不同位数回文数的东西,然后判断素数就可以。话说我 是打的表。 1.5.3 SuperPrime Rib DFS,自己还傻傻的想枚举每个素数呢。不过这个题和上个题倒 是让我复习了一下筛法。记住一个性质,如果是肋骨数,那么第一位 一定是 2、3、5、7,最后一位一定是 1、3、7、9。信不信由你。 反正我信了。


更多相关标签: